Problem Statement
A group of N people just reached a river they want to cross. The only means they can use to cross the river is a nearby boat with a single paddle. The boat can carry at most C people. Paddling the boat across the river takes one minute (regardless of how many people are in the boat). Each time the boat goes from one river bank to the other, exactly one person has to paddle. It is not allowed to change the person who paddles while crossing the river.
Get all people across the river as quickly as possible.
Let the strain on a person be the number of times they paddled across the river. Among all shortest schedules, pick any one that minimizes the maximum strain.
Return the schedule as a String[]. Use the first N uppercase English letters to represent the people. For each trip across the river, return a String with the people in the boat, with the person who paddles the boat listed first.
Definition
- Class:
- RowAcross
- Method:
- row
- Parameters:
- int, int
- Returns:
- String[]
- Method signature:
- String[] row(int N, int C)
- (be sure your method is public)
Constraints
- N will be between 1 and 26, inclusive.
- C will be between 2 and 26, inclusive.
Examples
13
4
Returns: {"ABCD", "B", "EFGH", "H", "IJKL", "K", "MBKH" }Four people go to the other side ('A' paddles), then 'B' brings the boat back. The same thing is repeated two more times. After six minutes, we have nine people at the desired bank of the river and four are still on the original bank. These four are 'B', 'H', 'K', and 'M'. Out of them, 'M' is the only person who hasn't paddled yet, so we have them take everyone else to the other side and we are done. Note that the maximum strain for this solution is 1: nobody had to paddle more than once.8
6
Returns: {"ACGHEF", "FAC", "DABCF" }In the returned solution two people ('A' and 'C') make unnecessary trips back and forth, but that does not matter. Three minutes is the optimal time, and the returned solution also clearly minimizes the maximum strain.