WC '18 Contest 4 J3 - Inventory

View as PDF

Submit solution

Points: 5 (partial)
Time limit: 1.0s
Memory limit: 16M

Problem type
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 1 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 A size-1 items (which take up 1 inventory slot each), B size-2 items, and C size-3 items (0 \le A, B, C \le 1\,000\,000\,000, 1 \le A + B + C \le 1\,000\,000\,000).

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 3 inventory slots, meaning that it can fit 1 or more items as long as the sum of their sizes is at most 3. 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!


In test cases worth 16/28 of the points, A + B + C \le 100.

Input Specification

The first and only line of input consists of three space-separated integers, A, B, and C.

Output Specification

Output a single integer, the minimum number of knapsacks required.

Sample Input 1

1 1 1

Sample Output 1


Sample Input 2

100 0 0

Sample Output 2


Sample Explanation

In the first case, Billy can fill one knapsack with both the size-1 and the size-2 items, and a second knapsack with the size-3 item.

In the second case, Billy can fill 33 knapsacks with 3 size-1 items each, and pack the single leftover size-1 item into a 34th knapsack.


There are no comments at the moment.