71872024-01-02 15:03:29anonSzivárványszámokcpp17Wrong answer 24/453ms4932 KiB
#include <bits/stdc++.h>
#define FastIO ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL)
typedef long long ll;
using namespace std;
ll solve(string N, ll limit, bool left, unordered_map<string, ll> &dp) {
    ll i, ans;
    string key = N + " " + to_string(limit) + " " + (left ? "1" : "0");
    auto found = dp.find(key);
    if(found == dp.end()) {
        if(N.empty())
            ans = !left;
        else {
            ans = 0;
            if(left) {
                for(i = limit; i <= (N[0] - '0'); i++) {
                    string ns;
                    if(i == (N[0] - '0'))
                        ns = N.substr(1);
                    else
                        ns = string(N.size() - 1, '9');
                    ans += solve(ns, i, true, dp) + solve(ns, i - 1, false, dp);
                }
            }
            else {
                for(i = min(limit, (ll) (N[0] - '0')); i >= 0; i--) {
                    string ns;
                    if(i == (N[0] - '0'))
                        ns = N.substr(1);
                    else
                        ns = string(N.size() - 1, '9');
                    ans += solve(ns, i, false, dp);
                }
            }
        }
        dp[key] = ans;
    }
    else
        ans = found->second;
    return ans;
}
int main() {
    FastIO;
    ll i, ans, N;
    string ns;
    unordered_map<string, ll> dp;
    cin >> N;
    ns = to_string(N - 1);
    ans = solve(ns, 1, true, dp);
    for(i = 0; i < ns.size(); i++)
        ans += solve(string(i, '9'), 1, true, dp);
    cout << ans + 1 << '\n';
    return 0;
}
SubtaskSumTestVerdictTimeMemory
base24/45
1Accepted0/03ms2108 KiB
2Accepted0/03ms2320 KiB
3Wrong answer0/03ms2464 KiB
4Accepted1/13ms2340 KiB
5Accepted1/13ms2568 KiB
6Accepted1/13ms2700 KiB
7Accepted1/13ms2920 KiB
8Accepted1/13ms2992 KiB
9Accepted1/13ms3032 KiB
10Accepted1/13ms3112 KiB
11Accepted1/13ms3116 KiB
12Accepted1/13ms3244 KiB
13Accepted2/23ms3340 KiB
14Accepted2/23ms3456 KiB
15Accepted2/23ms3552 KiB
16Accepted2/23ms3628 KiB
17Accepted1/13ms3988 KiB
18Wrong answer0/23ms4024 KiB
19Wrong answer0/23ms3884 KiB
20Wrong answer0/23ms4096 KiB
21Wrong answer0/33ms4152 KiB
22Accepted2/23ms4404 KiB
23Accepted2/23ms4348 KiB
24Accepted2/23ms4420 KiB
25Wrong answer0/23ms4428 KiB
26Wrong answer0/23ms4420 KiB
27Wrong answer0/23ms4312 KiB
28Wrong answer0/23ms4504 KiB
29Wrong answer0/23ms4716 KiB
30Wrong answer0/23ms4932 KiB