CSES - Putka Open 2020 – 3/5 - Results
Submission details
Task:Numerot
Sender:Olli
Submission time:2020-10-17 16:43:30 +0300
Language:C++ (C++11)
Status:READY
Result:100
Feedback
groupverdictscore
#1ACCEPTED12
#2ACCEPTED13
#3ACCEPTED75
Test results
testverdicttimegroup
#1ACCEPTED0.28 s1, 2, 3details
#2ACCEPTED0.29 s2, 3details
#3ACCEPTED0.72 s3details

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;
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/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;
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