Task: | Numerot |
Sender: | ArktinenKarpalo |
Submission time: | 2020-10-18 06:48:18 +0300 |
Language: | C++ (C++17) |
Status: | READY |
Result: | 100 |
group | verdict | score |
---|---|---|
#1 | ACCEPTED | 12 |
#2 | ACCEPTED | 13 |
#3 | ACCEPTED | 75 |
test | verdict | time | group | |
---|---|---|---|---|
#1 | ACCEPTED | 0.02 s | 1, 2, 3 | details |
#2 | ACCEPTED | 0.05 s | 2, 3 | details |
#3 | ACCEPTED | 0.53 s | 3 | details |
Compiler report
input/code.cpp: In function 'std::pair<long long int, long long int> test2(long long int, long long int)': input/code.cpp:79:1: warning: label 'wat' defined but not used [-Wunused-label] wat: ^~~
Code
#include <bits/stdc++.h>#define ll long long#define ld long double#define M 1000000007using namespace std;int ans[10101010];int ans_real[10101010];int ad[11];ll md(ll n) {ll ret = 0;while(n) {ret = max(ret, n%10);n/=10;}return ret;}int f(int n) {int cnt = 0;while(n) {int luku = n;int mx = 0;while(luku) {mx = max(luku%10, mx);luku /= 10;}ad[mx]++;// cout << n << " del " << mx<<endl;n -= mx;cnt++;}return cnt;}pair<int,int> tst[111][111];ll lol(ll n, ll k) {for(int i=0; i<k; i++)n *= 10;return n;}bool ok(ll n) {while(n > 9) {if(n%10 != 0)return false;n /= 10;}return true;}pair<ll, ll> igf(ll n) {string s = to_string(n);string s2 = s;s2[0] = '0';return make_pair(stoll(s2), s[0]-'0');}int cnt = 0;map<pair<ll,ll>, pair<ll,ll>> mp;// backpair<ll,ll> test2(ll mx, ll luku) {if(luku < 10) {if(mx > luku)return {1, mx-luku};elsereturn {1, 0};}if(mx == 9)return {(luku+8)/9, (luku+8)/9*9-luku};if(mp.count(make_pair(mx, luku))==1)return mp[{mx, luku}];cnt++;if(ok(luku)) {// taulukkowat:auto asd = test2(mx, luku-max(mx, md(luku)));asd.first++;mp[make_pair(mx, luku)] = asd;return asd;}ll aluku = luku;auto res = igf(luku);auto asd = test2(max(mx, res.second), res.first);//if(asd.second != 0)// goto wat;luku = lol(res.second, to_string(luku).size()-1);luku -= asd.second;asd.second = 0;auto ret = test2(mx, luku);ret.first += asd.first;ret.second += asd.second;mp[make_pair(mx, aluku)] = ret;if(ret.second != 0) {luku = aluku;}return ret;}ll ansans(ll n) {ll ret = 0;for(ll i=62; i>=0; i--) {ll luku = ret|(1LL<<i);auto res = test2(0, luku);if(res.first < n)ret = luku;}return ret+1;}int main() {cin.tie(0);cout.tie(0);ios_base::sync_with_stdio();int t;cin >> t;for(int i=0; i<t; i++) {ll x;cin >> x;cout << ansans(x) << "\n";}return 0;ans[0] = 0;cnt = 1;for(int i=1; i<=1e7; i++) {int luku = i;ans[i] = 1e9;while(luku) {ans[i] = min(ans[i], 1+ans[i-luku%10]);luku /= 10;}if(ans[i] == cnt) {ans_real[cnt++] = i;}}cnt = 0;for(ll i=1e18; i>=1e18-1000; i--) {cout << ansans(i) << " "<<endl;// auto res = test2(0, i);// if(res.first != ans[i])// cout << res.first << " "<<i<<" " << ans[i]<<endl;cnt = 0;}// cin >> t;}
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 |