49902023-04-08 15:45:52TomaSajtHázszámokcpp17Hibás válasz 20/1008ms6456 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 = 61; 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álasz8ms3112 KiB
2Elfogadva3ms2260 KiB
3Elfogadva4ms2412 KiB
subtask20/25
4Hibás válasz8ms3516 KiB
5Hibás válasz8ms3616 KiB
6Hibás válasz8ms3828 KiB
7Elfogadva3ms2960 KiB
8Elfogadva3ms3252 KiB
9Elfogadva4ms3384 KiB
10Hibás válasz8ms4672 KiB
11Hibás válasz6ms4284 KiB
12Hibás válasz4ms4064 KiB
13Hibás válasz6ms4408 KiB
14Elfogadva3ms4068 KiB
15Elfogadva3ms3984 KiB
16Elfogadva3ms3916 KiB
17Elfogadva3ms3980 KiB
18Elfogadva3ms4252 KiB
19Elfogadva3ms4200 KiB
subtask30/10
20Hibás válasz8ms5408 KiB
21Hibás válasz8ms5404 KiB
22Hibás válasz8ms5396 KiB
23Hibás válasz8ms5400 KiB
24Hibás válasz8ms5392 KiB
subtask40/15
25Hibás válasz8ms5620 KiB
26Hibás válasz6ms5216 KiB
27Hibás válasz6ms5072 KiB
28Hibás válasz6ms5216 KiB
29Elfogadva4ms5116 KiB
30Elfogadva3ms4812 KiB
31Elfogadva4ms5048 KiB
32Elfogadva4ms5144 KiB
33Elfogadva4ms5152 KiB
subtask520/20
34Elfogadva3ms4944 KiB
35Elfogadva3ms5100 KiB
36Elfogadva4ms5260 KiB
37Elfogadva4ms5228 KiB
38Elfogadva4ms5236 KiB
39Elfogadva4ms5232 KiB
40Elfogadva4ms5280 KiB
41Elfogadva4ms5252 KiB
42Elfogadva4ms5492 KiB
subtask60/30
43Hibás válasz8ms6316 KiB
44Hibás válasz6ms5740 KiB
45Hibás válasz6ms5724 KiB
46Hibás válasz6ms5876 KiB
47Elfogadva4ms5484 KiB
48Elfogadva4ms5500 KiB
49Elfogadva4ms5412 KiB
50Elfogadva4ms5472 KiB
51Elfogadva4ms5536 KiB
52Hibás válasz8ms6456 KiB
53Hibás válasz6ms5948 KiB
54Hibás válasz4ms5924 KiB
55Hibás válasz6ms5936 KiB
56Elfogadva4ms5476 KiB
57Elfogadva4ms5496 KiB
58Elfogadva4ms5752 KiB
59Elfogadva4ms5452 KiB
60Elfogadva4ms5460 KiB