Problem Statement
You have a stove and P pancake pans. The stove has enough heaters to use all pans at the same time.
You want to make N pancakes. Each pancake must be cooked for exactly two minutes: one minute from one side and then one minute from the other side.
We will measure the time in minutes since you start cooking. During each minute, each pan must either be unused or it must contain one of the pancakes. If a pan contains a pancake, the bottom side of the pancake is being cooked.
We will assume that at the beginning/end of each minute you can instantly perform all the necessary actions: getting some pancakes into pans, taking some pancakes out of pans, and flipping some pancakes over (either in the same pan or into a different pan).
Produce one possible schedule to cook all N pancakes in as few minutes as possible.
Return the schedule as a
Any valid cooking schedule that minimizes the number of minutes needed will be accepted.
Definition
- Class:
- Pancakes
- Method:
- makePancakes
- Parameters:
- int, int
- Returns:
- String[]
- Method signature:
- String[] makePancakes(int N, int P)
- (be sure your method is public)
Constraints
- N will be between 1 and 26, inclusive.
- P will be between 1 and 26, inclusive.
Examples
1
3
Returns: {"A--", "-a-" }
N = 1 means we want a single pancake. P = 3 means we have three pans. The preparation will take two minutes, because it's not possible to cook the pancake from both sides at the same time. Having more than one pan does not help us. Two of the three pans will remain unused each minute. In the example output we used a different pan during the second minute. This is allowed but not necessary. E.g., {"--a", "--A"} is another valid output for this test case, and in that output we use the same pan for both sides of the pancake.
3
1
Returns: {"A", "c", "B", "C", "a", "b" }
We want three pancakes and we only have a single pan. This time the cooking will clearly take us six minutes. Note that the order in which we cook does not matter. In particular, it is not necessary to cook both sides of a pancake immediately one after another. A pancake can sit and wait with just one side cooked for arbitrarily many minutes.
5
4
Returns: {"bA-e", "ECad", "-BcD" }
Given four pans, a naive solution needs four minutes to prepare five pancakes: cook four of them from one side, then cook them from the other side, and in the next two minutes do the same with the fifth pancake. However, if we are smart and schedule everything properly, it is possible to prepare five pancakes in only three minutes.
1
1
Returns: {"A", "a" }
1
17
Returns: {"A----------------", "a----------------" }
2
1
Returns: {"A", "B", "a", "b" }
2
2
Returns: {"AB", "ab" }
2
3
Returns: {"AB-", "ab-" }
3
2
Returns: {"AB", "Ca", "bc" }
4
1
Returns: {"A", "B", "C", "D", "a", "b", "c", "d" }
4
2
Returns: {"AB", "CD", "ab", "cd" }
4
3
Returns: {"ABC", "Dab", "cd-" }
5
1
Returns: {"A", "B", "C", "D", "E", "a", "b", "c", "d", "e" }
5
2
Returns: {"AB", "CD", "Ea", "bc", "de" }
5
3
Returns: {"ABC", "DEa", "bcd", "e--" }
5
4
Returns: {"bA-e", "ECad", "-BcD" }
6
1
Returns: {"A", "B", "C", "D", "E", "F", "a", "b", "c", "d", "e", "f" }
6
2
Returns: {"AB", "CD", "EF", "ab", "cd", "ef" }
6
3
Returns: {"ABC", "DEF", "abc", "def" }
6
4
Returns: {"ABCD", "EFab", "cdef" }
6
5
Returns: {"ABCDE", "Fabcd", "ef---" }
7
1
Returns: {"A", "B", "C", "D", "E", "F", "G", "a", "b", "c", "d", "e", "f", "g" }
7
2
Returns: {"AB", "CD", "EF", "Ga", "bc", "de", "fg" }
7
3
Returns: {"ABC", "DEF", "Gab", "cde", "fg-" }
7
4
Returns: {"ABCD", "EFGa", "bcde", "fg--" }
7
5
Returns: {"ABCDE", "FGabc", "defg-" }
7
6
Returns: {"ABCDEF", "Gabcde", "fg----" }
7
7
Returns: {"ABCDEFG", "abcdefg" }
7
17
Returns: {"ABCDEFG----------", "abcdefg----------" }
8
1
Returns: {"A", "B", "C", "D", "E", "F", "G", "H", "a", "b", "c", "d", "e", "f", "g", "h" }
8
2
Returns: {"AB", "CD", "EF", "GH", "ab", "cd", "ef", "gh" }
8
3
Returns: {"ABC", "DEF", "GHa", "bcd", "efg", "h--" }
8
4
Returns: {"ABCD", "EFGH", "abcd", "efgh" }
8
5
Returns: {"ABCDE", "FGHab", "cdefg", "h----" }
8
6
Returns: {"ABCDEF", "GHabcd", "efgh--" }
8
7
Returns: {"ABCDEFG", "Habcdef", "gh-----" }
9
1
Returns: {"A", "B", "C", "D", "E", "F", "G", "H", "I", "a", "b", "c", "d", "e", "f", "g", "h", "i" }
9
2
Returns: {"AB", "CD", "EF", "GH", "Ia", "bc", "de", "fg", "hi" }
9
3
Returns: {"ABC", "DEF", "GHI", "abc", "def", "ghi" }
9
4
Returns: {"ABCD", "EFGH", "Iabc", "defg", "hi--" }
9
5
Returns: {"ABCDE", "FGHIa", "bcdef", "ghi--" }
9
6
Returns: {"ABCDEF", "GHIabc", "defghi" }
9
7
Returns: {"ABCDEFG", "HIabcde", "fghi---" }
9
8
Returns: {"ABCDEFGH", "Iabcdefg", "hi------" }
10
2
Returns: {"AB", "CD", "EF", "GH", "IJ", "ab", "cd", "ef", "gh", "ij" }
10
5
Returns: {"ABCDE", "FGHIJ", "abcde", "fghij" }
10
6
Returns: {"ABCDEF", "GHIJab", "cdefgh", "ij----" }
11
3
Returns: {"ABC", "DEF", "GHI", "JKa", "bcd", "efg", "hij", "k--" }
11
7
Returns: {"ABCDEFG", "HIJKabc", "defghij", "k------" }
11
8
Returns: {"ABCDEFGH", "IJKabcde", "fghijk--" }
11
9
Returns: {"ABCDEFGHI", "JKabcdefg", "hijk-----" }
13
7
Returns: {"ABCDEFG", "HIJKLMa", "bcdefgh", "ijklm--" }
16
4
Returns: {"ABCD", "EFGH", "IJKL", "MNOP", "abcd", "efgh", "ijkl", "mnop" }
16
8
Returns: {"ABCDEFGH", "IJKLMNOP", "abcdefgh", "ijklmnop" }
17
9
Returns: {"ABCDEFGHI", "JKLMNOPQa", "bcdefghij", "klmnopq--" }
17
11
Returns: {"ABCDEFGHIJK", "LMNOPQabcde", "fghijklmnop", "q----------" }
17
12
Returns: {"ABCDEFGHIJKL", "MNOPQabcdefg", "hijklmnopq--" }
18
4
Returns: {"ABCD", "EFGH", "IJKL", "MNOP", "QRab", "cdef", "ghij", "klmn", "opqr" }
18
18
Returns: {"ABCDEFGHIJKLMNOPQR", "abcdefghijklmnopqr" }
19
13
Returns: {"ABCDEFGHIJKLM", "NOPQRSabcdefg", "hijklmnopqrs-" }
20
4
Returns: {"ABCD", "EFGH", "IJKL", "MNOP", "QRST", "abcd", "efgh", "ijkl", "mnop", "qrst" }
20
9
Returns: {"ABCDEFGHI", "JKLMNOPQR", "STabcdefg", "hijklmnop", "qrst-----" }
20
18
Returns: {"ABCDEFGHIJKLMNOPQR", "STabcdefghijklmnop", "qrst--------------" }
21
3
Returns: {"ABC", "DEF", "GHI", "JKL", "MNO", "PQR", "STU", "abc", "def", "ghi", "jkl", "mno", "pqr", "stu" }
21
10
Returns: {"ABCDEFGHIJ", "KLMNOPQRST", "Uabcdefghi", "jklmnopqrs", "tu--------" }
21
12
Returns: {"ABCDEFGHIJKL", "MNOPQRSTUabc", "defghijklmno", "pqrstu------" }
21
18
Returns: {"ABCDEFGHIJKLMNOPQR", "STUabcdefghijklmno", "pqrstu------------" }
21
19
Returns: {"ABCDEFGHIJKLMNOPQRS", "TUabcdefghijklmnopq", "rstu---------------" }
22
13
Returns: {"ABCDEFGHIJKLM", "NOPQRSTUVabcd", "efghijklmnopq", "rstuv--------" }
22
17
Returns: {"ABCDEFGHIJKLMNOPQ", "RSTUVabcdefghijkl", "mnopqrstuv-------" }
23
8
Returns: {"ABCDEFGH", "IJKLMNOP", "QRSTUVWa", "bcdefghi", "jklmnopq", "rstuvw--" }
23
18
Returns: {"ABCDEFGHIJKLMNOPQR", "STUVWabcdefghijklm", "nopqrstuvw--------" }
23
25
Returns: {"ABCDEFGHIJKLMNOPQRSTUVW--", "abcdefghijklmnopqrstuvw--" }
24
8
Returns: {"ABCDEFGH", "IJKLMNOP", "QRSTUVWX", "abcdefgh", "ijklmnop", "qrstuvwx" }
24
19
Returns: {"ABCDEFGHIJKLMNOPQRS", "TUVWXabcdefghijklmn", "opqrstuvwx---------" }
25
24
Returns: {"ABCDEFGHIJKLMNOPQRSTUVWX", "Yabcdefghijklmnopqrstuvw", "xy----------------------" }
26
1
Returns: {"A", "B", "C", "D", "E", "F", "G", "H", "I", "J", "K", "L", "M", "N", "O", "P", "Q", "R", "S", "T", "U", "V", "W", "X", "Y", "Z", "a", "b", "c", "d", "e", "f", "g", "h", "i", "j", "k", "l", "m", "n", "o", "p", "q", "r", "s", "t", "u", "v", "w", "x", "y", "z" }
26
2
Returns: {"AB", "CD", "EF", "GH", "IJ", "KL", "MN", "OP", "QR", "ST", "UV", "WX", "YZ", "ab", "cd", "ef", "gh", "ij", "kl", "mn", "op", "qr", "st", "uv", "wx", "yz" }
26
3
Returns: {"ABC", "DEF", "GHI", "JKL", "MNO", "PQR", "STU", "VWX", "YZa", "bcd", "efg", "hij", "klm", "nop", "qrs", "tuv", "wxy", "z--" }
26
4
Returns: {"ABCD", "EFGH", "IJKL", "MNOP", "QRST", "UVWX", "YZab", "cdef", "ghij", "klmn", "opqr", "stuv", "wxyz" }
26
5
Returns: {"ABCDE", "FGHIJ", "KLMNO", "PQRST", "UVWXY", "Zabcd", "efghi", "jklmn", "opqrs", "tuvwx", "yz---" }
26
6
Returns: {"ABCDEF", "GHIJKL", "MNOPQR", "STUVWX", "YZabcd", "efghij", "klmnop", "qrstuv", "wxyz--" }
26
7
Returns: {"ABCDEFG", "HIJKLMN", "OPQRSTU", "VWXYZab", "cdefghi", "jklmnop", "qrstuvw", "xyz----" }
26
8
Returns: {"ABCDEFGH", "IJKLMNOP", "QRSTUVWX", "YZabcdef", "ghijklmn", "opqrstuv", "wxyz----" }
26
9
Returns: {"ABCDEFGHI", "JKLMNOPQR", "STUVWXYZa", "bcdefghij", "klmnopqrs", "tuvwxyz--" }
26
10
Returns: {"ABCDEFGHIJ", "KLMNOPQRST", "UVWXYZabcd", "efghijklmn", "opqrstuvwx", "yz--------" }
26
11
Returns: {"ABCDEFGHIJK", "LMNOPQRSTUV", "WXYZabcdefg", "hijklmnopqr", "stuvwxyz---" }
26
12
Returns: {"ABCDEFGHIJKL", "MNOPQRSTUVWX", "YZabcdefghij", "klmnopqrstuv", "wxyz--------" }
26
13
Returns: {"ABCDEFGHIJKLM", "NOPQRSTUVWXYZ", "abcdefghijklm", "nopqrstuvwxyz" }
26
14
Returns: {"ABCDEFGHIJKLMN", "OPQRSTUVWXYZab", "cdefghijklmnop", "qrstuvwxyz----" }
26
15
Returns: {"ABCDEFGHIJKLMNO", "PQRSTUVWXYZabcd", "efghijklmnopqrs", "tuvwxyz--------" }
26
16
Returns: {"ABCDEFGHIJKLMNOP", "QRSTUVWXYZabcdef", "ghijklmnopqrstuv", "wxyz------------" }
26
17
Returns: {"ABCDEFGHIJKLMNOPQ", "RSTUVWXYZabcdefgh", "ijklmnopqrstuvwxy", "z----------------" }
26
18
Returns: {"ABCDEFGHIJKLMNOPQR", "STUVWXYZabcdefghij", "klmnopqrstuvwxyz--" }
26
19
Returns: {"ABCDEFGHIJKLMNOPQRS", "TUVWXYZabcdefghijkl", "mnopqrstuvwxyz-----" }
26
20
Returns: {"ABCDEFGHIJKLMNOPQRST", "UVWXYZabcdefghijklmn", "opqrstuvwxyz--------" }
26
21
Returns: {"ABCDEFGHIJKLMNOPQRSTU", "VWXYZabcdefghijklmnop", "qrstuvwxyz-----------" }
26
22
Returns: {"ABCDEFGHIJKLMNOPQRSTUV", "WXYZabcdefghijklmnopqr", "stuvwxyz--------------" }
26
23
Returns: {"ABCDEFGHIJKLMNOPQRSTUVW", "XYZabcdefghijklmnopqrst", "uvwxyz-----------------" }
26
24
Returns: {"ABCDEFGHIJKLMNOPQRSTUVWX", "YZabcdefghijklmnopqrstuv", "wxyz--------------------" }
26
25
Returns: {"ABCDEFGHIJKLMNOPQRSTUVWXY", "Zabcdefghijklmnopqrstuvwx", "yz-----------------------" }
1
2
Returns: {"A-", "a-" }
5
10
Returns: {"ABCDE-----", "abcde-----" }
1
10
Returns: {"A---------", "a---------" }