Game of Life (Codeforces 1523A)
Tags: Implement, implementation

  William really likes the cellular automaton called "Game of Life" so he decided to make his own version. For simplicity, William decided to define his cellular automaton on an array containing $$$n$$$ cells, with each cell either being alive or dead.Evolution of the array in William's cellular automaton occurs iteratively in the following way:  If the element is dead and it has exactly $$$1$$$ alive neighbor in the current state of the array, then on the next iteration it will become alive. For an element at index $$$i$$$ the neighbors would be elements with indices $$$i - 1$$$ and $$$i + 1$$$. If there is no element at that index, it is considered to be a dead neighbor.  William is a humane person so all alive elements stay alive. Check the note section for examples of the evolution.You are given some initial state of all elements and you need to help William find the state of the array after $$$m$$$ iterations of evolution.

Input: Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 10^3$$$). Description of the test cases follows.The first line of each test case contains two integers $$$n$$$ and $$$m$$$ ($$$2 \le n \le 10^3, 1 \le m \le 10^9$$$), which are the total number of cells in the array and the number of iterations.The second line of each test case contains a string of length $$$n$$$ made up of characters "0" and "1" and defines the initial state of the array. "1" means a cell is alive and "0" means it is dead.It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$10^4$$$.

Output: In each test case output a string of length $$$n$$$, made up of characters "0" and "1"  — the state of the array after $$$m$$$ iterations of evolution.

Note: Sequence of iterations of evolution for the first test case   01000000001  — initial state  11100000011  — first iteration of evolution  11110000111  — second iteration of evolution  11111001111  — third iteration of evolution Sequence of iterations of evolution for the second test case   0110100101  — initial state  1110111101  — first iteration of evolution  1110111101  — second iteration of evolution 

Sample Inputs:
4
11 3
01000000001
10 2
0110100101
5 2
10101
3 100
000

Sample Outputs:
11111001111
1110111101
10101
000

Solution (Python):
for _ in range(int(input())):
    (a, b) = map(int, input().split())
    c = list(input())
    d = []
    for i in range(a):
        if c[i] == '1':
            d.append(i)
    if len(d) == 0:
        print(*c, sep='')
    else:
        if d[0] != 0:
            if b >= d[0]:
                for i in range(d[0]):
                    c[i] = '1'
            else:
                for i in range(d[0] - b, d[0]):
                    c[i] = '1'
        if d[-1] != a - 1:
            if d[-1] + b >= a - 1:
                for i in range(d[-1] + 1, a):
                    c[i] = '1'
            else:
                for i in range(d[-1] + 1, d[-1] + b + 1):
                    c[i] = '1'
        for i in range(len(d) - 1):
            e = d[i + 1] - d[i] - 1
            if e >= 2:
                if 2 * b >= e:
                    for o in range(d[i] + 1, d[i + 1]):
                        c[o] = '1'
                    if e % 2 != 0:
                        c[d[i] + (e + 1) // 2] = '0'
                else:
                    for o in range(d[i] + 1, d[i] + b + 1):
                        c[o] = '1'
                    for o in range(d[i + 1] - b, d[i + 1]):
                        c[o] = '1'
        print(*c, sep='')

Solution (Python):
t = int(input())
for _ in range(t):
    (n, m) = (int(i) for i in input().split())
    s = [int(i) for i in input()]
    (le, ri, res) = (0, 0, s)
    while ri < n:
        while ri < n - 1 and res[ri] == 0:
            ri += 1
        (lo, hi, rem) = (le, ri, min(m, n))
        while rem > 0 and (hi - lo > 2 or res[lo] == 0 or res[hi] == 0):
            if res[lo] == 1:
                res[lo + 1] = 1
                lo += 1
            if res[hi] == 1:
                res[hi - 1] = 1
                hi -= 1
            rem -= 1
        (le, ri) = (ri, ri + 1)
    res = ''.join((str(i) for i in res))
    print(res)

Solution (Python):
for _ in range(int(input())):
    (n, m) = map(int, input().split())
    a = list(input())
    if '1' in a:
        z = 0
        b = ''
        for x in a:
            if x == '1':
                if z:
                    if b:
                        d = min(z // 2, m)
                        b += '1' * d + '0' * (z - d * 2) + '1' * d
                    else:
                        d = min(z, m)
                        b += '0' * (z - d) + '1' * d
                b += '1'
                z = 0
            else:
                z += 1
        d = min(z, m)
        b += '1' * d + '0' * (z - d)
        print(b)
    else:
        print(''.join(a))