New Year's '16 P6 - Cake Balancing - Olympiads Online Judge

New Year's '16 P6 - Cake Balancing

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$ $L$ items on the left side of his scale and $R$ $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$ $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$ $1 \leq W \leq 10^{5}$ .

Subtask 1 [20%]

$1 \le L, R \le 3$ $1 \leq L, R \leq 3$

Subtask 2 [80%]

$1 \le L, R \le 10$ $1 \leq L, R \leq 10$

Input Specification

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

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

The third line of input will contain $R$ $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

Copy

2 2 2
1 2
2 1

Sample Output 1

Copy

Explanation for Sample Output 1

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

Sample Input 2

Copy

3 2 2
1 1 1
1 2

Sample Output 2

Copy

Explanation for Sample Output 2

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

Sample Input 3

Copy

2 4 3
1 3
1 1 1 1

Sample Output 3

Copy

Sample Input 4

Copy

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

Copy

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.