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 ≤ 10⁶) 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 ≤ 10⁶), 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.

Input Format

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.

Output Format

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.

Sample Input

25 15 20 25
20 10 10 5 15 15

Sample Output

3

Explanation

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).

All Submissions
Best Solutions

Point Value: 7
Time Limit: 2.00s
Memory Limit: 16M
Added: Oct 06, 2014
Authors: Alex, frenzybenzy

Languages Allowed:
C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3

Comments (Search)