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

Code

#include <bits/stdc++.h>
using namespace std;
using ull = unsigned long long;
const ull INF = 9 * (ull)1e18;
const int K = 20;
const int D = 10;
pair<ull, int> dp[K + 1][D][D];
pair<ull, int> advance(pair<ull, int> cur, int k, int b, int d) {
// if (k <= 3) cerr << "advance(" << cur.first << "," << cur.second << " ;; " << k << ' ' << b << ' ' << d << "): ";
for (; d >= 0; --d) {
auto tmp = dp[k-1][max(b, d)][cur.second];
cur.first += tmp.first;
cur.second = tmp.second;
}
// if (k <= 3) cerr << cur.first << ' ' << cur.second << '\n';
return cur;
}
ull count(ull v) {
if (v < 10) return 1;
// cerr << "count " << v << ": ";
vector<int> nums;
while(v > 0) {
nums.push_back(v % 10);
v /= 10;
}
int k = nums.size();
vector<int> prefs(k, 0);
for (int i = k-2; i >= 0; --i) prefs[i] = max(prefs[i+1], nums[i+1]);
pair<ull, int> res = dp[0][prefs[0]][nums[0]];
for (int j = 1; j < k; ++j) {
if (nums[j] == 0) continue;
res = advance(res, j, prefs[j], nums[j] - 1);
}
// cerr << res.first << endl;
return res.first;
}
void solve() {
ull x;
cin >> x;
ull low = 1;
ull high = INF;
while(low != high) {
ull mid = (low + high) >> 1;
if (count(mid) >= x) high = mid;
else low = mid + 1;
// cerr << "range: " << low << ' ' << high << endl;
}
cout << low << '\n';
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(0);
for (int b = 0; b < 10; ++b) {
for (int r = 0; r < 10; ++r) {
if (b <= r) {
dp[0][b][r] = (b == 0 ? make_pair<ull, int>((r != 0), 0) : make_pair<ull, int>(2, 10 - b));
} else {
dp[0][b][r] = {1, 10 - max(0, b - r)};
}
}
}
for (int k = 1; k <= K; ++k) {
for (int b = 0; b < 10; ++b) {
for (int r = 0; r < 10; ++r) {
dp[k][b][r] = advance({0, r}, k, b, 9);
}
}
}
int t;
cin >> t;
for (int ti = 0; ti < t; ++ti) solve();
}

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