4993 2023. 04. 08 15:59:24 TomaSajt Házszámok cpp17 Accepted 100/100 4ms 5552 KiB 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int base;
map<pair<int, ll>, ll> mem;

// I have no idea how this works, just started messing around with formulas on
// OEIS and got this working

// calculates the number of `d` digits used from `1..n`
ll num_of_digits_upto(int d, ll n) {
  if (n <= 0)
    return 0;
  if (mem.count({d, n}))
    return mem.at({d, n});
  ll r = n % base;
  ll q = n / base;
  ll res = q + (r + 1) * num_of_digits_upto(d, q) +
           (base - r - 1) * num_of_digits_upto(d, q - 1);
  if (d != 0 && r >= d)
    res++;
  return mem[pair<int, ll>(d, n)] = res;
}

int main() {
  cin >> base;
  vector<ll> budget(base);
  for (auto &b : budget)
    cin >> b;
  auto is_enough = [&](ll n) {
    for (int d = 0; d < base; d++) {
      if (num_of_digits_upto(d, n) > budget[d])
        return false;
    }
    return true;
  };

  ll curr = 0;
  for (int i = 55; i >= 0; i--) {
    ll next = curr + (1ll << i);
    if (is_enough(next))
      curr = next;
  }
  cout << curr;
}
Subtask Sum Test Verdict Time Memory
subtask1 0/0
1 Accepted 3ms 1824 KiB
2 Accepted 3ms 2204 KiB
3 Accepted 4ms 2496 KiB
subtask2 25/25
4 Accepted 3ms 2328 KiB
5 Accepted 3ms 2460 KiB
6 Accepted 3ms 2672 KiB
7 Accepted 3ms 2800 KiB
8 Accepted 3ms 3052 KiB
9 Accepted 3ms 3108 KiB
10 Accepted 3ms 3120 KiB
11 Accepted 4ms 3308 KiB
12 Accepted 3ms 3372 KiB
13 Accepted 3ms 3400 KiB
14 Accepted 3ms 3796 KiB
15 Accepted 3ms 3680 KiB
16 Accepted 3ms 3532 KiB
17 Accepted 3ms 3580 KiB
18 Accepted 3ms 3480 KiB
19 Accepted 3ms 3540 KiB
subtask3 10/10
20 Accepted 4ms 3764 KiB
21 Accepted 4ms 3964 KiB
22 Accepted 4ms 4300 KiB
23 Accepted 3ms 3972 KiB
24 Accepted 4ms 4488 KiB
subtask4 15/15
25 Accepted 4ms 4364 KiB
26 Accepted 4ms 4392 KiB
27 Accepted 4ms 4336 KiB
28 Accepted 4ms 4460 KiB
29 Accepted 4ms 4372 KiB
30 Accepted 3ms 4112 KiB
31 Accepted 4ms 4372 KiB
32 Accepted 4ms 4404 KiB
33 Accepted 4ms 4600 KiB
subtask5 20/20
34 Accepted 3ms 4348 KiB
35 Accepted 3ms 4412 KiB
36 Accepted 4ms 4504 KiB
37 Accepted 4ms 4648 KiB
38 Accepted 4ms 4884 KiB
39 Accepted 4ms 4728 KiB
40 Accepted 4ms 4776 KiB
41 Accepted 4ms 5072 KiB
42 Accepted 4ms 5060 KiB
subtask6 30/30
43 Accepted 4ms 5084 KiB
44 Accepted 4ms 5104 KiB
45 Accepted 4ms 4936 KiB
46 Accepted 4ms 5092 KiB
47 Accepted 4ms 5112 KiB
48 Accepted 4ms 5184 KiB
49 Accepted 3ms 5100 KiB
50 Accepted 4ms 5224 KiB
51 Accepted 4ms 5420 KiB
52 Accepted 3ms 4956 KiB
53 Accepted 4ms 5268 KiB
54 Accepted 4ms 5236 KiB
55 Accepted 4ms 5284 KiB
56 Accepted 4ms 5252 KiB
57 Accepted 4ms 5280 KiB
58 Accepted 4ms 5552 KiB
59 Accepted 4ms 5228 KiB
60 Accepted 4ms 5240 KiB