49912023-04-08 15:46:44TomaSajtHázszámokcpp17Elfogadva 100/1004ms5560 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 = 55; i >= 0; i--) {
    ll next = curr + (1ll << i);
    if (is_enough(next)) {
      curr = next;
    }
  }
  cout << curr;
}
RészfeladatÖsszpontTesztVerdiktIdőMemória
subtask10/0
1Elfogadva3ms1824 KiB
2Elfogadva3ms2208 KiB
3Elfogadva4ms2572 KiB
subtask225/25
4Elfogadva3ms2460 KiB
5Elfogadva3ms2672 KiB
6Elfogadva3ms2880 KiB
7Elfogadva3ms3272 KiB
8Elfogadva3ms3224 KiB
9Elfogadva3ms3404 KiB
10Elfogadva3ms3316 KiB
11Elfogadva4ms3512 KiB
12Elfogadva3ms3384 KiB
13Elfogadva3ms3716 KiB
14Elfogadva3ms3708 KiB
15Elfogadva3ms3684 KiB
16Elfogadva3ms3604 KiB
17Elfogadva3ms3988 KiB
18Elfogadva3ms3932 KiB
19Elfogadva3ms4264 KiB
subtask310/10
20Elfogadva4ms4320 KiB
21Elfogadva4ms4640 KiB
22Elfogadva4ms4812 KiB
23Elfogadva3ms4468 KiB
24Elfogadva4ms4772 KiB
subtask415/15
25Elfogadva4ms4780 KiB
26Elfogadva4ms4716 KiB
27Elfogadva4ms4664 KiB
28Elfogadva4ms4788 KiB
29Elfogadva4ms4788 KiB
30Elfogadva3ms4528 KiB
31Elfogadva4ms4888 KiB
32Elfogadva4ms4912 KiB
33Elfogadva4ms4812 KiB
subtask520/20
34Elfogadva3ms4608 KiB
35Elfogadva3ms4872 KiB
36Elfogadva4ms5032 KiB
37Elfogadva4ms5084 KiB
38Elfogadva4ms5092 KiB
39Elfogadva4ms5208 KiB
40Elfogadva4ms5040 KiB
41Elfogadva4ms5020 KiB
42Elfogadva4ms5116 KiB
subtask630/30
43Elfogadva4ms5376 KiB
44Elfogadva4ms5560 KiB
45Elfogadva4ms5296 KiB
46Elfogadva4ms5348 KiB
47Elfogadva4ms5348 KiB
48Elfogadva4ms5252 KiB
49Elfogadva3ms5072 KiB
50Elfogadva4ms5232 KiB
51Elfogadva4ms5240 KiB
52Elfogadva2ms4940 KiB
53Elfogadva4ms5244 KiB
54Elfogadva4ms5208 KiB
55Elfogadva4ms5140 KiB
56Elfogadva4ms5244 KiB
57Elfogadva4ms5288 KiB
58Elfogadva4ms5552 KiB
59Elfogadva4ms5240 KiB
60Elfogadva4ms5344 KiB