CSES - Putka Open 2020 – 3/5 - Results
Submission details
Task:Numerot
Sender:Gomhog
Submission time:2020-10-17 00:13:36 +0300
Language: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
...

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
...

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
3223801064342340738
...