39262023-03-05 18:16:45zsomborHázszámokcpp17Wrong answer 25/1003ms5392 KiB
#include <iostream>
#include <vector>
using namespace std;
using ll = long long;

ll k, n = 0;
vector <ll> h(50, 1);
vector <ll> CNT(10, 0);
vector <ll> cnt(10, 0);
vector <ll> v(50, 0);

bool check(ll x) {
    fill(cnt.begin(), cnt.end(), 0);
    fill(v.begin(), v.end(), 0);
    for (int i = 1; i <= n; i++) {
        if (x < h[i]-1) {
            cnt[0] += ((x + 1) % h[i - 1]) * i;
            break;
        }
        cnt[0] += (k - 1) * h[i - 1] * i;
    }
    for (int i = n; i >= 0; i--) {
        v[i] = x / h[i];
        x %= h[i];
        if (v[i]) cnt[v[i]] += x + 1;
        for (int j = 1; j < v[i]; j++) cnt[j] += h[i];
        for (int j = 1; j < k; j++) cnt[j] += h[i] * i / k * v[i];
    }
    for (int i = 1; i < k; i++) cnt[0] -= cnt[i];
    for (int i = 0; i < k; i++) if (cnt[i] > CNT[i]) return false;
    return true;
}

int main()
{
    cin >> k;
    while (h[n] < 1e13) { n++; h[n] = k * h[n - 1]; }
    for (int i = 0; i < k; i++) cin >> CNT[i];
    ll l = 0, r = 1e13, m;
    while (r - l > 1) {
        m = (l + r) / 2;
        (check(m) ? l = m : r = m);
    }
    cout << l;
}
SubtaskSumTestVerdictTimeMemory
subtask10/0
1Accepted3ms1872 KiB
2Accepted3ms2124 KiB
3Accepted3ms2336 KiB
subtask20/25
4Accepted3ms2552 KiB
5Accepted3ms2712 KiB
6Accepted3ms2820 KiB
7Accepted3ms3032 KiB
8Accepted2ms3140 KiB
9Accepted2ms3140 KiB
10Accepted3ms3140 KiB
11Accepted3ms3104 KiB
12Accepted2ms3104 KiB
13Accepted2ms3120 KiB
14Accepted2ms3116 KiB
15Wrong answer2ms3116 KiB
16Accepted3ms3244 KiB
17Accepted2ms3332 KiB
18Accepted2ms3328 KiB
19Accepted2ms3332 KiB
subtask310/10
20Accepted3ms3568 KiB
21Accepted3ms4052 KiB
22Accepted3ms4128 KiB
23Accepted3ms4004 KiB
24Accepted3ms4028 KiB
subtask415/15
25Accepted3ms4092 KiB
26Accepted3ms4092 KiB
27Accepted3ms4228 KiB
28Accepted3ms4340 KiB
29Accepted3ms4420 KiB
30Accepted2ms4424 KiB
31Accepted3ms4660 KiB
32Accepted3ms4632 KiB
33Accepted3ms4744 KiB
subtask50/20
34Accepted3ms4736 KiB
35Accepted3ms4896 KiB
36Wrong answer3ms4788 KiB
37Accepted3ms4780 KiB
38Accepted3ms4676 KiB
39Accepted3ms4684 KiB
40Accepted3ms4756 KiB
41Accepted2ms4756 KiB
42Accepted3ms4872 KiB
subtask60/30
43Accepted3ms4868 KiB
44Accepted3ms5000 KiB
45Accepted3ms5260 KiB
46Accepted2ms5216 KiB
47Accepted3ms5316 KiB
48Wrong answer3ms5320 KiB
49Accepted3ms5392 KiB
50Accepted3ms5216 KiB
51Accepted3ms5224 KiB
52Accepted3ms5220 KiB
53Accepted3ms5336 KiB
54Accepted2ms5340 KiB
55Accepted2ms5332 KiB
56Accepted2ms5336 KiB
57Accepted3ms5232 KiB
58Accepted3ms5340 KiB
59Accepted3ms5228 KiB
60Accepted3ms5344 KiB