/* -*- coding: utf-8 -*- * * 491.cc: No.491 10^9+1ăšć›žæ–‡ - yukicoder */ #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; /* constant */ /* typedef */ typedef long long ll; /* global variables */ /* subroutines */ int ts[10], es[10], ds[10]; /* main */ int main() { ts[0] = 1; for (int i = 1; i <= 9; i++) ts[i] = ts[i - 1] * 10; es[0] = 1; es[1] = es[2] = 9; for (int i = 3; i <= 9; i++) es[i] = es[i - 2] * 10; //for (int i = 0; i <= 9; i++) printf("es[%d]=%d\n", i, es[i]); ll n; cin >> n; ll m = n / 1000000000; if (m > n % 1000000000) m--; //printf("m=%lld\n", m); int k = 0; while (m > 0) { ds[k++] = m % 10; m /= 10; } //printf("k=%d\n", k); int sum = 0; for (int i = 1; i < k; i++) sum += es[i]; for (int i0 = k - 1, i1 = 0; i0 >= i1; i0--, i1++) { sum += ((i1 == 0) ? ds[i0] - 1 : ds[i0]) * ts[(i0 - i1) / 2]; if (ds[i0] > ds[i1]) break; } sum++; printf("%d\n", sum); return 0; }