49932023-04-08 15:59:24TomaSajtHázszámokcpp17Elfogadva 100/1004ms5552 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ÖsszpontTesztVerdiktIdőMemória
subtask10/0
1Elfogadva3ms1824 KiB
2Elfogadva3ms2204 KiB
3Elfogadva4ms2496 KiB
subtask225/25
4Elfogadva3ms2328 KiB
5Elfogadva3ms2460 KiB
6Elfogadva3ms2672 KiB
7Elfogadva3ms2800 KiB
8Elfogadva3ms3052 KiB
9Elfogadva3ms3108 KiB
10Elfogadva3ms3120 KiB
11Elfogadva4ms3308 KiB
12Elfogadva3ms3372 KiB
13Elfogadva3ms3400 KiB
14Elfogadva3ms3796 KiB
15Elfogadva3ms3680 KiB
16Elfogadva3ms3532 KiB
17Elfogadva3ms3580 KiB
18Elfogadva3ms3480 KiB
19Elfogadva3ms3540 KiB
subtask310/10
20Elfogadva4ms3764 KiB
21Elfogadva4ms3964 KiB
22Elfogadva4ms4300 KiB
23Elfogadva3ms3972 KiB
24Elfogadva4ms4488 KiB
subtask415/15
25Elfogadva4ms4364 KiB
26Elfogadva4ms4392 KiB
27Elfogadva4ms4336 KiB
28Elfogadva4ms4460 KiB
29Elfogadva4ms4372 KiB
30Elfogadva3ms4112 KiB
31Elfogadva4ms4372 KiB
32Elfogadva4ms4404 KiB
33Elfogadva4ms4600 KiB
subtask520/20
34Elfogadva3ms4348 KiB
35Elfogadva3ms4412 KiB
36Elfogadva4ms4504 KiB
37Elfogadva4ms4648 KiB
38Elfogadva4ms4884 KiB
39Elfogadva4ms4728 KiB
40Elfogadva4ms4776 KiB
41Elfogadva4ms5072 KiB
42Elfogadva4ms5060 KiB
subtask630/30
43Elfogadva4ms5084 KiB
44Elfogadva4ms5104 KiB
45Elfogadva4ms4936 KiB
46Elfogadva4ms5092 KiB
47Elfogadva4ms5112 KiB
48Elfogadva4ms5184 KiB
49Elfogadva3ms5100 KiB
50Elfogadva4ms5224 KiB
51Elfogadva4ms5420 KiB
52Elfogadva3ms4956 KiB
53Elfogadva4ms5268 KiB
54Elfogadva4ms5236 KiB
55Elfogadva4ms5284 KiB
56Elfogadva4ms5252 KiB
57Elfogadva4ms5280 KiB
58Elfogadva4ms5552 KiB
59Elfogadva4ms5228 KiB
60Elfogadva4ms5240 KiB