49842023-04-08 15:31:50TomaSajtHázszámokcpp17Időlimit túllépés 0/100300ms5296 KiB
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int base;

// 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;
  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)
    return res + 1;
  return res;
}

int main() {
  cin >> base;
  vector<ll> budget(base);
  for (auto &b : budget)
    cin >> b;
  auto is_enough = [&](int 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 = 30; i >= 0; i--) {
    ll next = curr + (1ll << i);
    if (is_enough(next)) {
      curr = next;
    }
  }
  cout << curr;
}
RészfeladatÖsszpontTesztVerdiktIdőMemória
subtask10/0
1Időlimit túllépés272ms1784 KiB
2Elfogadva3ms2064 KiB
3Hibás válasz13ms2272 KiB
subtask20/25
4Időlimit túllépés261ms1748 KiB
5Időlimit túllépés272ms2656 KiB
6Időlimit túllépés259ms2856 KiB
7Elfogadva3ms2972 KiB
8Elfogadva3ms2936 KiB
9Elfogadva3ms3064 KiB
10Időlimit túllépés300ms3276 KiB
11Elfogadva29ms3392 KiB
12Elfogadva4ms3488 KiB
13Elfogadva3ms3704 KiB
14Elfogadva3ms3912 KiB
15Elfogadva3ms4124 KiB
16Elfogadva3ms4204 KiB
17Elfogadva3ms4236 KiB
18Elfogadva3ms4308 KiB
19Elfogadva3ms4312 KiB
subtask30/10
20Időlimit túllépés280ms4516 KiB
21Időlimit túllépés259ms4632 KiB
22Időlimit túllépés268ms4732 KiB
23Időlimit túllépés247ms4616 KiB
24Időlimit túllépés248ms4496 KiB
subtask40/15
25Időlimit túllépés263ms4628 KiB
26Időlimit túllépés268ms4600 KiB
27Hibás válasz115ms4516 KiB
28Hibás válasz37ms4640 KiB
29Hibás válasz17ms4764 KiB
30Elfogadva3ms4736 KiB
31Hibás válasz9ms4844 KiB
32Hibás válasz8ms4732 KiB
33Hibás válasz8ms4728 KiB
subtask50/20
34Elfogadva3ms4728 KiB
35Elfogadva3ms4728 KiB
36Hibás válasz8ms4736 KiB
37Hibás válasz8ms4736 KiB
38Hibás válasz8ms4736 KiB
39Hibás válasz8ms4732 KiB
40Hibás válasz8ms4860 KiB
41Hibás válasz8ms5076 KiB
42Hibás válasz8ms5192 KiB
subtask60/30
43Időlimit túllépés250ms5060 KiB
44Időlimit túllépés248ms5172 KiB
45Hibás válasz115ms5152 KiB
46Hibás válasz37ms5156 KiB
47Hibás válasz16ms5160 KiB
48Hibás válasz13ms5156 KiB
49Hibás válasz9ms5180 KiB
50Hibás válasz8ms5168 KiB
51Hibás válasz8ms5168 KiB
52Időlimit túllépés300ms5024 KiB
53Időlimit túllépés263ms5024 KiB
54Hibás válasz115ms5156 KiB
55Hibás válasz37ms5296 KiB
56Hibás válasz16ms5280 KiB
57Hibás válasz13ms5168 KiB
58Hibás válasz9ms5268 KiB
59Hibás válasz8ms5268 KiB
60Hibás válasz8ms5268 KiB