Exam Plan

Solutions Since we want to maximize the number of chapters, we just sort the array and pick the first chapters which sum is less than or equal to \( t \). Here is a C++ implementation: 1 2 3 4 5 6 7 8 9 10 11 12 13 int n, t; cin >> n >> t; vector<int> v(n); copy_n(istream_iterator<int>(cin), n, begin(v)); sort(begin(v), end(v)); auto cnt = 0; for (auto i=0; i<n; ++i) { if (t-v[i] < 0) break; t -= v[i]; cnt++; } cout << cnt; The solution is \( O(N \cdot logN) \). [Read More]

Jesse and Cookies

Solutions This is a typical job for a priority queue. Basically, we maintain the least sweet cookie on top: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 priority_queue<int, deque<int>, greater<int>> cookies; while (N--) { cin >> tmp; cookies.push(tmp); } auto cnt = 0; while (cookies.size()>1 && cookies.top()<K) { const auto c1 = cookies.top(); cookies.pop(); const auto c2 = cookies.top(); cookies.pop(); cookies.push(c1 + 2*c2); ++cnt; } cout << ((cookies. [Read More]