시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
1 초 | 128 MB | 4 | 3 | 3 | 75.000% |
Stephen Wolfram in a “New Kind of Science” describes a special kind of cellular automata. The automata he describes are rather interesting. They consist of rows of blocks, where blocks are either filled or not filled depending on the previous row. To generate a new row of blocks, the automata looks at the preceding row and then follows a pre-set “rule” to either color or not color a square on the output row.
For example the following diagram illustrates the “output” from one of these special kind of cellular automata:
was generated by repeated application of “Rule 254”. The automaton was initialized with an input line that consisted of a single black square. Repeated application of rule 254 to the ouput line from the preceding step generated the black triangle shown above.
For this rule, the top row in each box gives one of eight possible color combinations for a cell (the middle cell) and its two neighbors (the left and right neighbors of the cell). The bottom row in a box specifies the color that the center cell should have on the next step for each of the 8 possible cases.
Given this arrangement, there are 255 different generating rules or automata numbered as follows:
For every line in the input file, your program must determine which (if any) of the 255 possible automata could have generated that particular line when started from the standard starting state. If none of the automata generate the sequence by the given step number, output “NONE”. If more than one automata generated that line, then, you must output all of the automata that generate the line as described below in the output section.
3 WBWBWBWBW 1000 WBWBWBWBBBW 5235 WBWWBWWBBBBWWBBWWWWWWBBWWWBBWWWWWWBBWWBBBBWWBWWBW 5 WBWBDCWBW END OF INPUT
LINE 1 (91,3) LINE 2 (15,8)(158,11)(159,14)(243,8) LINE 3 (129,84)(161,84) LINE 4 NONE