49932023-04-08 15:59:24TomaSajtHázszámokcpp17Accepted 100/1004ms5552 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;
}
SubtaskSumTestVerdictTimeMemory
subtask10/0
1Accepted3ms1824 KiB
2Accepted3ms2204 KiB
3Accepted4ms2496 KiB
subtask225/25
4Accepted3ms2328 KiB
5Accepted3ms2460 KiB
6Accepted3ms2672 KiB
7Accepted3ms2800 KiB
8Accepted3ms3052 KiB
9Accepted3ms3108 KiB
10Accepted3ms3120 KiB
11Accepted4ms3308 KiB
12Accepted3ms3372 KiB
13Accepted3ms3400 KiB
14Accepted3ms3796 KiB
15Accepted3ms3680 KiB
16Accepted3ms3532 KiB
17Accepted3ms3580 KiB
18Accepted3ms3480 KiB
19Accepted3ms3540 KiB
subtask310/10
20Accepted4ms3764 KiB
21Accepted4ms3964 KiB
22Accepted4ms4300 KiB
23Accepted3ms3972 KiB
24Accepted4ms4488 KiB
subtask415/15
25Accepted4ms4364 KiB
26Accepted4ms4392 KiB
27Accepted4ms4336 KiB
28Accepted4ms4460 KiB
29Accepted4ms4372 KiB
30Accepted3ms4112 KiB
31Accepted4ms4372 KiB
32Accepted4ms4404 KiB
33Accepted4ms4600 KiB
subtask520/20
34Accepted3ms4348 KiB
35Accepted3ms4412 KiB
36Accepted4ms4504 KiB
37Accepted4ms4648 KiB
38Accepted4ms4884 KiB
39Accepted4ms4728 KiB
40Accepted4ms4776 KiB
41Accepted4ms5072 KiB
42Accepted4ms5060 KiB
subtask630/30
43Accepted4ms5084 KiB
44Accepted4ms5104 KiB
45Accepted4ms4936 KiB
46Accepted4ms5092 KiB
47Accepted4ms5112 KiB
48Accepted4ms5184 KiB
49Accepted3ms5100 KiB
50Accepted4ms5224 KiB
51Accepted4ms5420 KiB
52Accepted3ms4956 KiB
53Accepted4ms5268 KiB
54Accepted4ms5236 KiB
55Accepted4ms5284 KiB
56Accepted4ms5252 KiB
57Accepted4ms5280 KiB
58Accepted4ms5552 KiB
59Accepted4ms5228 KiB
60Accepted4ms5240 KiB