New Year's '16 P6 - Cake Balancing

View as PDF

Submit solution

Points: 15 (partial)
Time limit: 1.0s
Memory limit: 128M

Author:
Problem type

Xyene wants to bake two cakes to celebrate the new year. Unfortunately, he does not have proper equipment with which to precisely measure ingredients, but since he'll be baking two identical cakes all he needs to measure are two equal amounts of ingredients. Therefore, he's decided to use a weighing scale to measure the ingredients he'll need.

He's placed L items on the left side of his scale and R on the right, until he had an equal amount (by weight) on both sides. Now, Xyene wants to unload the scale, and begin baking! At any step in his unloading process, he may remove any number of items from one side of the scale. However, if the scale is ever off balance by more than W grams, it will tip over, and all the expensive ingredients on it will fall off!

Xyene wants to unload the scale in such a way that it never loses balance. If he unloads optimally, how many steps will it take for Xyene to completely unload the weighing scale?

Constraints

For all cases, 1 \le W \le 10^5.

Subtask 1 [20%]

1 \le L, R \le 3

Subtask 2 [80%]

1 \le L, R \le 10

Input Specification

The first line of input will contain L, R and W.

The second line of input will contain L space-separated integers representing the weight of the ingredients on the left side of the balance, with the i^{th} representing the weight in grams W_i (1 \le W_i \le W) of the i^{th} ingredient.

The third line of input will contain R space-separated integers representing the right side of the balance, given in the same format as the left side.

Output Specification

A single integer, the number of steps required to unload the balance. Since Xyene was able to load all the ingredients onto the scale, it is guaranteed that there must exist some way to unload the scale with it maintaining balance.

Sample Input 1

2 2 2
1 2
2 1

Sample Output 1

3

Explanation for Sample Output 1

Xyene can start from either side. Starting from the left, he removes 2. Next, he removes [1, 2] from the right side, before removing 1 from the left side.

Sample Input 2

3 2 2
1 1 1
1 2

Sample Output 2

3

Explanation for Sample Output 2

Xyene removes 2 off of the right side, followed by [1, 1, 1] from the left side. Finally, he removes 1 from the right side.

Sample Input 3

2 4 3
1 3
1 1 1 1

Sample Output 3

3

Sample Input 4

10 10 10
1 2 3 4 5 6 7 8 9 10
1 2 3 4 5 6 7 8 9 10

Sample Output 4

7

Comments


  • -1
    sayed_elabady  commented on Jan. 2, 2016, 2:19 p.m.

    Explanation of the forth sample please? i see it should be 8 not 7


    • 8
      awaykened  commented on Jan. 2, 2016, 2:41 p.m.

      first take 10 from left, 10 1 9 from right, 1 9 2 8 from left, 2 8 3 7 from right, 3 7 4 6 from left, 4 5 6 from right, 5 from left.