-
Notifications
You must be signed in to change notification settings - Fork 1
Expand file tree
/
Copy pathjesse-and-cookies.cpp
More file actions
45 lines (39 loc) · 1.05 KB
/
jesse-and-cookies.cpp
File metadata and controls
45 lines (39 loc) · 1.05 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
// Author: btjanaka (Bryon Tjanaka)
// Problem: (HackerRank) jesse-and-cookies
// Title: Jesse and Cookies
// Link: https://www.hackerrank.com/challenges/jesse-and-cookies/problem
// Idea: Throw everything in a heap and keep doing the operation described.
// Note that runtime is n log n because the number of cookies decreases by one
// each time we do the operation (since we combine two cookies into one).
// Difficulty: easy
// Tags: heap, priority-queue
#include <bits/stdc++.h>
using namespace std;
int main() {
cin.tie(NULL);
ios_base::sync_with_stdio(false);
int n, k, x;
cin >> n >> k;
priority_queue<int, vector<int>, greater<int>> pq;
for (int i = 0; i < n; ++i) {
cin >> x;
pq.push(x);
}
int ops = 0;
while (!pq.empty() && pq.top() < k) {
int a = pq.top();
pq.pop();
if (pq.empty()) break; // Might run out in the middle.
int b = pq.top();
pq.pop();
pq.push(a + 2 * b);
++ops;
}
if (pq.empty()) {
// No cookies.
cout << -1 << endl;
} else {
cout << ops << endl;
}
return 0;
}