Problem D
Rule N
A cellular automaton is an infinite one-dimensional array of cells. Each cell in the array has one of two states, $0$ or $1$, but the state of the cell may change over the course of an iterative process. At each iteration, each cell will take on a new state by applying a transition rule that operates on the state of the cell and the state of its two neighbouring cells. The state of a cell and its two neighbours is called a “pattern.” Observe that there are eight possible patterns: $111$, $110$, $101$, $100$, $011$, $010$, $001$, and $000$.
The transition rule is specified by a nonnegative integer, $N$, less than $256$. The indices of the nonzero digits of the $8\textrm{-bit}$ binary representation of $N$ specify which patterns will result in a cell having $1$ as its new state after applying the transition rule. Conversely, the indices of the zero digits in the $8\textrm{-bit}$ binary representation of $N$ (including leading zeroes) specify which patterns will result in a cell having $0$ as its new state after applying the transition rule. In particular, the least significant digit of the $8\textrm{-bit}$ binary representation of $N$ defines the new state for the pattern $000$, the second least significant digit defines the new state for the pattern $001$, the third least significant digit defines the new state for the pattern $010$, etc.
For example, Rule $158$ (where $158=10011110_2$) has the following transitions.
|
Pattern |
$111$ |
$110$ |
$101$ |
$100$ |
$011$ |
$010$ |
$001$ |
$000$ |
|
Next State |
$1$ |
$0$ |
$0$ |
$1$ |
$1$ |
$1$ |
$1$ |
$0$ |
When a transition rule is applied, it is applied to all cells simultaneously and the state changes are instantaneous.
Given a rule, $N$, a number of iterations, $R$, and the current states of a contiguous section of $L$ cells of a cellular automaton, compute the states of the cells in that section in each of the next $R$ iterations of the transition rule being applied. It is assumed that each of the infinitely many cells in the cellular automaton that are not in the given section are initially in the $0$ state.
Input
The input consists of two lines. The first line consists of three integers, $N$, $L$, and $R$, where $0\leq N \leq 255$, $1\leq L \leq 100$, and $1\leq R \leq 100$. The next line is a sequence of $L$ binary digits giving the initial states of the section of cells in the cellular automaton.
Output
Output $R$ lines, representing the states of the cells in the given section of the cellular automaton in each of the first $R$ iterations of applying transition rule $N$.
| Sample Input 1 | Sample Output 1 |
|---|---|
158 7 6 1101000 |
1001100 0111010 0110011 1101110 1001100 0111011 |
| Sample Input 2 | Sample Output 2 |
|---|---|
90 51 32 000000000000000000000000010000000000000000000000000 |
000000000000000000000000101000000000000000000000000 000000000000000000000001000100000000000000000000000 000000000000000000000010101010000000000000000000000 000000000000000000000100000001000000000000000000000 000000000000000000001010000010100000000000000000000 000000000000000000010001000100010000000000000000000 000000000000000000101010101010101000000000000000000 000000000000000001000000000000000100000000000000000 000000000000000010100000000000001010000000000000000 000000000000000100010000000000010001000000000000000 000000000000001010101000000000101010100000000000000 000000000000010000000100000001000000010000000000000 000000000000101000001010000010100000101000000000000 000000000001000100010001000100010001000100000000000 000000000010101010101010101010101010101010000000000 000000000100000000000000000000000000000001000000000 000000001010000000000000000000000000000010100000000 000000010001000000000000000000000000000100010000000 000000101010100000000000000000000000001010101000000 000001000000010000000000000000000000010000000100000 000010100000101000000000000000000000101000001010000 000100010001000100000000000000000001000100010001000 001010101010101010000000000000000010101010101010100 010000000000000001000000000000000100000000000000010 101000000000000010100000000000001010000000000000101 000100000000000100010000000000010001000000000001000 101010000000001010101000000000101010100000000010101 000001000000010000000100000001000000010000000100000 000010100000101000001010000010100000101000001010000 000100010001000100010001000100010001000100010001000 101010101010101010101010101010101010101010101010101 000000000000000000000000000000000000000000000000000 |
