### 2016 Canadian Computing Competition

## Problem S5: Circle of Life

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 `N` cells. The cells are numbered from 1 to `N` in the order you would expect: that is, cell 1 and cell 2 are adjacent, cell 2 and cell 3 are adjacent, and so on up to cell `N` − 1, which is adjacent to cell `N`. Since the strip is circular, cell 1 is also adjacent to cell `N`.

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 a 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 `T` generations.

### Input Format

The first line will contain two space-separated integers `N` and `T` (3 ≤ `N` ≤ 100 000; 1 ≤ `T` ≤ 10^{15}). The second line will contain a string consisting of exactly `N` characters, representing the initial configuration of the `N` cells. Each character in the string will be either '0' or '1'. The initial state of cell `i` is given by the `i`-th 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, `N` ≤ 15 and `T` ≤ 15.

For an additional 6 of the 15 available marks, `N` ≤ 15.

For an additional 4 of the 15 available marks, `T` ≤ 100 000.

Note that for full marks, solutions will need to handle 64-bit integers. For example

- in C/C++, the type
`long long`

should be used; - in Java, the type
`long`

should be used; - in Pascal, the type
`int64`

should be used.

### Output Format

Output the string of `N` characters representing the final state of the cells, in the same format and order as the input.

### Sample Input 1

7 1 0000001

### Sample Output 1

1000010

### Explanation 1

Cell 1 and cell `N` − 1 are adjacent to cell `N`, and thus are alive after one generation.

### Sample Input 2

5 3 01011

### Sample Output 2

10100

### Explanation 2

After one generation, the configuration becomes `00011`

.

After two generations, the configuration becomes `10111`

.

All Submissions

Best Solutions

**Point Value:** 20 (partial)

**Time Limit:** 2.00s

**Memory Limit:** 16M

**Added:** Feb 22, 2016

**Author:** nullptr

**Languages Allowed:**

C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3

## Comments (Search)

gpfaulton Jan 22, 2017 - 5:46:05 pm UTC bits?jargonon Jan 22, 2017 - 7:21:59 pm UTC Re: bits?