fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. /*
  5. PROBLEM (simple)
  6. ----------------
  7. There are n tasks, need[i] work each.
  8.  
  9. In each round:
  10. - choose ONE task to focus -> gains x work
  11. - all other unfinished tasks gain y work  (y < x)
  12.  
  13. Tasks disappear once finished.
  14.  
  15. Goal: minimum number of rounds to finish all tasks.
  16.  
  17. Key trick
  18. ---------
  19. Binary search the answer R (round count).
  20.  
  21. Check if R rounds is enough:
  22. - Every task automatically gets baseline R*y work (because even when not chosen, it gets y).
  23. - If a task still needs more, the only way is choosing it in some rounds.
  24.   Each time we choose it, it gains EXTRA (x-y) beyond baseline.
  25.  
  26. For task i:
  27. rem = max(0, need[i] - R*y)
  28. boostsNeeded = ceil(rem / (x-y))
  29.  
  30. Total boosts across all tasks must be <= R (we only have R rounds to boost tasks).
  31. */
  32.  
  33. static bool canFinish(long long R, long long x, long long y, const vector<long long>& need) {
  34.     long long extra = x - y;           // extra gained when focused
  35.     __int128 totalBoosts = 0;          // use big type to avoid overflow
  36.  
  37.     for (long long w : need) {
  38.         __int128 base = (__int128)R * y;  // baseline progress after R rounds
  39.         if (base >= w) continue;          // already finished without boosting
  40.  
  41.         __int128 rem = w - base;
  42.         // ceil(rem / extra)
  43.         __int128 boosts = (rem + extra - 1) / extra;
  44.         totalBoosts += boosts;
  45.  
  46.         // early stop: if we already need more boosts than rounds exist, not possible
  47.         if (totalBoosts > R) return false;
  48.     }
  49.  
  50.     return totalBoosts <= R;
  51. }
  52.  
  53. int main() {
  54.     ios::sync_with_stdio(false);
  55.     cin.tie(nullptr);
  56.  
  57.     int n;
  58.     long long x, y;
  59.     cin >> n >> x >> y;
  60.  
  61.     vector<long long> need(n);
  62.     for (int i = 0; i < n; i++) cin >> need[i];
  63.  
  64.     // Find a high bound for binary search by doubling
  65.     long long lo = 0, hi = 1;
  66.     while (!canFinish(hi, x, y, need)) hi *= 2;
  67.  
  68.     // Binary search for smallest R that works
  69.     while (lo + 1 < hi) {
  70.         long long mid = lo + (hi - lo) / 2;
  71.         if (canFinish(mid, x, y, need)) hi = mid;
  72.         else lo = mid;
  73.     }
  74.  
  75.     cout << hi << "\n";
  76.     return 0;
  77. }
Success #stdin #stdout 0.01s 5324KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
1
https://ideone.com/OrxYtA
language:
C++14 (gcc 8.3)
created:
2 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!