71872024-01-02 15:03:29anonSzivárványszámokcpp17Hibás válasz 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;
}
RészfeladatÖsszpontTesztVerdiktIdőMemória
base24/45
1Elfogadva0/03ms2108 KiB
2Elfogadva0/03ms2320 KiB
3Hibás válasz0/03ms2464 KiB
4Elfogadva1/13ms2340 KiB
5Elfogadva1/13ms2568 KiB
6Elfogadva1/13ms2700 KiB
7Elfogadva1/13ms2920 KiB
8Elfogadva1/13ms2992 KiB
9Elfogadva1/13ms3032 KiB
10Elfogadva1/13ms3112 KiB
11Elfogadva1/13ms3116 KiB
12Elfogadva1/13ms3244 KiB
13Elfogadva2/23ms3340 KiB
14Elfogadva2/23ms3456 KiB
15Elfogadva2/23ms3552 KiB
16Elfogadva2/23ms3628 KiB
17Elfogadva1/13ms3988 KiB
18Hibás válasz0/23ms4024 KiB
19Hibás válasz0/23ms3884 KiB
20Hibás válasz0/23ms4096 KiB
21Hibás válasz0/33ms4152 KiB
22Elfogadva2/23ms4404 KiB
23Elfogadva2/23ms4348 KiB
24Elfogadva2/23ms4420 KiB
25Hibás válasz0/23ms4428 KiB
26Hibás válasz0/23ms4420 KiB
27Hibás válasz0/23ms4312 KiB
28Hibás válasz0/23ms4504 KiB
29Hibás válasz0/23ms4716 KiB
30Hibás válasz0/23ms4932 KiB