Submission #1291049

---

Source Code Expand

#include <bits/stdc++.h>
#define INF 0x3f3f3f3f
#define maxn 500100
#define lson root << 1
#define rson root << 1 | 1
#define lent (t[root].r - t[root].l + 1)
#define lenl (t[lson].r - t[lson].l + 1)
#define lenr (t[rson].r - t[rson].l + 1)
#define N 1111
#define eps 1e-6
#define pi acos(-1.0)
#define e exp(1.0)
using namespace std;
const int mod = 1e9 + 7;
typedef long long ll;
typedef unsigned long long ull;
char s[maxn];
int a[maxn];
int len;
bool check(int x)
{
    int sum = x * 9, cnt = 0;
    for (int i = 0; i < len; i++)
    {
        sum += a[i];
        cnt += sum % 10;
        sum /= 10;
    }
    while (sum > 0)
    {
        cnt += sum % 10;
        sum /= 10;
    }
    return cnt <= x * 9;
}
int main()
{
#ifndef ONLINE_JUDGE
    freopen("in.txt", "r", stdin);
    freopen("out.txt", "w", stdout);
    long _begin_time = clock();
#endif
    while (~scanf("%s", s))
    {
        memset(a, 0, sizeof(a));
        len = strlen(s);
        reverse(s, s + len);
        for (int i = 0; i < len; i++)
            a[i] = (s[i] - '0') * 9;
        for (int i = 0; i < len; i++)
        {
            a[i + 1] += a[i] / 10;
            a[i] %= 10;
        }
        if (a[len])
            len++;
        int l = 0, r = len * 2, ans = -1;
        while (l < r)
        {
            int mid = l + r >> 1;
            if (check(mid))
            {
                ans = mid;
                r = mid;
            }
            else
                l = mid + 1;
        }
        printf("%d\n", ans);
    }
#ifndef ONLINE_JUDGE
    long _end_time = clock();
    printf("time = %ld ms.", _end_time - _begin_time);
#endif
    return 0;
}

Submission Info

Judge Result