Task: | Numerot |
Sender: | Olli |
Submission time: | 2020-10-17 16:43:30 +0300 |
Language: | C++ (C++11) |
Status: | READY |
Result: | 100 |
group | verdict | score |
---|---|---|
#1 | ACCEPTED | 12 |
#2 | ACCEPTED | 13 |
#3 | ACCEPTED | 75 |
test | verdict | time | group | |
---|---|---|---|---|
#1 | ACCEPTED | 0.28 s | 1, 2, 3 | details |
#2 | ACCEPTED | 0.29 s | 2, 3 | details |
#3 | ACCEPTED | 0.72 s | 3 | details |
Code
#include <iostream>#include <fstream>#include <vector>#include <algorithm>#include <queue>#include <stack>using namespace std;typedef long long ll;typedef long double ld;const int N = 100;const int M = 1e5;const ll INF = 1e18;ll a[10][N]; //Answer for small valuesll b[10][N]; //Where one ends up after reducing the small valuell A[10][10][100]; //Answer for values near powers of tenll B[10][10][100]; //Where one ends up after reducing the value near power of tenll getFirstDigit(ll x) {int k = 0;ll po = 1;while(po*10 <= x) {po *= 10;++k;if(k == 18) break;}ll d = 1;while(d < 9 && (d+1)*po <= x) {++d;}return d;}ll deleteFirstDigit(ll x) {ll po = 1;int k = 0;while(po*10 <= x) {++k;po *= 10;if(k == 18) break;}ll d = 1;while(d < 9 && (d+1)*po <= x) ++d;return x - po*d;}inline ll getK(ll x) {ll k = 1;ll po = 1;while(po*10 <= x) {po *= 10;++k;if(k == 19) {return k;}}return k;}ll getEn(ll d, ll x) {if(x < N) return b[d][x];ll D = getFirstDigit(x);ll e = getEn(max(d, D), deleteFirstDigit(x));if(e == 0) {e = -max(d, D);}e += 10; e %= 10;for(ll i = D-1; i >= 1; --i) {e = B[max(d, i)][e][getK(x)-1];if(e == 0) {e -= max(d, i);}e += 10;e %= 10;}return B[d][e][getK(x)-1];}ll calc(ll d, ll x) {if(x < N) {return a[d][x];}ll D = getFirstDigit(x);ll ans = calc(max(d, D), deleteFirstDigit(x));ll e = getEn(max(d, D), deleteFirstDigit(x));if(e == 0) {++ans;e -= max(d, D);}e+=10; e%=10;ll k = getK(x);for(ll i = D-1; i >= 1; --i) {ans += A[max(d, i)][e][k-1];e = B[max(d, i)][e][k-1];if(e == 0) {++ans;e -= max(d, i);}e+=10; e%=10;}ans += A[d][e][k-1];return ans;}ll g(ll i) {ll ans = 1;while(i > 0) {ans = max(ans, i%10);i/=10;}return ans;}ll f[M];int main() {ofstream out;out.open("output3.txt");for(ll x = 1; x < N; ++x) {for(ll d = 0; d < 10; ++d) {ll j = max(d, g(x));ll y = x - j;if(y < 0) {a[d][x] = 1;b[d][x] = y;continue;}a[d][x] = a[d][y] + 1;b[d][x] = b[d][y];}}ll po = 1;for(int k = 1; k <= 18; ++k) {po *= 10;for(int d = 0; d < 10; ++d) {for(int x = 1; x <= 9; ++x) {//Consider the number 10^k - (10 - x)if(po < N) {A[d][x][k] = a[d][po - (10 - x)];B[d][x][k] = b[d][po - (10 - x)];continue;}ll ans = 0;//First reduce roughly po/10ans += (po/10)/9;if(x == 9) {++ans;}ll las = x+1;if(las == 10) las = 1;for(int i = 8; i >= 0; --i) {ans += A[max(d, i)][las][k-1];las = B[max(d, i)][las][k-1];las = las + 10;if(las == 10 && i > 0) {++ans;las = 10 - max(d, i);}}las = las - 10;if(las == -10) las = 0;A[d][x][k] = ans;B[d][x][k] = las;}}}int t;cin >> t;while(t > 0) {--t;ll x;cin >> x;ll k = 0;for(ll bit = 62; bit >= 0; --bit) {ll ne = k + (((ll) 1) << bit);if(calc(0, ne) >= x) continue;k = ne;}++k;cout << k << "\n";/*po = 1;for(int i = 1; i <= 16; ++i) {po *= 10;}for(ll j = 16; j >= 0; --j) {for(ll d = 9; d >= 0; --d) {ll ne = k + d*po;if(calc(0, ne) >= x) {continue;}k = ne;}po/=10;}++k;cout << k << "\n";*/}return 0;for(int i = 1; i < M; ++i) {f[i] = INF;ll j = i;while(j > 0) {f[i] = min(f[i], f[i - j%10] + 1);j /= 10;}}for(int i = 1; i < M; ++i) {if(i == 10100) {cout << calc(0, i) << " " << f[i] << "\n";}if(calc(0, i) != f[i]) {cout << "Oh no!\n";cout << i << "\n";return 0;}}return 0;/*for(int i = 1; i <= 2000; ++i) {out << i << " " << calc(0, i) << "\n";}*//*int n;cin >> n;cout << calc(0, n) << "\n";*/}
Test details
Test 1
Group: 1, 2, 3
Verdict: ACCEPTED
input |
---|
1000 1 2 3 4 ... |
correct output |
---|
1 10 11 20 22 ... |
user output |
---|
1 10 11 20 22 ... Truncated |
Test 2
Group: 2, 3
Verdict: ACCEPTED
input |
---|
1000 224995 413660 249827 2125 ... |
correct output |
---|
1731724 3216040 1940719 14585 532612 ... |
user output |
---|
1731724 3216040 1940719 14585 532612 ... Truncated |
Test 3
Group: 3
Verdict: ACCEPTED
input |
---|
1000 627887018110416188 785474884983906653 653772166720939773 784335285960673683 ... |
correct output |
---|
5530371754830260284 6918696171534226533 5757755627065159149 6908439780325129803 3223801064342340738 ... |
user output |
---|
5530371754830260284 6918696171534226533 5757755627065159149 6908439780325129803 3223801064 ... Truncated |