Problem Statement
Time limit: 4 seconds.
Pirates Alice, Bob and their captain Cindy are dividing some loot. The loot consists of N items, numbered from 0 to N-1. Item i has the value loot[i] dubloons.
Cindy has two goals: She wants to reward her crew as much as possible, but at the same time she wants to prevent disputes among them.
There is only one way to prevent disputes: Alice and Bob must get items with the exact same value.
Return a String of length N. For each i, character i should be 'A', 'B', or 'C': the first letter of the name of the person who should get item i. The total value of Alice's items must be equal to the total value of Bob's items, and this value must be as large as possible.
Definition
- Class:
- ThreeWaySplit
- Method:
- split
- Parameters:
- int[]
- Returns:
- String
- Method signature:
- String split(int[] loot)
- (be sure your method is public)
Notes
- Any optimal solution will be accepted.
Constraints
- loot will contain between 1 and 24 elements, inclusive.
- Each element of loot will be between 1 and 10^9, inclusive.
Examples
{4, 7, 53}Returns: "CCC"
The only way to give Alice and Bob items with the same value is to give them nothing at all.{1, 1, 1, 4, 1}Returns: "BBBAB"
Alice and Bob may get a different number of items, only their total value must be equal. Here, Cindy can split all the loot between her two crew members. The example return value is the only optimal solution for this test case.{47, 47, 47}Returns: "CBA"
In the optimal solution each pirate gets one of these three items. As order does not matter, there are six optimal return values: all permutations of the string "ABC".{1, 2, 3, 4, 5, 6}Returns: "CBBABA"
There are several ways how to give 10 to Alice, 10 to Bob and 1 to Cindy. This is clearly optimal.