Woburn Challenge 2018-19 Round 4 - Junior Division
Billy, the king of video games, has received exclusive early access to play the upcoming action role-playing game Diablo Immortal! He's found that it truly revolutionizes the Diablo series, not only by moving to the superior gaming environment of a mobile phone, but by introducing a new system for managing the player's item inventory.
Billy has or more items which he'd like his character to carry around, each of which has a certain size which indicates how many inventory slots it takes up. There are size- items (which take up inventory slot each), size- items, and size- items .
The character isn't allowed to carry all of these items around directly, as that would be unrealistic. Instead, they must be packed into knapsacks. Each knapsack has inventory slots, meaning that it can fit or more items as long as the sum of their sizes is at most . Each item must be packed entirely into a single knapsack.
The character may carry any number of knapsacks, but each one must be purchased through an in-game microtransaction, so Billy would prefer to use as few as possible. Help him determine the minimum number of knapsacks required to fit all of the items!
Subtasks
In test cases worth 16/28 of the points, .
Input Specification
The first and only line of input consists of three space-separated integers, , , and .
Output Specification
Output a single integer, the minimum number of knapsacks required.
Sample Input 1
1 1 1
Sample Output 1
2
Sample Input 2
100 0 0
Sample Output 2
34
Sample Explanation
In the first case, Billy can fill one knapsack with both the size- and the size- items, and a second knapsack with the size- item.
In the second case, Billy can fill knapsacks with size- items each, and pack the single leftover size- item into a th knapsack.
Comments