Canadian Computing Competition: 2016 Stage 1, Senior #5
You may have heard of Conway's Game of Life, which is a simple set of rules for cells on a grid that can produce incredibly complex configurations. In this problem we will deal with a simplified version of the game.
There is a one-dimensional circular strip of cells. The cells are numbered from to in the order you would expect: that is, cell and cell are adjacent, cell and cell are adjacent, and so on up to cell , which is adjacent to cell . Since the trip is circular, cell is also adjacent to cell .
Each cell is either alive (represented by a
1) or dead (represented by a
0). The cells change over a number of generations. If exactly one of the cell's neighbours is alive in the current generation, then the cell will be alive in the next generation. Otherwise, the cell will be dead in the next generation.
Given the initial state of the strip, find the state after generations.
The first line will contain two space-separated integers and (). The second line will contain a string consisting of exactly characters, representing the initial configuration of the cells. Each character in the string will be either
1. The initial state of cell is given by the character of the string. The character
1 represents an alive cell and the character
0 represents a dead cell.
- For 1 of the 15 available marks, and .
- For an additional 6 of the 15 available marks, .
- For an additional 4 of the 15 available marks, and .
Note that for full marks, solutions will need to handle 64-bit integers. For example:
- in C/C++, the type
long longshould be used;
- in Java, the type
longshould be used;
- in Pascal, the type
int64should be used.
Output the string of characters representing the final state of the cells, in the same format and order as the input.
Sample Input 1
7 1 0000001
Output for Sample Input 1
Explanation for Output for Sample Input 1
Cell and cell are adjacent to cell , and thus alive after one generation.
Sample Input 2
5 3 01011
Output for Sample Input 2
Explanation for Output for Sample Input 2
After one generation, configuration becomes
After two generations, configuration becomes