fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. // Speed up I/O
  5. #define fast_io ios::sync_with_stdio(0); cin.tie(0); cout.tie(0)
  6.  
  7. // Typedefs
  8. #define int long long
  9. #define endl '\n'
  10.  
  11. // Constants
  12. const int N = 35;
  13. const int INF = 1e18;
  14.  
  15. // Array to store trash weights
  16. int a[N];
  17.  
  18. void solve() {
  19.     int n, c;
  20.     cin >> n >> c;
  21.  
  22.     for (int i = 0; i < n; ++i)
  23.         cin >> a[i];
  24.  
  25.     sort(a, a + n);  // Sort the trash bags by weight
  26.  
  27.     bool destroyed[N] = {0};  // Keep track of destroyed bags
  28.     int remaining = n;
  29.     int coins = 0;
  30.  
  31.     while (true) {
  32.         int idx = -1;
  33.  
  34.         // Find the heaviest bag ≤ c that is not destroyed
  35.         for (int i = n - 1; i >= 0; --i) {
  36.             if (!destroyed[i] && a[i] <= c) {
  37.                 idx = i;
  38.                 break;
  39.             }
  40.         }
  41.  
  42.         // If no destroyable bag is found, break
  43.         if (idx == -1) break;
  44.  
  45.         destroyed[idx] = true;
  46.         remaining--;
  47.  
  48.         // Double all remaining trash bags
  49.         for (int i = 0; i < n; ++i) {
  50.             if (!destroyed[i]) {
  51.                 if (a[i] <= INF / 2) a[i] *= 2;
  52.                 else a[i] = INF; // Prevent overflow
  53.             }
  54.         }
  55.     }
  56.  
  57.     // Count coins for bags still heavier than c
  58.     for (int i = 0; i < n; ++i) {
  59.         if (!destroyed[i] && a[i] > c)
  60.             coins++;
  61.     }
  62.  
  63.     cout << coins << endl;
  64. }
  65.  
  66. int32_t main() {
  67.     fast_io;
  68.  
  69.     int t;
  70.     cin >> t;
  71.     while (t--) {
  72.         solve();
  73.     }
  74.  
  75.     return 0;
  76. }
  77.  
Success #stdin #stdout 0s 5320KB
comments (?)
stdin
copy 
4
5 10
10 4 15 1 8
3 42
1000000000 1000000000 1000000000
10 30
29 25 2 12 15 42 14 6 16 9
10 1000000
1 1 1 1 1 1 1 1 1 864026633
stdout
copy 
2
3
6
1
https://ideone.com/kZHPHn
language:
C++ (gcc 8.3)
created:
3 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!