4991 2023. 04. 08 15:46:44 TomaSajt Házszámok cpp17 Elfogadva 100/100 4ms 5560 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 Összpont Teszt Verdikt Idő Memória
subtask1 0/0
1 Elfogadva 3ms 1824 KiB
2 Elfogadva 3ms 2208 KiB
3 Elfogadva 4ms 2572 KiB
subtask2 25/25
4 Elfogadva 3ms 2460 KiB
5 Elfogadva 3ms 2672 KiB
6 Elfogadva 3ms 2880 KiB
7 Elfogadva 3ms 3272 KiB
8 Elfogadva 3ms 3224 KiB
9 Elfogadva 3ms 3404 KiB
10 Elfogadva 3ms 3316 KiB
11 Elfogadva 4ms 3512 KiB
12 Elfogadva 3ms 3384 KiB
13 Elfogadva 3ms 3716 KiB
14 Elfogadva 3ms 3708 KiB
15 Elfogadva 3ms 3684 KiB
16 Elfogadva 3ms 3604 KiB
17 Elfogadva 3ms 3988 KiB
18 Elfogadva 3ms 3932 KiB
19 Elfogadva 3ms 4264 KiB
subtask3 10/10
20 Elfogadva 4ms 4320 KiB
21 Elfogadva 4ms 4640 KiB
22 Elfogadva 4ms 4812 KiB
23 Elfogadva 3ms 4468 KiB
24 Elfogadva 4ms 4772 KiB
subtask4 15/15
25 Elfogadva 4ms 4780 KiB
26 Elfogadva 4ms 4716 KiB
27 Elfogadva 4ms 4664 KiB
28 Elfogadva 4ms 4788 KiB
29 Elfogadva 4ms 4788 KiB
30 Elfogadva 3ms 4528 KiB
31 Elfogadva 4ms 4888 KiB
32 Elfogadva 4ms 4912 KiB
33 Elfogadva 4ms 4812 KiB
subtask5 20/20
34 Elfogadva 3ms 4608 KiB
35 Elfogadva 3ms 4872 KiB
36 Elfogadva 4ms 5032 KiB
37 Elfogadva 4ms 5084 KiB
38 Elfogadva 4ms 5092 KiB
39 Elfogadva 4ms 5208 KiB
40 Elfogadva 4ms 5040 KiB
41 Elfogadva 4ms 5020 KiB
42 Elfogadva 4ms 5116 KiB
subtask6 30/30
43 Elfogadva 4ms 5376 KiB
44 Elfogadva 4ms 5560 KiB
45 Elfogadva 4ms 5296 KiB
46 Elfogadva 4ms 5348 KiB
47 Elfogadva 4ms 5348 KiB
48 Elfogadva 4ms 5252 KiB
49 Elfogadva 3ms 5072 KiB
50 Elfogadva 4ms 5232 KiB
51 Elfogadva 4ms 5240 KiB
52 Elfogadva 2ms 4940 KiB
53 Elfogadva 4ms 5244 KiB
54 Elfogadva 4ms 5208 KiB
55 Elfogadva 4ms 5140 KiB
56 Elfogadva 4ms 5244 KiB
57 Elfogadva 4ms 5288 KiB
58 Elfogadva 4ms 5552 KiB
59 Elfogadva 4ms 5240 KiB
60 Elfogadva 4ms 5344 KiB