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
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.
7
3
Returns: {"ABC", "B", "DBE", "C", "FCG" }
11
11
Returns: {"ABCDEFGHIJK" }
16
9
Returns: {"ABCDEFGHI", "B", "JBKLMNOP" }
15
20
Returns: {"ABCDEFGHIJKLMNO" }
12
12
Returns: {"ABCDEFGHIJKL" }
19
4
Returns: {"ABCD", "B", "EBFG", "C", "HCIJ", "D", "KDLM", "F", "NFOP", "G", "QGRS" }
20
20
Returns: {"ABCDEFGHIJKLMNOPQRST" }
1
6
Returns: {"A" }
3
7
Returns: {"ABC" }
2
5
Returns: {"AB" }
8
5
Returns: {"ABCDE", "B", "FBGH" }
10
8
Returns: {"ABCDEFGH", "B", "IBJ" }
6
7
Returns: {"ABCDEF" }
5
5
Returns: {"ABCDE" }
7
6
Returns: {"ABCDEF", "B", "GB" }
15
11
Returns: {"ABCDEFGHIJK", "B", "LBMNO" }
20
9
Returns: {"ABCDEFGHI", "B", "JBKLMNOPQ", "C", "RCST" }
26
17
Returns: {"ABCDEFGHIJKLMNOPQ", "B", "RBSTUVWXYZ" }
3
2
Returns: {"BA", "A", "CA" }
2
6
Returns: {"AB" }
4
5
Returns: {"ABCD" }
9
3
Returns: {"ABC", "B", "DBE", "C", "FCG", "E", "HEI" }
7
5
Returns: {"ABCDE", "B", "FBG" }
12
11
Returns: {"ABCDEFGHIJK", "B", "LB" }
17
13
Returns: {"ABCDEFGHIJKLM", "B", "NBOPQ" }
15
14
Returns: {"ABCDEFGHIJKLMN", "B", "OB" }
13
10
Returns: {"ABCDEFGHIJ", "B", "KBLM" }
20
14
Returns: {"ABCDEFGHIJKLMN", "B", "OBPQRST" }
18
10
Returns: {"ABCDEFGHIJ", "B", "KBLMNOPQR" }
17
18
Returns: {"ABCDEFGHIJKLMNOPQ" }
1
12
Returns: {"A" }
9
9
Returns: {"ABCDEFGHI" }
16
13
Returns: {"ABCDEFGHIJKLM", "B", "NBOP" }
14
8
Returns: {"ABCDEFGH", "B", "IBJKLMN" }
12
8
Returns: {"ABCDEFGH", "B", "IBJKL" }
17
8
Returns: {"ABCDEFGH", "B", "IBJKLMNO", "C", "PCQ" }
15
13
Returns: {"ABCDEFGHIJKLM", "B", "NBO" }
16
16
Returns: {"ABCDEFGHIJKLMNOP" }
13
13
Returns: {"ABCDEFGHIJKLM" }
20
3
Returns: {"ABC", "B", "DBE", "C", "FCG", "E", "HEI", "G", "JGK", "I", "LIM", "K", "NKO", "M", "PMQ", "O", "ROS", "Q", "TQ" }
25
5
Returns: {"ABCDE", "B", "FBGHI", "C", "JCKLM", "D", "NDOPQ", "E", "RESTU", "G", "VGWXY" }
8
9
Returns: {"ABCDEFGH" }
7
2
Returns: {"AB", "B", "BC", "C", "CD", "D", "DE", "E", "EF", "F", "FG" }
12
2
Returns: {"AB", "B", "BC", "C", "CD", "D", "DE", "E", "EF", "F", "FG", "G", "GH", "H", "HI", "I", "IJ", "J", "JK", "K", "KL" }
11
10
Returns: {"ABCDEFGHIJ", "B", "KB" }
16
10
Returns: {"ABCDEFGHIJ", "B", "KBLMNOP" }
17
11
Returns: {"ABCDEFGHIJK", "B", "LBMNOPQ" }
1
5
Returns: {"A" }
18
16
Returns: {"ABCDEFGHIJKLMNOP", "B", "QBR" }
3
6
Returns: {"ABC" }
2
2
Returns: {"BA" }
10
9
Returns: {"ABCDEFGHI", "B", "JB" }
6
4
Returns: {"ABCD", "B", "EBF" }
5
4
Returns: {"ABCD", "B", "EB" }
14
19
Returns: {"ABCDEFGHIJKLMN" }
11
9
Returns: {"ABCDEFGHI", "B", "JBK" }
15
10
Returns: {"ABCDEFGHIJ", "B", "KBLMNO" }
15
7
Returns: {"ABCDEFG", "B", "HBIJKLM", "C", "NCO" }
23
24
Returns: {"ABCDEFGHIJKLMNOPQRSTUVW" }
3
5
Returns: {"ABC" }
2
7
Returns: {"AB" }
8
3
Returns: {"ABC", "B", "DBE", "C", "FCG", "E", "HE" }
4
6
Returns: {"ABCD" }
10
10
Returns: {"ABCDEFGHIJ" }
9
2
Returns: {"AB", "B", "BC", "C", "CD", "D", "DE", "E", "EF", "F", "FG", "G", "GH", "H", "HI" }
5
7
Returns: {"ABCDE" }
7
4
Returns: {"ABCD", "B", "EBFG" }
14
12
Returns: {"ABCDEFGHIJKL", "B", "MBN" }
12
4
Returns: {"ABCD", "B", "EBFG", "C", "HCIJ", "D", "KDL" }
19
12
Returns: {"ABCDEFGHIJKL", "B", "MBNOPQRS" }
17
12
Returns: {"ABCDEFGHIJKL", "B", "MBNOPQ" }
15
9
Returns: {"ABCDEFGHI", "B", "JBKLMNO" }
24
12
Returns: {"ABCDEFGHIJKL", "B", "MBNOPQRSTUVW", "C", "XC" }
13
9
Returns: {"ABCDEFGHI", "B", "JBKLM" }
25
20
Returns: {"ABCDEFGHIJKLMNOPQRST", "B", "UBVWXY" }
14
3
Returns: {"ABC", "B", "DBE", "C", "FCG", "E", "HEI", "G", "JGK", "I", "LIM", "K", "NK" }
17
17
Returns: {"ABCDEFGHIJKLMNOPQ" }
1
3
Returns: {"A" }
9
8
Returns: {"ABCDEFGH", "B", "IB" }
6
2
Returns: {"AB", "B", "BC", "C", "CD", "D", "DE", "E", "EF" }
16
14
Returns: {"ABCDEFGHIJKLMN", "B", "OBP" }
14
9
Returns: {"ABCDEFGHI", "B", "JBKLMN" }
24
22
Returns: {"ABCDEFGHIJKLMNOPQRSTUV", "B", "WBX" }
12
9
Returns: {"ABCDEFGHI", "B", "JBKL" }
17
15
Returns: {"ABCDEFGHIJKLMNO", "B", "PBQ" }
15
12
Returns: {"ABCDEFGHIJKL", "B", "MBNO" }
13
12
Returns: {"ABCDEFGHIJKL", "B", "MB" }
26
3
Returns: {"ABC", "B", "DBE", "C", "FCG", "E", "HEI", "G", "JGK", "I", "LIM", "K", "NKO", "M", "PMQ", "O", "ROS", "Q", "TQU", "S", "VSW", "U", "XUY", "W", "ZW" }
16
11
Returns: {"ABCDEFGHIJK", "B", "LBMNOP" }
14
10
Returns: {"ABCDEFGHIJ", "B", "KBLMN" }
24
19
Returns: {"ABCDEFGHIJKLMNOPQRS", "B", "TBUVWX" }
13
2
Returns: {"AB", "B", "BC", "C", "CD", "D", "DE", "E", "EF", "F", "FG", "G", "GH", "H", "HI", "I", "IJ", "J", "JK", "K", "KL", "L", "LM" }
17
10
Returns: {"ABCDEFGHIJ", "B", "KBLMNOPQ" }
15
3
Returns: {"ABC", "B", "DBE", "C", "FCG", "E", "HEI", "G", "JGK", "I", "LIM", "K", "NKO" }
25
18
Returns: {"ABCDEFGHIJKLMNOPQR", "B", "SBTUVWXY" }
1
4
Returns: {"A" }
26
9
Returns: {"ABCDEFGHI", "B", "JBKLMNOPQ", "C", "RCSTUVWXY", "D", "ZD" }
18
17
Returns: {"ABCDEFGHIJKLMNOPQ", "B", "RB" }
2
3
Returns: {"AB" }
4
2
Returns: {"AB", "B", "BC", "C", "CD" }
6
5
Returns: {"ABCDE", "B", "FB" }
5
3
Returns: {"ABC", "B", "DBE" }
11
8
Returns: {"ABCDEFGH", "B", "IBJK" }
16
8
Returns: {"ABCDEFGH", "B", "IBJKLMNO", "C", "PC" }
21
10
Returns: {"ABCDEFGHIJ", "B", "KBLMNOPQRS", "C", "TCU" }
1
7
Returns: {"A" }
3
4
Returns: {"ABC" }
2
4
Returns: {"AB" }
8
4
Returns: {"ABCD", "B", "EBFG", "C", "HC" }
4
7
Returns: {"ABCD" }
6
6
Returns: {"ABCDEF" }
5
6
Returns: {"ABCDE" }
7
7
Returns: {"ABCDEFG" }
14
13
Returns: {"ABCDEFGHIJKLM", "B", "NB" }
19
15
Returns: {"ABCDEFGHIJKLMNO", "B", "PBQRS" }
15
8
Returns: {"ABCDEFGH", "B", "IBJKLMNO" }
13
8
Returns: {"ABCDEFGH", "B", "IBJKLM" }
12
16
Returns: {"ABCDEFGHIJKL" }
20
8
Returns: {"ABCDEFGH", "B", "IBJKLMNO", "C", "PCQRST" }
17
16
Returns: {"ABCDEFGHIJKLMNOP", "B", "QB" }
13
21
Returns: {"ABCDEFGHIJKLM" }
21
13
Returns: {"ABCDEFGHIJKLM", "B", "NBOPQRSTU" }
1
2
Returns: {"A" }
26
15
Returns: {"ABCDEFGHIJKLMNO", "B", "PBQRSTUVWXYZ" }
22
2
Returns: {"AB", "B", "BC", "C", "CD", "D", "DE", "E", "EF", "F", "FG", "G", "GH", "H", "HI", "I", "IJ", "J", "JK", "K", "KL", "L", "LM", "M", "MN", "N", "NO", "O", "OP", "P", "PQ", "Q", "QR", "R", "RS", "S", "ST", "T", "TU", "U", "UV" }
3
3
Returns: {"ABC" }
23
11
Returns: {"ABCDEFGHIJK", "B", "LBMNOPQRSTU", "C", "VCW" }
4
4
Returns: {"ABCD" }
6
3
Returns: {"ABC", "B", "DBE", "C", "FC" }
9
17
Returns: {"ABCDEFGHI" }
16
15
Returns: {"ABCDEFGHIJKLMNO", "B", "PB" }
14
14
Returns: {"ABCDEFGHIJKLMN" }
12
10
Returns: {"ABCDEFGHIJ", "B", "KBL" }
19
10
Returns: {"ABCDEFGHIJ", "B", "KBLMNOPQRS" }
17
14
Returns: {"ABCDEFGHIJKLMN", "B", "OBPQ" }
15
15
Returns: {"ABCDEFGHIJKLMNO" }
22
21
Returns: {"ABCDEFGHIJKLMNOPQRSTU", "B", "VB" }
13
11
Returns: {"ABCDEFGHIJK", "B", "LBM" }
12
21
Returns: {"ABCDEFGHIJKL" }
18
13
Returns: {"ABCDEFGHIJKLM", "B", "NBOPQR" }
16
12
Returns: {"ABCDEFGHIJKL", "B", "MBNOP" }
14
11
Returns: {"ABCDEFGHIJK", "B", "LBMN" }
17
9
Returns: {"ABCDEFGHI", "B", "JBKLMNOPQ" }
24
7
Returns: {"ABCDEFG", "B", "HBIJKLM", "C", "NCOPQRS", "D", "TDUVWX" }
8
8
Returns: {"ABCDEFGH" }
22
8
Returns: {"ABCDEFGH", "B", "IBJKLMNO", "C", "PCQRSTUV" }
4
3
Returns: {"ABC", "B", "DB" }
2
15
Returns: {"AB" }
5
2
Returns: {"AB", "B", "BC", "C", "CD", "D", "DE" }
10
2
Returns: {"AB", "B", "BC", "C", "CD", "D", "DE", "E", "EF", "F", "FG", "G", "GH", "H", "HI", "I", "IJ" }
25
3
Returns: {"ABC", "B", "DBE", "C", "FCG", "E", "HEI", "G", "JGK", "I", "LIM", "K", "NKO", "M", "PMQ", "O", "ROS", "Q", "TQU", "S", "VSW", "U", "XUY" }
24
3
Returns: {"ABC", "B", "DBE", "C", "FCG", "E", "HEI", "G", "JGK", "I", "LIM", "K", "NKO", "M", "PMQ", "O", "ROS", "Q", "TQU", "S", "VSW", "U", "XU" }
23
3
Returns: {"ABC", "B", "DBE", "C", "FCG", "E", "HEI", "G", "JGK", "I", "LIM", "K", "NKO", "M", "PMQ", "O", "ROS", "Q", "TQU", "S", "VSW" }
22
3
Returns: {"ABC", "B", "DBE", "C", "FCG", "E", "HEI", "G", "JGK", "I", "LIM", "K", "NKO", "M", "PMQ", "O", "ROS", "Q", "TQU", "S", "VS" }
21
3
Returns: {"ABC", "B", "DBE", "C", "FCG", "E", "HEI", "G", "JGK", "I", "LIM", "K", "NKO", "M", "PMQ", "O", "ROS", "Q", "TQU" }
19
3
Returns: {"ABC", "B", "DBE", "C", "FCG", "E", "HEI", "G", "JGK", "I", "LIM", "K", "NKO", "M", "PMQ", "O", "ROS" }
23
4
Returns: {"ABCD", "B", "EBFG", "C", "HCIJ", "D", "KDLM", "F", "NFOP", "G", "QGRS", "I", "TIUV", "J", "WJ" }
14
4
Returns: {"ABCD", "B", "EBFG", "C", "HCIJ", "D", "KDLM", "F", "NF" }
11
2
Returns: {"AB", "B", "BC", "C", "CD", "D", "DE", "E", "EF", "F", "FG", "G", "GH", "H", "HI", "I", "IJ", "J", "JK" }
13
4
Returns: {"ABCD", "B", "EFGH", "H", "IJKL", "K", "MBKH" }
21
2
Returns: {"AB", "B", "BC", "C", "CD", "D", "DE", "E", "EF", "F", "FG", "G", "GH", "H", "HI", "I", "IJ", "J", "JK", "K", "KL", "L", "LM", "M", "MN", "N", "NO", "O", "OP", "P", "PQ", "Q", "QR", "R", "RS", "S", "ST", "T", "TU" }
16
2
Returns: {"AB", "B", "BC", "C", "CD", "D", "DE", "E", "EF", "F", "FG", "G", "GH", "H", "HI", "I", "IJ", "J", "JK", "K", "KL", "L", "LM", "M", "MN", "N", "NO", "O", "OP" }
18
4
Returns: {"ABCD", "B", "EBFG", "C", "HCIJ", "D", "KDLM", "F", "NFOP", "G", "QGR" }
26
2
Returns: {"AB", "B", "BC", "C", "CD", "D", "DE", "E", "EF", "F", "FG", "G", "GH", "H", "HI", "I", "IJ", "J", "JK", "K", "KL", "L", "LM", "M", "MN", "N", "NO", "O", "OP", "P", "PQ", "Q", "QR", "R", "RS", "S", "ST", "T", "TU", "U", "UV", "V", "VW", "W", "WX", "X", "XY", "Y", "YZ" }
24
4
Returns: {"ABCD", "B", "EBFG", "C", "HCIJ", "D", "KDLM", "F", "NFOP", "G", "QGRS", "I", "TIUV", "J", "WJX" }
23
3
Returns: {"ABC", "B", "DBE", "C", "FCG", "E", "HEI", "G", "JGK", "I", "LIM", "K", "NKO", "M", "PMQ", "O", "ROS", "Q", "TQU", "S", "VSW" }
17
3
Returns: {"ABC", "B", "DBE", "C", "FCG", "E", "HEI", "G", "JGK", "I", "LIM", "K", "NKO", "M", "PMQ" }
9
4
Returns: {"ABCD", "B", "EBFG", "C", "HCI" }
10
3
Returns: {"ABC", "B", "DBE", "C", "FCG", "E", "HEI", "G", "JG" }
25
4
Returns: {"ABCD", "B", "EBFG", "C", "HCIJ", "D", "KDLM", "F", "NFOP", "G", "QGRS", "I", "TIUV", "J", "WJXY" }
13
3
Returns: {"ABC", "B", "DBE", "C", "FCG", "E", "HEI", "G", "JGK", "I", "LIM" }
16
3
Returns: {"ABC", "B", "DBE", "C", "FCG", "E", "HEI", "G", "JGK", "I", "LIM", "K", "NKO", "M", "PM" }
23
2
Returns: {"AB", "B", "BC", "C", "CD", "D", "DE", "E", "EF", "F", "FG", "G", "GH", "H", "HI", "I", "IJ", "J", "JK", "K", "KL", "L", "LM", "M", "MN", "N", "NO", "O", "OP", "P", "PQ", "Q", "QR", "R", "RS", "S", "ST", "T", "TU", "U", "UV", "V", "VW" }
17
2
Returns: {"AB", "B", "BC", "C", "CD", "D", "DE", "E", "EF", "F", "FG", "G", "GH", "H", "HI", "I", "IJ", "J", "JK", "K", "KL", "L", "LM", "M", "MN", "N", "NO", "O", "OP", "P", "PQ" }
19
3
Returns: {"ABC", "B", "DBE", "C", "FCG", "E", "HEI", "G", "JGK", "I", "LIM", "K", "NKO", "M", "PMQ", "O", "ROS" }
15
4
Returns: {"ABCD", "B", "EBFG", "C", "HCIJ", "D", "KDLM", "F", "NFO" }
20
4
Returns: {"ABCD", "B", "EBFG", "C", "HCIJ", "D", "KDLM", "F", "NFOP", "G", "QGRS", "I", "TI" }
12
3
Returns: {"ABC", "B", "DBE", "C", "FCG", "E", "HEI", "G", "JGK", "I", "LI" }
22
3
Returns: {"ABC", "B", "DBE", "C", "FCG", "E", "HEI", "G", "JGK", "I", "LIM", "K", "NKO", "M", "PMQ", "O", "ROS", "Q", "TQU", "S", "VS" }
11
4
Returns: {"ABCD", "B", "EBFG", "C", "HCIJ", "D", "KD" }
8
2
Returns: {"AB", "B", "BC", "C", "CD", "D", "DE", "E", "EF", "F", "FG", "G", "GH" }
10
4
Returns: {"ABCD", "B", "EBFG", "C", "HCIJ" }
18
2
Returns: {"AB", "B", "BC", "C", "CD", "D", "DE", "E", "EF", "F", "FG", "G", "GH", "H", "HI", "I", "IJ", "J", "JK", "K", "KL", "L", "LM", "M", "MN", "N", "NO", "O", "OP", "P", "PQ", "Q", "QR" }
16
4
Returns: {"ABCD", "B", "EBFG", "C", "HCIJ", "D", "KDLM", "F", "NFOP" }
22
4
Returns: {"ABCD", "B", "EBFG", "C", "HCIJ", "D", "KDLM", "F", "NFOP", "G", "QGRS", "I", "TIUV" }
19
2
Returns: {"AB", "B", "BC", "C", "CD", "D", "DE", "E", "EF", "F", "FG", "G", "GH", "H", "HI", "I", "IJ", "J", "JK", "K", "KL", "L", "LM", "M", "MN", "N", "NO", "O", "OP", "P", "PQ", "Q", "QR", "R", "RS" }
21
4
Returns: {"ABCD", "B", "EBFG", "C", "HCIJ", "D", "KDLM", "F", "NFOP", "G", "QGRS", "I", "TIU" }
24
2
Returns: {"AB", "B", "BC", "C", "CD", "D", "DE", "E", "EF", "F", "FG", "G", "GH", "H", "HI", "I", "IJ", "J", "JK", "K", "KL", "L", "LM", "M", "MN", "N", "NO", "O", "OP", "P", "PQ", "Q", "QR", "R", "RS", "S", "ST", "T", "TU", "U", "UV", "V", "VW", "W", "WX" }
26
4
Returns: {"ABCD", "B", "EBFG", "C", "HCIJ", "D", "KDLM", "F", "NFOP", "G", "QGRS", "I", "TIUV", "J", "WJXY", "L", "ZL" }
14
2
Returns: {"AB", "B", "BC", "C", "CD", "D", "DE", "E", "EF", "F", "FG", "G", "GH", "H", "HI", "I", "IJ", "J", "JK", "K", "KL", "L", "LM", "M", "MN" }
25
3
Returns: {"ABC", "B", "DBE", "C", "FCG", "E", "HEI", "G", "JGK", "I", "LIM", "K", "NKO", "M", "PMQ", "O", "ROS", "Q", "TQU", "S", "VSW", "U", "XUY" }
17
4
Returns: {"ABCD", "B", "EBFG", "C", "HCIJ", "D", "KDLM", "F", "NFOP", "G", "QG" }
18
3
Returns: {"ABC", "B", "DBE", "C", "FCG", "E", "HEI", "G", "JGK", "I", "LIM", "K", "NKO", "M", "PMQ", "O", "RO" }
15
2
Returns: {"AB", "B", "BC", "C", "CD", "D", "DE", "E", "EF", "F", "FG", "G", "GH", "H", "HI", "I", "IJ", "J", "JK", "K", "KL", "L", "LM", "M", "MN", "N", "NO" }
20
2
Returns: {"AB", "B", "BC", "C", "CD", "D", "DE", "E", "EF", "F", "FG", "G", "GH", "H", "HI", "I", "IJ", "J", "JK", "K", "KL", "L", "LM", "M", "MN", "N", "NO", "O", "OP", "P", "PQ", "Q", "QR", "R", "RS", "S", "ST" }
11
3
Returns: {"ABC", "B", "DBE", "C", "FCG", "E", "HEI", "G", "JGK" }
21
3
Returns: {"ABC", "B", "DBE", "C", "FCG", "E", "HEI", "G", "JGK", "I", "LIM", "K", "NKO", "M", "PMQ", "O", "ROS", "Q", "TQU" }
24
3
Returns: {"ABC", "B", "DBE", "C", "FCG", "E", "HEI", "G", "JGK", "I", "LIM", "K", "NKO", "M", "PMQ", "O", "ROS", "Q", "TQU", "S", "VSW", "U", "XU" }
25
2
Returns: {"AB", "B", "BC", "C", "CD", "D", "DE", "E", "EF", "F", "FG", "G", "GH", "H", "HI", "I", "IJ", "J", "JK", "K", "KL", "L", "LM", "M", "MN", "N", "NO", "O", "OP", "P", "PQ", "Q", "QR", "R", "RS", "S", "ST", "T", "TU", "U", "UV", "V", "VW", "W", "WX", "X", "XY" }
5
10
Returns: {"ABCDE" }