Task: | Numerot |
Sender: | Laakeri |
Submission time: | 2020-10-17 20:42:52 +0300 |
Language: | C++ (C++11) |
Status: | READY |
Result: | 100 |
group | verdict | score |
---|---|---|
#1 | ACCEPTED | 12 |
#2 | ACCEPTED | 13 |
#3 | ACCEPTED | 75 |
test | verdict | time | group | |
---|---|---|---|---|
#1 | ACCEPTED | 0.04 s | 1, 2, 3 | details |
#2 | ACCEPTED | 0.04 s | 2, 3 | details |
#3 | ACCEPTED | 0.10 s | 3 | details |
Code
#include <bits/stdc++.h>#define F first#define S secondusing 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 |