49892023-04-08 15:43:45TomaSajtHázszámokcpp17Hibás válasz 20/1008ms6084 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 = 60; i >= 0; i--) {
    ll next = curr + (1ll << i);
    if (is_enough(next)) {
      curr = next;
    }
  }
  cout << curr;
}
RészfeladatÖsszpontTesztVerdiktIdőMemória
subtask10/0
1Hibás válasz8ms3084 KiB
2Elfogadva3ms2276 KiB
3Elfogadva4ms2632 KiB
subtask20/25
4Hibás válasz8ms3700 KiB
5Hibás válasz8ms4216 KiB
6Hibás válasz7ms4136 KiB
7Elfogadva3ms3124 KiB
8Elfogadva3ms3300 KiB
9Elfogadva3ms3396 KiB
10Hibás válasz7ms4580 KiB
11Hibás válasz6ms4096 KiB
12Elfogadva3ms3472 KiB
13Elfogadva3ms3900 KiB
14Elfogadva3ms4132 KiB
15Elfogadva3ms4004 KiB
16Elfogadva3ms4064 KiB
17Elfogadva3ms4056 KiB
18Elfogadva3ms4052 KiB
19Elfogadva3ms4196 KiB
subtask30/10
20Hibás válasz7ms5240 KiB
21Hibás válasz7ms5360 KiB
22Hibás válasz8ms5360 KiB
23Hibás válasz7ms5492 KiB
24Hibás válasz7ms5308 KiB
subtask40/15
25Hibás válasz7ms5436 KiB
26Hibás válasz6ms5204 KiB
27Elfogadva4ms4932 KiB
28Elfogadva4ms4932 KiB
29Elfogadva4ms4968 KiB
30Elfogadva3ms4696 KiB
31Elfogadva4ms5072 KiB
32Elfogadva4ms5088 KiB
33Elfogadva4ms5088 KiB
subtask520/20
34Elfogadva3ms4836 KiB
35Elfogadva3ms4928 KiB
36Elfogadva4ms5196 KiB
37Elfogadva4ms5304 KiB
38Elfogadva4ms5212 KiB
39Elfogadva4ms5012 KiB
40Elfogadva4ms5156 KiB
41Elfogadva4ms5036 KiB
42Elfogadva4ms5128 KiB
subtask60/30
43Hibás válasz7ms5876 KiB
44Hibás válasz6ms5556 KiB
45Elfogadva4ms5004 KiB
46Elfogadva4ms5056 KiB
47Elfogadva4ms5316 KiB
48Elfogadva4ms5436 KiB
49Elfogadva4ms5244 KiB
50Elfogadva4ms5256 KiB
51Elfogadva4ms5260 KiB
52Hibás válasz8ms6084 KiB
53Hibás válasz6ms5736 KiB
54Elfogadva4ms5228 KiB
55Elfogadva4ms5544 KiB
56Elfogadva4ms5472 KiB
57Elfogadva4ms5500 KiB
58Elfogadva4ms5752 KiB
59Elfogadva4ms5596 KiB
60Elfogadva4ms5456 KiB