Programming contests

ILBPM9987L Informatikai versenyfeladatok, 2023. ősz

November 17, 2023 8:00 PM – January 31, 2024 11:59 PM

Bankrupt Baker

Wolfgang Puck has an extensive collection of cake recipes. They are separated into different binders depending on the type of cake. Although Wolfgang has restaurant franchises all over the world, he is in a period of hard times and is struggling to afford ingredients for his cakes. What cakes can he create with his small budget?

Input Specification

On the first line, you are given t (1 ≤ t ≤ 100), the number of binders. Each binder begins with title, the name of the binder, then the next line contains m, n, and b (1 ≤ m, n ≤ 100, 1 ≤ b ≤ 106), where b is Wolfgang's budget in dollars. The next m lines are given as “ingredient c” (see sample input), where c (0 ≤ c ≤ 5000) is the price in dollars for one unit of ingredient.

Then follow n recipes. Each recipe begins with name on a line of its own, then the very next line contains k (1 ≤ k ≤ 100). The following k lines are of the form “requirement x” (see sample input), where x is the number of units of the ingredient requirement used in the recipe name.

Output Specification

For each binder, output the name of the binder in uppercase letters, then on separate lines a list of recipes within Wolfgang's budget in increasing order of cost. If no such recipe exists, print “Too expensive!”. If recipes have the same cost, print them in lexicographical order. Print a blank line after each binder.

Sample Input

  1. 2
  2. My Favourite Cheesecake
  3. 8 3 100
  4. sugar 4
  5. water 0
  6. lemonjuice 3
  7. creamcheese 20
  8. vanilla 5
  9. egg 5
  10. cream 10
  11. strawberry 5
  12. Strawberry Whipped Cream
  13. 2
  14. cream 5
  15. strawberry 3
  16. Scrumptious Caramel Topping
  17. 3
  18. sugar 6
  19. water 3
  20. lemonjuice 1
  21. Secret Cheesecake Base
  22. 5
  23. creamcheese 3
  24. sugar 5
  25. vanilla 1
  26. egg 6
  27. cream 1
  28. Million Dollar Cakes
  29. 3 1 999999
  30. costlyflour 500
  31. gold 4500
  32. diamond 5000
  33. Display Cake - Do Not Eat!
  34. 3
  35. costlyflour 100
  36. gold 100
  37. diamond 100
download as text file

Output for Sample Input

  1. MY FAVOURITE CHEESECAKE
  2. Scrumptious Caramel Topping
  3. Strawberry Whipped Cream
  4. MILLION DOLLAR CAKES
  5. Too expensive!
download as text file
University of Debrecen; Faculty of Informatics; v. 03/01/2019