2017武大校赛网络预选赛C题 Divide by Six

DIVIDE BY SIX

无解时输出-1s而不是WTF

数据可能有前导零

Input file: standard input Output file: standard output Time limit: 1 second Memory limit: 512 mebibytes

A positive integer number n is written on a blackboard. It consists of not more than 10^510​5​​ digits. You have to transform it into a mogicalnumber by erasing some of the digits, and you want to erase as few digits as possible.

The number is lucky if it consists of at least one digit, doesn't have leading zeroes and is a multiple of 6. For example, 0, 66,66666 are lucky numbers, and 00, 25, 77 are not.

Write a program which for the given $n$ will find a mogical number such that $n$ can be transformed into this number by erasing as few digits as possible. You can erase an arbitraty set of digits. For example, they don't have to go one after another in the number $n$.

Print the length of your answer after the erasing.

If it's impossible to obtain a lucky number, print -1s.

Input

The first line of input contains $n$ -- a positive integer ( 1\le n \le 10^{100000}1≤n≤10​100000​​ ).

Output

Print one number — the number of your lucky number obtained by erasing as few as possible digits. If there is no answer, print -1s.

Example

Input 1

0010456

Output 1

4

Input 2

11

Output 2

-1s 题意：给你一个数，你可以删除任意一个，使得删除后的数字可以被6整除， 那么要求找到最少删除多少个使得剩下的数字可以被6整除，输出删除后数字的长度； 思路：学弟教的，数位dp；dp[100005][6]; i-第i位数字，j-余数位j，dp[i][j]:前i位数字余数为j时的最大长度； （前位所得的余数*10+本位数字）%6； 状态转移方程：dp[i][(j*10+t)%6]=max(dp[i][(j*10+t)%6],dp[i-1][j]); 第一个样例： 代码： #include<cstdio> #include<cstring> #include<cstdlib> #include<algorithm> using namespace std; const int maxn=100005; const int inf=1e9-1; char s[maxn]; int dp[maxn][6]; int n; int main() { int ans=-inf; scanf("%s",s+1); int len=strlen(s+1); for(int i=0;i<=len;i++) for(int j=0;j<6;j++) dp[i][j]=-inf; for(int i=1;i<=len;i++) if(s[i]=='0') ans=1; for(int i=1;i<=len;i++) { int t=s[i]-'0'; if(t!=0) dp[i][t%6]=1; for(int j=0;j<6;j++) dp[i][j]=max(dp[i][j],dp[i-1][j]); for(int j=0;j<6;j++) dp[i][(j*10+t)%6]=max(dp[i][(j*10+t)%6],dp[i-1][j]+1); ans=max(ans,dp[i][0]); } if(ans==-inf) printf("-1s\n"); else printf("%d\n",ans); return 0; } 另外一道题，不过要输出的不是长度而是数，|还没解决|http://codeforces.com/problemset/problem/792/C