49842023-04-08 15:31:50TomaSajtHázszámokcpp17Time limit exceeded 0/100300ms5296 KiB
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int base;

// 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;
  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)
    return res + 1;
  return res;
}

int main() {
  cin >> base;
  vector<ll> budget(base);
  for (auto &b : budget)
    cin >> b;
  auto is_enough = [&](int 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 = 30; i >= 0; i--) {
    ll next = curr + (1ll << i);
    if (is_enough(next)) {
      curr = next;
    }
  }
  cout << curr;
}
SubtaskSumTestVerdictTimeMemory
subtask10/0
1Time limit exceeded272ms1784 KiB
2Accepted3ms2064 KiB
3Wrong answer13ms2272 KiB
subtask20/25
4Time limit exceeded261ms1748 KiB
5Time limit exceeded272ms2656 KiB
6Time limit exceeded259ms2856 KiB
7Accepted3ms2972 KiB
8Accepted3ms2936 KiB
9Accepted3ms3064 KiB
10Time limit exceeded300ms3276 KiB
11Accepted29ms3392 KiB
12Accepted4ms3488 KiB
13Accepted3ms3704 KiB
14Accepted3ms3912 KiB
15Accepted3ms4124 KiB
16Accepted3ms4204 KiB
17Accepted3ms4236 KiB
18Accepted3ms4308 KiB
19Accepted3ms4312 KiB
subtask30/10
20Time limit exceeded280ms4516 KiB
21Time limit exceeded259ms4632 KiB
22Time limit exceeded268ms4732 KiB
23Time limit exceeded247ms4616 KiB
24Time limit exceeded248ms4496 KiB
subtask40/15
25Time limit exceeded263ms4628 KiB
26Time limit exceeded268ms4600 KiB
27Wrong answer115ms4516 KiB
28Wrong answer37ms4640 KiB
29Wrong answer17ms4764 KiB
30Accepted3ms4736 KiB
31Wrong answer9ms4844 KiB
32Wrong answer8ms4732 KiB
33Wrong answer8ms4728 KiB
subtask50/20
34Accepted3ms4728 KiB
35Accepted3ms4728 KiB
36Wrong answer8ms4736 KiB
37Wrong answer8ms4736 KiB
38Wrong answer8ms4736 KiB
39Wrong answer8ms4732 KiB
40Wrong answer8ms4860 KiB
41Wrong answer8ms5076 KiB
42Wrong answer8ms5192 KiB
subtask60/30
43Time limit exceeded250ms5060 KiB
44Time limit exceeded248ms5172 KiB
45Wrong answer115ms5152 KiB
46Wrong answer37ms5156 KiB
47Wrong answer16ms5160 KiB
48Wrong answer13ms5156 KiB
49Wrong answer9ms5180 KiB
50Wrong answer8ms5168 KiB
51Wrong answer8ms5168 KiB
52Time limit exceeded300ms5024 KiB
53Time limit exceeded263ms5024 KiB
54Wrong answer115ms5156 KiB
55Wrong answer37ms5296 KiB
56Wrong answer16ms5280 KiB
57Wrong answer13ms5168 KiB
58Wrong answer9ms5268 KiB
59Wrong answer8ms5268 KiB
60Wrong answer8ms5268 KiB