CSES - Putka Open 2020 – 3/5 - Results
Submission details
Task:Numerot
Sender:Gomhog
Submission time:2020-10-17 00:13:36 +0300
Language:C++ (C++11)
Status:READY
Result:100
Feedback
groupverdictscore
#1ACCEPTED12
#2ACCEPTED13
#3ACCEPTED75
Test results
testverdicttimegroup
#1ACCEPTED0.24 s1, 2, 3details
#2ACCEPTED0.27 s2, 3details
#3ACCEPTED0.80 s3details

Code

#include <bits/stdc++.h>
typedef long long ll;
typedef long double ld;
#define F first
#define S second
using namespace std;
const ll INF=9000000000000000000LL;
ll stepcnt[19][10][10];
ll red[19][10][10];
void process() {
for (int i=1;i<10;i++) {
for (int j=0;j<10;j++) {
if (i<=10-j) {
stepcnt[1][i][j]=2;
red[1][i][j]=i;
} else {
stepcnt[1][i][j]=1;
red[1][i][j]=i-(10-j);
}
}
}
for (int po=2;po<=18;po++) {
for (int i=1;i<10;i++) {
for (int j=0;j<10;j++) {
int cu=j;
for (int k=0;k<10;k++) {
int lol=max(9-k,i);
stepcnt[po][i][j]+=stepcnt[po-1][lol][cu];
cu=red[po-1][lol][cu];
}
red[po][i][j]=cu;
}
}
}
}
ll steps(ll x) {
if (x<0) return -1;
if (x==0) return 0;
if (x%10==0) {
ll parsa=0;
ll chk=x;
while (chk) {
if (chk%10 > parsa) parsa=chk%10;
chk/=10;
}
return 1+steps(x-parsa);
}
int lol=1;
ll te=10;
while (lol<18 && 10*te-(x%(10*te)) < 10) {
lol++;
te*=10;
}
ll j = te-(x%te);
ll parsa=1;
for (ll tmp=x/te;tmp>0;tmp/=10) {
if (tmp%10 > parsa) parsa=tmp%10;
}
ll st=stepcnt[lol][parsa][j];
ll re=red[lol][parsa][j];
ll ne = (x/te)*te-re;
return st+steps(ne);
}
ll solve(ll x) {
ll lo=0;
ll hi=INF;
while (lo<hi) {
ll mid=lo+(hi-lo)/2;
if (steps(mid)<x) lo=mid+1;
else hi=mid;
}
return lo;
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
process();
int tst;
cin>>tst;
for (int t=0;t<tst;t++) {
ll x;
cin>>x;
cout<<solve(x)<<"\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