Divide by Three codeforces

C. Divide by Three time limit per test 1 second memory limit per test 256 megabytes input standard input output standard output

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

The number is called beautiful if it consists of at least one digit, doesn't have leading zeroes and is a multiple of 3. For example, 0, 99,10110 are beautiful numbers, and 00, 03, 122 are not.

Write a program which for the given n will find a beautiful 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.

If it's impossible to obtain a beautiful number, print -1. If there are multiple answers, print any of them.

Input

The first line of input contains n — a positive integer number without leading zeroes (1 ≤ n < 10100000).

Output

Print one number — any beautiful number obtained by erasing as few as possible digits. If there is no answer, print  - 1.

Examples input 1033 output 33 input 10 output 0 input 11 output -1 Note

In the first example it is enough to erase only the first digit to obtain a multiple of 3. But if we erase the first digit, then we obtain a number with a leading zero. So the minimum number of digits to be erased is two.

题目大意：给出一个序列，求删除最少的位数获得一个没有前置0且可以被3整除的数。

解体思路：因为最多删除不超过连个数，故将两种情况进行讨论，选取最优解。

注：这一题可以用字符串处理，这样更简单，因为vector获得长度与处理前置0没有用字符串处理起来更简单。

#include <iostream> #include <cstdio> #include <cstring> #include <vector> using namespace std; const int maxn = 1e5 + 100; int temp[maxn]; bool flag; bool ans1, ans2; void fun(vector<int> & a, int b, int c, int & l, bool & ans) { for(int k = 1; k <= c; ++k) { for(int i = l - 1; i >= 0; --i) { if(a[i] % 3 == b) { a.erase(a.begin() + i); l--; break; } } } for(int i = 0; i < l; ++i) { temp[i] = a[i]; } a.clear(); int x = 0; while(temp[x] == 0 && x < l) { x++; } for(int i = x; i < l; ++i) { a.push_back(temp[i]); } l -= x; if(l == 0 && flag) { a.push_back(0); } if(l > 0) { ans = true; } /*remove(a); int x = 0; int l = a.capacity(); for(int i = 0; i < x && a.capacity() != 1; ++i) { a.erase(a.begin() + i); }*/ } void output(vector<int> a) { int l = a.capacity(); for(int i = 0; i < l; ++i) { cout << a[i]; } cout << endl; } int main() { string s; cin >> s; vector<int> a1; vector<int> a2; int l = s.size(); int i = 0, sum = 0, sum1 = 0, sum2 = 0; int l1 = s.size(), l2 = s.size(); flag = false; while(s[i] == '0' && i < l) { i++; } for(; i < l; ++i) { a1.push_back(s[i] - '0'); a2.push_back(s[i] - '0'); sum = (sum + s[i] - '0') % 3; if((s[i] - '0') % 3 == 1) { sum1 = sum1 + 1; } if((s[i] - '0') % 3 == 2) { sum2 = sum2 + 1; } if(a1[i] == 0) { flag = true; } } if(sum % 3 == 1) { if(sum1 >= 1) { fun(a1, 1, 1, l1, ans1); } if(sum2 >= 2) { fun(a2, 2, 2, l2, ans2); } } else if(sum % 3 == 2) { if(sum1 >= 2) { fun(a1, 1, 2, l1, ans1); } if(sum2 >= 1) { fun(a2, 2, 1, l2, ans2); } } else if(sum % 3 == 0) { ans1 = true; ans2 = true; } if(!ans1 && !ans2) { if(flag) { cout << 0 << endl; } else { cout << -1 << endl; } return 0; } if(ans1 && ans2) { if(l1 >= l2) { output(a1); } else { output(a2); } return 0; } if(ans1) { output(a1); } if(ans2) { output(a2); } return 0; }