Flag signals
Statement
The signal station at a harbor has flags in N colors numbered 1 through N. Every color is stocked generously, so any number of flags can be taken out and used.
The station stands M flagpoles in a row from left to right and makes one signal by hanging one flag on each pole. The same color may be hung on several poles. Ships read the flags in order from the left, so two signals that carry the same colors in different places are different signals.
Write a program that prints every signal the station can make, in lexicographic order. Lexicographic order means that the signal whose left pole carries the smaller flag number comes first, and when those numbers are equal, the signal whose next pole carries the smaller flag number comes first.
For example, suppose flags in N=3 colors are hung on M=2 flagpoles. There are 9 signals that can be made, and listing them in lexicographic order gives the following table.
| Signal | Left pole | Right pole |
|---|---|---|
| 1 | 1 | 1 |
| 2 | 1 | 2 |
| 3 | 1 | 3 |
| 4 | 2 | 1 |
| 5 | 2 | 2 |
| 6 | 2 | 3 |
| 7 | 3 | 1 |
| 8 | 3 | 2 |
| 9 | 3 | 3 |
Compare signal 2 in the table with signal 4. The colors of the flags hung are the same, 1 and 2, but the places they hang in are swapped, so the two are different signals. Both signals are therefore in the table. The same color may also be hung on both poles, as in signal 1 or signal 5.
One more flagpole means that many more signals. With the same N=3 and M=3, the signals run 1 1 1, 1 1 2, 1 1 3, 1 2 1 from the front and end at 3 3 3, as in the following table, and there are 27 of them in all.
| Signal | Left pole | Middle pole | Right pole |
|---|---|---|---|
| 1 | 1 | 1 | 1 |
| 2 | 1 | 1 | 2 |
| 3 | 1 | 1 | 3 |
| 4 | 1 | 2 | 1 |
| 5 | 1 | 2 | 2 |
| 6 | 1 | 2 | 3 |
| 27 | 3 | 3 | 3 |
Each pole can carry any one of the N colors with no restriction, so the number of signals that can be made is N multiplied by itself M times. The number of signals for each N and M is as in the following table.
| N | 2 | 3 | 3 | 4 | 5 | 7 |
|---|---|---|---|---|---|---|
| M | 2 | 2 | 3 | 3 | 4 | 6 |
| Number of signals | 4 | 9 | 27 | 64 | 625 | 117,649 |
Input and Output Examples
Example 1
Input
3 2
Output
1 1 1 2 1 3 2 1 2 2 2 3 3 1 3 2 3 3
Example 2
Input
1 1
Output
1
Example 3
Input
2 2
Output
1 1 1 2 2 1 2 2
Input
The number of flag colors N at the signal station is given first as a natural number. N is a natural number from 1 to 7.
The number of flagpoles M standing in the row then comes on the same line, separated by a space. M is a natural number from 1 to 7, and it is not larger than N, the number of colors.
The input is therefore one line, and that line holds two natural numbers separated by one space.
Output
Print every signal that can be made in lexicographic order, one per line. One line holds the M flag numbers in order starting from the left pole. On top of that, The last three characters of the output are therefore a space, a newline and a newline, in that order. When a line holds more than one value, the values are separated by a single space.
Requirements
- The same color may be hung on several poles
- Signals that carry the same colors in different places are different signals
- Print the signals in lexicographic order
- You must write a program that reads from standard input and writes to standard output
- Trailing spaces at the end of a line and blank lines at the end of the output are ignored when grading
- The languages you can use are Python and JavaScript
- The memory limit is 256MB. The browser does not measure it, it only states it
- The time limit is set by measuring the setter's reference solution on the same runtime
- On this problem you submit code, not a prompt. That code runs in the browser on this device, and all that goes to the server is a fingerprint of the output and the time it took. Whether it is correct is decided by the server. The run time is a number each device reports, so the code and the device details are posted next to it on the leaderboard.
- The output has to match the expected value down to the character. A space inside a line counts the same as any other character.
- There are 14 cases, and 3 of them show the input together with the expected output. The rest are used only when you submit and are not shown on this page.
- You have to pass all 14 cases to solve this.
Examples
3 public cases. Judging also uses hidden cases. You have to pass all 14 cases to solve this.
1 1
1
2 2
1 1 1 2 2 1 2 2
3 2
1 1 1 2 1 3 2 1 2 2 2 3 3 1 3 2 3 3
Solution
Your code runs on this device. Only the fingerprint of the output and the elapsed time go to the server. The server decides whether it is correct.
Submitting requires you to log in. Running against the public cases works without one.
You can test with 3 public cases. Submitting runs the hidden cases too.
People who solved this problem
Nobody yet. You could be the first.