fork download
copy 
  1. // We have some coin denominations and unlimited supply of each.
  2. // Goal: find the k-th smallest sum we can make.
  3. // e.g. coins = {3, 5} -> makeable sums are 3, 5, 6, 8, 9, 10, 11, ...
  4. //      so k=4 gives 8.
  5.  
  6. #include <bits/stdc++.h>
  7. using namespace std;
  8.  
  9. int main() {
  10.     ios::sync_with_stdio(false);
  11.     cin.tie(nullptr);
  12.  
  13.     int n;
  14.     long long k;
  15.     cin >> n >> k;
  16.  
  17.     vector<long long> coins(n);
  18.     for (int i = 0; i < n; i++) cin >> coins[i];
  19.  
  20.     // Key idea: if we can already make some sum S,
  21.     // then we can also make S + smallest, S + 2*smallest, etc
  22.     // by just adding more of the smallest coin.
  23.     // So sums naturally fall into groups based on their remainder
  24.     // when divided by smallest. Within each group we only care
  25.     // about the first (smallest) sum we can make — the rest follow on its own.
  26.     long long smallest = *min_element(coins.begin(), coins.end());
  27.  
  28.     // This whole approach is O(smallest) in memory and time,
  29.     // so smallest needs to be reasonably small. Also needs to fit in an int
  30.     // since we use it as array size and loop bound.
  31.     if (smallest > 2'000'000) {
  32.         // too large for the residue graph approach - bail out
  33.         // (remove this check if the problem doesn't allow early exit)
  34.         assert(false);
  35.     }
  36.     int M = (int)smallest;
  37.  
  38.     // For each remainder group, find the smallest sum we can make in it.
  39.     // We model this as a shortest path problem:
  40.     //   - each remainder (0 to M-1) is a node
  41.     //   - adding a coin takes us from one remainder to another
  42.     //   - we want to reach each remainder with the least total value
  43.     // minSum[r] = smallest sum we can make that gives remainder r
  44.     vector<long long> minSum(M, LLONG_MAX);
  45.     minSum[0] = 0; // sum of 0 has remainder 0, that's our starting point
  46.  
  47.     using Entry = pair<long long, int>;
  48.     priority_queue<Entry, vector<Entry>, greater<Entry>> heap; // min-heap
  49.     heap.push({0, 0});
  50.  
  51.     while (!heap.empty()) {
  52.         auto [curSum, rem] = heap.top();
  53.         heap.pop();
  54.  
  55.         // we already found a better sum for this remainder before, skip
  56.         if (curSum != minSum[rem]) continue;
  57.  
  58.         // try adding one of each coin and see if it improves any remainder
  59.         for (long long coin : coins) {
  60.             // reduce coin mod M first — coin could be way bigger than M
  61.             int newRem = (rem + (int)(coin % M)) % M;
  62.  
  63.             // use __int128 for the addition — curSum + coin could overflow long long.
  64.             // only skip if it actually overflows; don't cut at some arbitrary threshold
  65.             // because the real answer might legitimately be that large.
  66.             __int128 newSum128 = (__int128)curSum + coin;
  67.             if (newSum128 > LLONG_MAX) continue;
  68.  
  69.             long long newSum = (long long)newSum128;
  70.  
  71.             if (newSum < minSum[newRem]) {
  72.                 minSum[newRem] = newSum;
  73.                 heap.push({newSum, newRem});
  74.             }
  75.         }
  76.     }
  77.  
  78.     // Now we can quickly count how many sums are makeable up to any limit.
  79.     // For remainder r, the makeable sums are minSum[r], minSum[r]+smallest, minSum[r]+2*smallest, ...
  80.     // so the count up to limit is simply (limit - minSum[r]) / smallest + 1.
  81.     // We add that up for all remainders and subtract 1 to ignore the empty sum (0).
  82.     // Using __int128 because the count can get really large when k is big.
  83.     auto countUpTo = [&](long long limit) -> __int128 {
  84.         __int128 total = 0;
  85.         for (int r = 0; r < M; r++) {
  86.             if (minSum[r] != LLONG_MAX && minSum[r] <= limit) {
  87.                 total += 1 + (limit - minSum[r]) / smallest;
  88.             }
  89.         }
  90.         // minSum[0] is 0, so we counted the empty sum in there — remove it
  91.         if (limit >= 0) total -= 1;
  92.         return total;
  93.     };
  94.  
  95.     // Binary search for the answer.
  96.     // We need the smallest value where countUpTo reaches k.
  97.     // First figure out a safe upper bound by doubling, then narrow it down.
  98.     long long lo = 1;
  99.     long long hi = smallest;
  100.  
  101.     while (countUpTo(hi) < (__int128)k) {
  102.         if (hi > LLONG_MAX / 2) {
  103.             hi = LLONG_MAX;
  104.             break;
  105.         }
  106.         hi *= 2; // keep going until we've gone past the k-th sum
  107.     }
  108.  
  109.     long long ans = hi;
  110.     while (lo <= hi) {
  111.         long long mid = lo + (hi - lo) / 2;
  112.  
  113.         if (countUpTo(mid) >= (__int128)k) {
  114.             ans = mid;
  115.             hi = mid - 1; // mid works, but let's see if something smaller works too
  116.         } else {
  117.             lo = mid + 1; // haven't reached k sums yet, go higher
  118.         }
  119.     }
  120.  
  121.     cout << ans << "\n";
  122.     return 0;
  123. }
Runtime error #stdin #stdout 0.04s 5280KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/nNiZ84
language:
C++14 (gcc 8.3)
created:
79 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!