49902023-04-08 15:45:52TomaSajtHázszámokcpp17Wrong answer 20/1008ms6456 KiB
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int base;

map<pair<ll, int>, 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 pog(ll n, int d) {
  if (n <= 0)
    return 0;
  if (mem.count({n, d})) {
    return mem.at(pair<ll, int>(n, d));
  }
  ll r = n % base;
  ll q = n / base;
  ll res = q + (r + 1) * pog(q, d) + (base - r - 1) * pog(q - 1, d);
  if (d != 0 && r >= d) {
    res++;
  }
  return mem[pair<ll, int>(n, d)] = res;
}

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

  ll curr = 0;
  for (int i = 61; i >= 0; i--) {
    ll next = curr + (1ll << i);
    if (is_enough(next)) {
      curr = next;
    }
  }
  cout << curr;
}
SubtaskSumTestVerdictTimeMemory
subtask10/0
1Wrong answer8ms3112 KiB
2Accepted3ms2260 KiB
3Accepted4ms2412 KiB
subtask20/25
4Wrong answer8ms3516 KiB
5Wrong answer8ms3616 KiB
6Wrong answer8ms3828 KiB
7Accepted3ms2960 KiB
8Accepted3ms3252 KiB
9Accepted4ms3384 KiB
10Wrong answer8ms4672 KiB
11Wrong answer6ms4284 KiB
12Wrong answer4ms4064 KiB
13Wrong answer6ms4408 KiB
14Accepted3ms4068 KiB
15Accepted3ms3984 KiB
16Accepted3ms3916 KiB
17Accepted3ms3980 KiB
18Accepted3ms4252 KiB
19Accepted3ms4200 KiB
subtask30/10
20Wrong answer8ms5408 KiB
21Wrong answer8ms5404 KiB
22Wrong answer8ms5396 KiB
23Wrong answer8ms5400 KiB
24Wrong answer8ms5392 KiB
subtask40/15
25Wrong answer8ms5620 KiB
26Wrong answer6ms5216 KiB
27Wrong answer6ms5072 KiB
28Wrong answer6ms5216 KiB
29Accepted4ms5116 KiB
30Accepted3ms4812 KiB
31Accepted4ms5048 KiB
32Accepted4ms5144 KiB
33Accepted4ms5152 KiB
subtask520/20
34Accepted3ms4944 KiB
35Accepted3ms5100 KiB
36Accepted4ms5260 KiB
37Accepted4ms5228 KiB
38Accepted4ms5236 KiB
39Accepted4ms5232 KiB
40Accepted4ms5280 KiB
41Accepted4ms5252 KiB
42Accepted4ms5492 KiB
subtask60/30
43Wrong answer8ms6316 KiB
44Wrong answer6ms5740 KiB
45Wrong answer6ms5724 KiB
46Wrong answer6ms5876 KiB
47Accepted4ms5484 KiB
48Accepted4ms5500 KiB
49Accepted4ms5412 KiB
50Accepted4ms5472 KiB
51Accepted4ms5536 KiB
52Wrong answer8ms6456 KiB
53Wrong answer6ms5948 KiB
54Wrong answer4ms5924 KiB
55Wrong answer6ms5936 KiB
56Accepted4ms5476 KiB
57Accepted4ms5496 KiB
58Accepted4ms5752 KiB
59Accepted4ms5452 KiB
60Accepted4ms5460 KiB