CSES - Putka Open 2020 – 3/5 - Results
Submission details
Task:Numerot
Sender:Laakeri
Submission time:2020-10-17 20:42:52 +0300
Language:C++ (C++11)
Status:READY
Result:100
Feedback
groupverdictscore
#1ACCEPTED12
#2ACCEPTED13
#3ACCEPTED75
Test results
testverdicttimegroup
#1ACCEPTED0.04 s1, 2, 3details
#2ACCEPTED0.04 s2, 3details
#3ACCEPTED0.10 s3details

Code

#include <bits/stdc++.h>
#define F first
#define S second
using namespace std;
typedef uint64_t ll;
pair<ll, ll> dp[22][10][10][10];
ll ff(ll n) {
if (n==0) return 0;
if (n<10) return 1;
ll fn=0;
ll subs=0;
ll k=1;
ll lv=0;
ll x=n/10;
ll y=0;
while (x){
k*=10;
if (lv==0){
fn++;
if (x%10!=0){
lv=x%10;
subs=lv*k;
}
} else {
y=max(y, x%10);
}
x/=10;
}
assert(fn>0&&lv>0&&subs>=10);
auto u = dp[fn][lv][n%10][y];
n-=subs;
n-=n%10;
n+=(ll)u.S;
return u.F+ff(n);
}
pair<ll, ll> fa(ll n, ll y, bool init) {
if (n<10) return {0, n};
ll fn=0;
ll subs=0;
ll k=1;
ll lv=0;
ll x=n/10;
ll ny=y;
ll ma=max(y, n%10);
while (x){
ma=max(ma, x%10);
k*=10;
if (lv==0){
fn++;
if (x%10!=0){
lv=x%10;
subs=lv*k;
}
} else {
ny=max(ny, x%10);
}
x/=10;
}
assert(fn>0&&lv>0&&subs>=10);
if (!init) {
auto u = dp[fn][lv][n%10][ny];
n-=subs;
n-=n%10;
n+=(ll)u.S;
auto uu = fa(n, y, false);
return {u.F+uu.F, uu.S};
}
if (ma>n%10){
auto uu=fa(n-ma, y, false);
return {1+uu.F, uu.S};
} else {
auto uu=fa(n-n%10, y, true);
return {1+uu.F, uu.S};
}
}
int f[1010101];
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
for (int i=1;i<=1000000;i++){
f[i]=i;
int x=i;
while (x){
f[i]=min(f[i], f[i-x%10]+1);
x/=10;
}
}
for (int n=0;n<19;n++){
for (int m=0;m<10;m++){
for (int k=0;k<10;k++){
for (int x=0;x<10;x++){
if (n==0){
dp[n][m][k][x]={0, k};
continue;
}
ll num=m;
for (int i=0;i<n;i++){
num*=10;
}
num+=k;
dp[n][m][k][x]=fa(num, x, true);
}
}
}
}
int t;
cin>>t;
for (int i=0;i<t;i++){
ll x;
cin>>x;
uint64_t mi=0;
uint64_t ma=x*9;
while (mi<=ma){
uint64_t mid = (mi+ma)/2ull;
ll y=ff(mid);
if(y<x){
mi=mid+1;
} else {
ma=mid-1;
}
}
cout<<mi<<endl;
}
}

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