Task: | Numerot |
Sender: | Olli |
Submission time: | 2020-10-17 16:35:52 +0300 |
Language: | C++ (C++11) |
Status: | READY |
Result: | 25 |
group | verdict | score |
---|---|---|
#1 | ACCEPTED | 12 |
#2 | ACCEPTED | 13 |
#3 | TIME LIMIT EXCEEDED | 0 |
test | verdict | time | group | |
---|---|---|---|---|
#1 | ACCEPTED | 0.02 s | 1, 2, 3 | details |
#2 | ACCEPTED | 0.06 s | 2, 3 | details |
#3 | TIME LIMIT EXCEEDED | -- | 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 values ll b[10][N]; //Where one ends up after reducing the small value ll A[10][10][100]; //Answer for values near powers of ten ll B[10][10][100]; //Where one ends up after reducing the value near power of ten ll 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; while(po*10 <= x) po *= 10; ll d = 1; while((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/10 ans += (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; 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: TIME LIMIT EXCEEDED
input |
---|
1000 627887018110416188 785474884983906653 653772166720939773 784335285960673683 ... |
correct output |
---|
5530371754830260284 6918696171534226533 5757755627065159149 6908439780325129803 3223801064342340738 ... |
user output |
---|
(empty) |