Task: | Numerot |
Sender: | Gomhog |
Submission time: | 2020-10-17 00:13:36 +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.24 s | 1, 2, 3 | details |
#2 | ACCEPTED | 0.27 s | 2, 3 | details |
#3 | ACCEPTED | 0.80 s | 3 | details |
Code
#include <bits/stdc++.h>typedef long long ll;typedef long double ld;#define F first#define S secondusing 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 |