4993 2023. 04. 08 15:59:24 TomaSajt Házszámok cpp17 Elfogadva 100/100 4ms 5552 KiB 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

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

int main() {
  cin >> base;
  vector<ll> budget(base);
  for (auto &b : budget)
    cin >> b;
  auto is_enough = [&](ll n) {
    for (int d = 0; d < base; d++) {
      if (num_of_digits_upto(d, n) > budget[d])
        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 2204 KiB
3 Elfogadva 4ms 2496 KiB
subtask2 25/25
4 Elfogadva 3ms 2328 KiB
5 Elfogadva 3ms 2460 KiB
6 Elfogadva 3ms 2672 KiB
7 Elfogadva 3ms 2800 KiB
8 Elfogadva 3ms 3052 KiB
9 Elfogadva 3ms 3108 KiB
10 Elfogadva 3ms 3120 KiB
11 Elfogadva 4ms 3308 KiB
12 Elfogadva 3ms 3372 KiB
13 Elfogadva 3ms 3400 KiB
14 Elfogadva 3ms 3796 KiB
15 Elfogadva 3ms 3680 KiB
16 Elfogadva 3ms 3532 KiB
17 Elfogadva 3ms 3580 KiB
18 Elfogadva 3ms 3480 KiB
19 Elfogadva 3ms 3540 KiB
subtask3 10/10
20 Elfogadva 4ms 3764 KiB
21 Elfogadva 4ms 3964 KiB
22 Elfogadva 4ms 4300 KiB
23 Elfogadva 3ms 3972 KiB
24 Elfogadva 4ms 4488 KiB
subtask4 15/15
25 Elfogadva 4ms 4364 KiB
26 Elfogadva 4ms 4392 KiB
27 Elfogadva 4ms 4336 KiB
28 Elfogadva 4ms 4460 KiB
29 Elfogadva 4ms 4372 KiB
30 Elfogadva 3ms 4112 KiB
31 Elfogadva 4ms 4372 KiB
32 Elfogadva 4ms 4404 KiB
33 Elfogadva 4ms 4600 KiB
subtask5 20/20
34 Elfogadva 3ms 4348 KiB
35 Elfogadva 3ms 4412 KiB
36 Elfogadva 4ms 4504 KiB
37 Elfogadva 4ms 4648 KiB
38 Elfogadva 4ms 4884 KiB
39 Elfogadva 4ms 4728 KiB
40 Elfogadva 4ms 4776 KiB
41 Elfogadva 4ms 5072 KiB
42 Elfogadva 4ms 5060 KiB
subtask6 30/30
43 Elfogadva 4ms 5084 KiB
44 Elfogadva 4ms 5104 KiB
45 Elfogadva 4ms 4936 KiB
46 Elfogadva 4ms 5092 KiB
47 Elfogadva 4ms 5112 KiB
48 Elfogadva 4ms 5184 KiB
49 Elfogadva 3ms 5100 KiB
50 Elfogadva 4ms 5224 KiB
51 Elfogadva 4ms 5420 KiB
52 Elfogadva 3ms 4956 KiB
53 Elfogadva 4ms 5268 KiB
54 Elfogadva 4ms 5236 KiB
55 Elfogadva 4ms 5284 KiB
56 Elfogadva 4ms 5252 KiB
57 Elfogadva 4ms 5280 KiB
58 Elfogadva 4ms 5552 KiB
59 Elfogadva 4ms 5228 KiB
60 Elfogadva 4ms 5240 KiB