/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 300 点
問題文
各桁に 0 が出現しないような正の整数 N が与えられます。
N の桁数を k とします。N の桁を 0 個以上 k 個未満消して、残った桁をそのままの順序で結合することで 3 の倍数を作りたいです。
3 の倍数を作ることができるか判定し、作ることができるなら作るのに必要な最少の消す桁数を求めてください。
制約
- 1 \le N \lt 10^{18}
- N は各桁に 0 が出現しない整数
入力
入力は以下の形式で標準入力から与えられる。
N
出力
3 の倍数を作ることができないなら -1 を、作ることができるなら作るのに必要な最少の消す桁数を出力せよ。
入力例 1
35
出力例 1
1
5 を消した 3 という数は 3 の倍数です。このとき消した桁数は 1 で最少です。
入力例 2
369
出力例 2
0
1 つも桁を消さなくてもいいことに注意してください。
入力例 3
6227384
出力例 3
1
例えば、 8 を消した 622734 は 3 の倍数です。
入力例 4
11
出力例 4
-1
消す桁数は N の桁数を k として 0 個以上 k 個未満でなければならないため、全部の桁を消すことはできないことに注意してください。
この場合問題文に従って 3 の倍数を作ることは不可能なため -1 を出力します。
Score : 300 points
Problem Statement
Given is a positive integer N, where none of the digits is 0.
Let k be the number of digits in N. We want to make a multiple of 3 by erasing at least 0 and at most k-1 digits from N and concatenating the remaining digits without changing the order.
Determine whether it is possible to make a multiple of 3 in this way. If it is possible, find the minimum number of digits that must be erased to make such a number.
Constraints
- 1 \le N \lt 10^{18}
- None of the digits in N is 0.
Input
Input is given from Standard Input in the following format:
N
Output
If it is impossible to make a multiple of 3, print -1; otherwise, print the minimum number of digits that must be erased to make such a number.
Sample Input 1
35
Sample Output 1
1
By erasing the 5, we get the number 3, which is a multiple of 3. Here we erased the minimum possible number of digits - 1.
Sample Input 2
369
Sample Output 2
0
Note that we can choose to erase no digit.
Sample Input 3
6227384
Sample Output 3
1
For example, by erasing the 8, we get the number 622734, which is a multiple of 3.
Sample Input 4
11
Sample Output 4
-1
Note that we must erase at least 0 and at most k-1 digits, where k is the number of digits in N, so we cannot erase all the digits.
In this case, it is impossible to make a multiple of 3 in the way described in the problem statement, so we should print -1.