PEG Test – Oct 3rd, 2014
Problem F: Change
After Korra's decision to leave the spirit world portals permanently open in support of having human and spirits live in unity, Korra, Tenzin, and friends have decided to change the world once again. The harmonic convergence has gifted many people in the world with the power of airbending. Alas, people cannot control it. So, after around a hundred years after their destruction, it's finally time for the air nation to be rebuilt.
However, the evil Red Lotus group consisting of Zaheer, Gazan, Ming-Hua, and P'Li has managed to take the group of new age airbenders hostage. Each of the four Red Lotus members has held an equal number of people hostages at different places in the temple. To save them, Team Avatar, consisting of Korra, Mako, Bolin, Asami, Lin, and Opal have closed in on the temple. Now, the team has to make some strategic decisions to save as many hostages as possible. Korra has to decide which members of the team (including herself) has to take on which members of the Red Lotus.
Zaheer, Gazan, Ming-Hua, and P'Li have strengths of Z, G, MH, and P (1 ≤ Z, G, MH, P ≤ 106) respectively. Korra, Mako, Bolin, Asami, Lin, and Opal have strengths of K, M, B, A, L, and O (1 ≤ K, M, B, A, L, O ≤ 106), respectively. Multiple people of Team Avatar may be assigned to the same Red Lotus member. The winner of a battle will be the side with the strictly larger total strength level. When more than one Team Avatar member is assigned to the same fight, their total strength will be the sum of the strengths of all members assigned.
Given the strengths of everybody, Korra would like to know the maximum number of battles they can win (between 0 and 4) if she assigned optimally.
Line 1: Four integers Z, G, MH, and P, representing the strengths of members of the Red Lotus.
Line 2: Six integers K, M, B, A, L, and O, representing the strengths of members of Team Avatar.
A single integer representing the maximum number of battles that can be won (0, 1, 2, 3, or 4) if Korra deploys Team Avatar members optimally.
25 15 20 25 20 10 10 5 15 15
One possible way is by assigning:
Korra to Gazan (20 > 15)
Mako, Bolin and Asami to Ming-Hua (10 + 10 + 5 > 20), and
Lin and Opal to P'Li (15 + 15 > 25).
C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3