49892023-04-08 15:43:45TomaSajtHázszámokcpp17Wrong answer 20/1008ms6084 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 = 60; i >= 0; i--) {
    ll next = curr + (1ll << i);
    if (is_enough(next)) {
      curr = next;
    }
  }
  cout << curr;
}
SubtaskSumTestVerdictTimeMemory
subtask10/0
1Wrong answer8ms3084 KiB
2Accepted3ms2276 KiB
3Accepted4ms2632 KiB
subtask20/25
4Wrong answer8ms3700 KiB
5Wrong answer8ms4216 KiB
6Wrong answer7ms4136 KiB
7Accepted3ms3124 KiB
8Accepted3ms3300 KiB
9Accepted3ms3396 KiB
10Wrong answer7ms4580 KiB
11Wrong answer6ms4096 KiB
12Accepted3ms3472 KiB
13Accepted3ms3900 KiB
14Accepted3ms4132 KiB
15Accepted3ms4004 KiB
16Accepted3ms4064 KiB
17Accepted3ms4056 KiB
18Accepted3ms4052 KiB
19Accepted3ms4196 KiB
subtask30/10
20Wrong answer7ms5240 KiB
21Wrong answer7ms5360 KiB
22Wrong answer8ms5360 KiB
23Wrong answer7ms5492 KiB
24Wrong answer7ms5308 KiB
subtask40/15
25Wrong answer7ms5436 KiB
26Wrong answer6ms5204 KiB
27Accepted4ms4932 KiB
28Accepted4ms4932 KiB
29Accepted4ms4968 KiB
30Accepted3ms4696 KiB
31Accepted4ms5072 KiB
32Accepted4ms5088 KiB
33Accepted4ms5088 KiB
subtask520/20
34Accepted3ms4836 KiB
35Accepted3ms4928 KiB
36Accepted4ms5196 KiB
37Accepted4ms5304 KiB
38Accepted4ms5212 KiB
39Accepted4ms5012 KiB
40Accepted4ms5156 KiB
41Accepted4ms5036 KiB
42Accepted4ms5128 KiB
subtask60/30
43Wrong answer7ms5876 KiB
44Wrong answer6ms5556 KiB
45Accepted4ms5004 KiB
46Accepted4ms5056 KiB
47Accepted4ms5316 KiB
48Accepted4ms5436 KiB
49Accepted4ms5244 KiB
50Accepted4ms5256 KiB
51Accepted4ms5260 KiB
52Wrong answer8ms6084 KiB
53Wrong answer6ms5736 KiB
54Accepted4ms5228 KiB
55Accepted4ms5544 KiB
56Accepted4ms5472 KiB
57Accepted4ms5500 KiB
58Accepted4ms5752 KiB
59Accepted4ms5596 KiB
60Accepted4ms5456 KiB