# Mark and Toys

See the original problem on HackerRank.

## Solutions

Since we need to maximize the number of toys, we can sort the array in incresing order of price and pick them as long as the budget is available.

A solution in C++:

  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23  #include #include #include #include using namespace std; int main() { int n, k; cin >> n >> k; vector prices(n); copy_n(istream_iterator(cin), n, begin(prices)); sort(begin(prices), end(prices)); auto toys = 0, cost=0; for (auto i=0u; i

 1 2 3 4 5 6 7 8 9  import Data.List (sort) keepWhileSumBelow k = foldl (\l x -> if sum (x:l) < k then x:l else l) [] maximumToys prices k = length $keepWhileSumBelow k$ sort prices main = do contents <- getContents let (_:k:prices) = map read $words contents print$ maximumToys prices k 
  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  #include #include #include using namespace std; int main() { int n, k; cin >> n >> k; vector prices; for (int i = 0; i < n; i++) { int price_item; cin >> price_item; auto sum = accumulate(begin(prices), end(prices), 0); if (sum + price_item <= k) { prices.push_back(price_item); push_heap(begin(prices), end(prices)); } else if (sum) { pop_heap(begin(prices), end(prices)); auto last = prices.rbegin(); *last = min(*last, price_item); push_heap(begin(prices), end(prices)); } } cout << prices.size() << "\n"; }