Task: | Numerot |
Sender: | mango_lassi |
Submission time: | 2020-10-17 21:01:19 +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.03 s | 1, 2, 3 | details |
#2 | ACCEPTED | 0.03 s | 2, 3 | details |
#3 | ACCEPTED | 0.04 s | 3 | details |
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 |