3929 2023. 03. 05 19:07:42 zsombor Házszámok cpp17 Accepted 100/100 3ms 5284 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 (ll i = 1; i <= n; i++) {
        if (x < h[i]) {
            cnt[0] += (x - h[i - 1] + 1) * i;
            break;
        }
        cnt[0] += (k - 1) * h[i - 1] * i;
    }
    for (ll 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;
}
Subtask Sum Test Verdict Time Memory
subtask1 0/0
1 Accepted 3ms 1876 KiB
2 Accepted 3ms 2116 KiB
3 Accepted 3ms 2168 KiB
subtask2 25/25
4 Accepted 3ms 2304 KiB
5 Accepted 3ms 2520 KiB
6 Accepted 3ms 2732 KiB
7 Accepted 3ms 2944 KiB
8 Accepted 3ms 3196 KiB
9 Accepted 2ms 3244 KiB
10 Accepted 3ms 3272 KiB
11 Accepted 2ms 3340 KiB
12 Accepted 3ms 3584 KiB
13 Accepted 2ms 3664 KiB
14 Accepted 2ms 3668 KiB
15 Accepted 3ms 3552 KiB
16 Accepted 3ms 3672 KiB
17 Accepted 3ms 3672 KiB
18 Accepted 3ms 3796 KiB
19 Accepted 3ms 3880 KiB
subtask3 10/10
20 Accepted 3ms 3888 KiB
21 Accepted 2ms 3772 KiB
22 Accepted 3ms 3924 KiB
23 Accepted 3ms 3956 KiB
24 Accepted 3ms 3956 KiB
subtask4 15/15
25 Accepted 3ms 3952 KiB
26 Accepted 3ms 3848 KiB
27 Accepted 3ms 3984 KiB
28 Accepted 3ms 4096 KiB
29 Accepted 3ms 4092 KiB
30 Accepted 3ms 4212 KiB
31 Accepted 3ms 4216 KiB
32 Accepted 3ms 4340 KiB
33 Accepted 3ms 4336 KiB
subtask5 20/20
34 Accepted 3ms 4304 KiB
35 Accepted 3ms 4416 KiB
36 Accepted 3ms 4304 KiB
37 Accepted 3ms 4392 KiB
38 Accepted 3ms 4516 KiB
39 Accepted 3ms 4480 KiB
40 Accepted 3ms 4604 KiB
41 Accepted 3ms 4484 KiB
42 Accepted 3ms 4600 KiB
subtask6 30/30
43 Accepted 3ms 4624 KiB
44 Accepted 3ms 4852 KiB
45 Accepted 3ms 4824 KiB
46 Accepted 3ms 5040 KiB
47 Accepted 3ms 5140 KiB
48 Accepted 3ms 5140 KiB
49 Accepted 3ms 5140 KiB
50 Accepted 3ms 5260 KiB
51 Accepted 3ms 5172 KiB
52 Accepted 3ms 5168 KiB
53 Accepted 3ms 5168 KiB
54 Accepted 3ms 5168 KiB
55 Accepted 3ms 5164 KiB
56 Accepted 3ms 5160 KiB
57 Accepted 3ms 5284 KiB
58 Accepted 2ms 5284 KiB
59 Accepted 2ms 5044 KiB
60 Accepted 3ms 5048 KiB