Problem:


Problem B: Independent Research

Problem

ことを建て前に、計画倒れがいかにして発生するかを生徒に体験させるため、長期休暇に課される試練のことである。
その中でも、自由研究とは、長期休暇の課題の中でも最も過酷な課題である。
「自由研究」と言う名に反して強制である場合が多く、研究しないという選択肢は存在しない。
絵、工作、生き物観察など、様々な分野の課題があり、とりあえず僕は、生き物観察を自由研究のテーマとした。

-->

僕は夏休みの自由研究のテーマとして、生き物観察を選択し、生き物観察キットを購入した。

この生き物は3次元グリッド状の空間を好んで生息する。
各セルには最大1匹までしか入れない。
周囲の環境に合わせ1日が経過するごとに誕生と死滅を繰り返す。

誕生と死滅の条件は、セルに隣接する生き物の数に依存する。
ここで、あるセルに生き物が隣接するとは、あるセルと生き物が生息しているもう一つのセルが面、辺、または点を共有していることを言う。
誕生と死滅のルールは次のようになる。

生き物が生息していないセルにおいて、隣接する生き物の数が
 ai (1 ≤ i ≤ M1 ) 匹であるような
 i がある場合、そのセルに生き物が誕生する。

生き物が生息しているセルにおいて、隣接する生き物の数が
 bj (1 ≤ j ≤ M2 ) 匹であるような
 j がない場合、そのセルの生き物は死滅する。

今回購入した飼育箱はセルの数が5*5*5である立方体の飼育箱だ。
この飼育箱ではこの生き物はどのような振る舞いをするのだろうか…？　とても楽しみである。

〜数日後〜

とりあえず、飼育してみたが…　

毎日観察するなんて時間がかかるし、僕にはめんどくさくてやる気がおきない。

そうだ、コンピューターとプログラムを使ってシミュレートしよう。

Input

入力は複数のデータセットからなる。
各データセットは以下のフォーマットで与えられる。

N
(z = 0 の飼育箱の状態)
(空行)
(z = 1 の飼育箱の状態)
(空行)
(z = 2 の飼育箱の状態)
(空行)
(z = 3 の飼育箱の状態)
(空行)
(z = 4 の飼育箱の状態)
(空行)
M1 a1 a2 …　aM1
M2 b1 b2 …　bM2

最初にシミュレートする日数 N が与えられる。

次に飼育箱の初期状態の情報が与えられる。これは5つの5*5の2次元グリッドで与えられる。

各2次元グリッドは0と1から成り立ち、1は生き物がいることを示し、0は何もいないことを示す。

例えば、 z  = 0のセルの状態の2次元グリッドの4行2列目の値が1だった場合、飼育箱の座標(1, 3, 0)の位置に生き物がいることを表す。

次に、整数 M1 が与えられ、そのあとに M1 個の数字 ai が与えられる。

次に、整数 M2 が与えられ、そのあとに M2 個の数字 bj が与えられる。

入力の終わりは N = 0で表される。

Constraints

入力は以下の条件を満たす。

1 ≤ N  ≤ 100

 x,y,z  ≤ 5

0 ≤ grid(x,y,z)  ≤ 1

-->

0 ≤ M1 , M2  ≤ 27

0 ≤ ai , bj  ≤ 26 
(1 ≤ i ≤ M1 , 1 ≤ j ≤ M2 )

任意の i , j (1 ≤ i < j ≤ M1 ) 
において、 ai &ne; aj 

任意の i , j (1 ≤ i < j ≤ M2 ) 
において、 bi &ne; bj 

Output

各データセットに対し、 N 日経過後の状態を出力せよ。

出力は以下のフォーマットに従う。

Case (テストケースの番号):
(z = 0 の飼育箱の状態)
(空行)
(z = 1 の飼育箱の状態)
(空行)
(z = 2 の飼育箱の状態)
(空行)
(z = 3 の飼育箱の状態)
(空行)
(z = 4 の飼育箱の状態)

1行目にテストケース番号を出力し、次の行から N 日経過後の状態として、5*5の2次元グリッドを5つ出力せよ。

各テストケースの出力間には空行を出力しなさい。

Sample Input

5
00000
01010
00000
00100
00000

00000
01010
00000
01010
00000

00000
00100
00000
01010
00000

00000
01010
00000
00100
00000

00000
00000
00100
00000
00000

1 2
2 3 4
4
01110
00100
00100
00100
01110

01110
10001
10000
10001
01110

11111
10001
11111
10000
10000

01110
10001
10000
10001
01110

00000
00000
00000
00000
00000

2 3 4
1 2
100
00100
01010
01110
10001
10001

01110
00100
00100
00100
01110

00000
00000
00000
00000
00000

11111
00010
00100
01000
11111

10001
10001
10001
10001
01110

5 1 3 5 7 9
5 0 2 4 6 8
0

Sample Output

Case 1:
00000
00000
01010
01110
10101

00000
10001
00000
00000
00000

00000
00000
11111
10001
00000

00000
00000
00000
00000
01010

00000
00000
01110
00100
11111

Case 2:
00010
10110
00000
11000
10000

00001
00000
10101
00010
00100

10001
00000
00000
00000
00010

01110
10001
00000
00001
10000

00000
00000
00111
01001
01000

Case 3:
00000
00000
00000
00000
00000

00000
00000
00000
00000
00000

00000
00000
00000
00000
00000

00000
00000
00000
00000
00000

00000
00000
00000
00000
00000



Sample input:
5
00000
01010
00000
00100
00000

00000
01010
00000
01010
00000

00000
00100
00000
01010
00000

00000
01010
00000
00100
00000

00000
00000
00100
00000
00000

1 2
2 3 4
4
01110
00100
00100
00100
01110

01110
10001
10000
10001
01110

11111
10001
11111
10000
10000

01110
10001
10000
10001
01110

00000
00000
00000
00000
00000

2 3 4
1 2
100
00100
01010
01110
10001
10001

01110
00100
00100
00100
01110

00000
00000
00000
00000
00000

11111
00010
00100
01000
11111

10001
10001
10001
10001
01110

5 1 3 5 7 9
5 0 2 4 6 8
0


Sample output:
Case 1:
00000
00000
01010
01110
10101

00000
10001
00000
00000
00000

00000
00000
11111
10001
00000

00000
00000
00000
00000
01010

00000
00000
01110
00100
11111

Case 2:
00010
10110
00000
11000
10000

00001
00000
10101
00010
00100

10001
00000
00000
00000
00010

01110
10001
00000
00001
10000

00000
00000
00111
01001
01000

Case 3:
00000
00000
00000
00000
00000

00000
00000
00000
00000
00000

00000
00000
00000
00000
00000

00000
00000
00000
00000
00000

00000
00000
00000
00000
00000

Submission status: Accepted

Solution code:
# AOJ 1510 Independent Research
# Python3 2018.7.13 bal4u

mv = [[-1,-1,-1],[-1,-1,0],[-1,-1,1],[-1,0,-1],[-1,0,0],[-1,0,1],[-1,1,-1],[-1,1,0],[-1,1,1],
      [0,-1,-1],[0,-1,0],[0,-1,1],[0,0,-1],[0,0,1],[0,1,-1],[0,1,0],[0,1,1],
      [1,-1,-1],[1,-1,0],[1,-1,1],[1,0,-1],[1,0,0],[1,0,1],[1,1,-1],[1,1,0],[1,1,1]]
				
cno = 0
arr = [[[[0 for x in range(5)] for y in range(5)] for z in range(5)] for k in range(2)]
while True:
	n = int(input())
	if n == 0: break
	for z in range(5):
		if z > 0: input()
		for y in range(5): arr[0][z][y] = list(map(int, input()))
	a, b = [0]*27, [0]*27
	ts = input()
	if len(ts) == 0: ts = input()
	ts = list(map(int, ts.split()))
	for t in ts[1:]: a[t] = 1
	ts = list(map(int, input().split()))
	for t in ts[1:]: b[t] = 1
	for j in range(n):
		for z in range(5):
			for y in range(5):
				for x in range(5):
					s = 0;
					for i in range(26):
						xx, yy, zz = x+mv[i][0], y+mv[i][1], z+mv[i][2]
						if xx >= 0 and xx < 5 and yy >= 0 and yy < 5 and zz >= 0 and zz < 5:
							s += arr[j&1][zz][yy][xx] & 1
					if arr[j&1][z][y][x] & 1: arr[1-(j&1)][z][y][x] = b[s]
					else: arr[1-(j&1)][z][y][x] = a[s]
	if cno: print()
	cno += 1
	print("Case ", cno, ":", sep='')
	for z in range(5):
		if z > 0: print()
		for y in range(5): print(*arr[n&1][z][y], sep='')

Submission status: Accepted

Solution code:
from collections import defaultdict
t = 1
def change(s):
    s_ = [[[s[z][y][x] for x in range(7)] for y in range(7)] for z in range(7)]
    for z in range(1,6):
        for y in range(1,6):
            for x in range(1,6):
                su = -s[z][y][x]
                for i in range(z-1,z+2):
                    for j in range(y-1,y+2):
                        for k in range(x-1,x+2):
                            su += s[i][j][k]
                if not s[z][y][x]:
                    if fa[su]:
                        s_[z][y][x] = 1
                else:
                    if not fb[su]:
                        s_[z][y][x] = 0
    return s_

while 1:
    n = int(input())
    if n == 0:
        break
    if t != 1:
        print()
    s = [[[0]*7 for i in range(7)]]
    for i in range(5):
        s.append([[0]*7]+[[0]+[int(x) for x in input()]+[0] for j in range(5)]+[[0]*7])
        input()
    s.append([[0]*7 for i in range(7)])
    a = [int(x) for x in input().split()[1:]]
    b = [int(x) for x in input().split()[1:]]
    fa = defaultdict(lambda : 0)
    fb = defaultdict(lambda : 0)
    for i in a:
        fa[i] = 1
    for i in b:
        fb[i] = 1
    for i in range(n):
        s = change(s)
    print("Case",str(t)+":")
    for z in range(1,6):
        for y in range(1,6):
            for x in range(1,6):
                print(s[z][y][x],end = "")
            print()
        if z < 5:
            print()
    t += 1

Submission status: Accepted

Solution code:
class Simulator:
    def __init__(self, exist_mp, cnt_mp, birth_num, death_num, limit):
        self.exist_mp = exist_mp
        self.cnt_mp = cnt_mp
        self.birth_num = birth_num
        self.death_num = death_num
        self.birth_list = []
        self.death_list = []
        self.limit = limit

    def check(self):
        self.birth_list = []
        self.death_list = []
        for z in range(1, 6):
            for y in range(1, 6):
                for x in range(1, 6):
                    if not self.exist_mp[z][y][x] and\
                       self.cnt_mp[z][y][x] in self.birth_num:
                        self.birth_list.append((x, y, z))
                    if self.exist_mp[z][y][x] and\
                       self.cnt_mp[z][y][x] not in self.death_num:
                        self.death_list.append((x, y, z))

    def birth(self):
        for x, y, z in self.birth_list:
            self.exist_mp[z][y][x] = 1
            self.cnt_mp[z][y][x] -= 1
            for nz in (z - 1, z, z + 1):
                for ny in (y - 1, y, y + 1):
                    for nx in (x - 1, x, x + 1):
                        self.cnt_mp[nz][ny][nx] += 1

    def death(self):
        for x, y, z in self.death_list:
            self.exist_mp[z][y][x] = 0
            self.cnt_mp[z][y][x] += 1
            for nz in (z - 1, z, z + 1):
                for ny in (y - 1, y, y + 1):
                    for nx in (x - 1, x, x + 1):
                        self.cnt_mp[nz][ny][nx] -= 1

    def run(self):
        while self.limit > 0:
            self.check()
            self.birth()
            self.death()
            self.limit -= 1

    def print_mp(self):
        for z in range(1, 6):
            for y in range(1, 6):
                print(*self.exist_mp[z][y][1:6],sep="")
            if z != 5:print()


case = 1
while True:
    n = int(input())
    if n == 0:break
    if case != 1:print()
    exist_mp = [[[0] * 7 for _ in range(7)]]
    for z in range(5):
        mp = [[0] * 7]
        for _ in range(5):
            mp.append([0] + list(map(int, list(input()))) + [0])
        mp.append([0] * 7)
        exist_mp.append(mp)
        if z != 4:input()
    exist_mp.append([[0] * 7 for _ in range(7)])

    cnt_mp = [[[0] * 7 for _ in range(7)] for _ in range(7)]
    for z in range(1, 6):
        for y in range(1, 6):
            for x in range(1, 6):
                if exist_mp[z][y][x]:
                    cnt_mp[z][y][x] -= 1
                    for nz in (z - 1, z, z + 1):
                        for ny in (y - 1, y, y + 1):
                            for nx in (x - 1, x, x + 1):
                                cnt_mp[nz][ny][nx] += 1
    s = input()
    if s == "":
        birth_num = set(list(map(int, input().split()))[1:])
        death_num = set(list(map(int, input().split()))[1:])
    else:
        birth_num = set(list(map(int, s.split()))[1:])
        death_num = set(list(map(int, input().split()))[1:])
    simulator = Simulator(exist_mp, cnt_mp, birth_num, death_num, n)
    simulator.run()
    print("Case {}:".format(case))
    simulator.print_mp()
    case += 1

Submission status: Runtime Error

Solution code:
# AOJ 1510 Independent Research
# Python3 2018.7.13 bal4u

mv = [[-1,-1,-1],[-1,-1,0],[-1,-1,1],[-1,0,-1],[-1,0,0],[-1,0,1],[-1,1,-1],[-1,1,0],[-1,1,1],
      [0,-1,-1],[0,-1,0],[0,-1,1],[0,0,-1],[0,0,1],[0,1,-1],[0,1,0],[0,1,1],
      [1,-1,-1],[1,-1,0],[1,-1,1],[1,0,-1],[1,0,0],[1,0,1],[1,1,-1],[1,1,0],[1,1,1]]
				
cno = 0
arr = [[[[0 for x in range(5)] for y in range(5)] for z in range(5)] for k in range(2)]
while True:
	n = int(input())
	if n == 0: break
	for z in range(5):
		for y in range(5): arr[0][z][y] = list(map(int, input()))
		input()
	a, b = [0]*27, [0]*27
	ts = list(map(int, input().split()))
	for t in ts[1:]: a[t] = 1
	ts = list(map(int, input().split()))
	for t in ts[1:]: b[t] = 1
	for j in range(n):
		for z in range(5):
			for y in range(5):
				for x in range(5):
					s = 0;
					for i in range(26):
						xx, yy, zz = x+mv[i][0], y+mv[i][1], z+mv[i][2]
						if xx >= 0 and xx < 5 and yy >= 0 and yy < 5 and zz >= 0 and zz < 5:
							s += arr[j&1][zz][yy][xx] & 1
					if arr[j&1][z][y][x] & 1: arr[1-(j&1)][z][y][x] = b[s]
					else: arr[1-(j&1)][z][y][x] = a[s]
	if cno: print()
	cno += 1
	print("Case ", cno, ":", sep='')
	for z in range(5):
		if z > 0: print()
		for y in range(5): print(*arr[n&1][z][y], sep='')

Submission status: Runtime Error

Solution code:
# AOJ 1510 Independent Research
# Python3 2018.7.13 bal4u

mv = [[-1,-1,-1],[-1,-1,0],[-1,-1,1],[-1,0,-1],[-1,0,0],[-1,0,1],[-1,1,-1],[-1,1,0],[-1,1,1],
      [0,-1,-1],[0,-1,0],[0,-1,1],[0,0,-1],[0,0,1],[0,1,-1],[0,1,0],[0,1,1],
      [1,-1,-1],[1,-1,0],[1,-1,1],[1,0,-1],[1,0,0],[1,0,1],[1,1,-1],[1,1,0],[1,1,1]]
				
cno = 0
arr = [[[[0 for x in range(5)] for y in range(5)] for z in range(5)] for k in range(2)]
while True:
	n = int(input())
	if n == 0: break
	for z in range(5):
		if z > 0: input()
		for y in range(5): arr[0][z][y] = list(map(int, input()))
	a, b = [0]*27, [0]*27
	ts = list(map(int, input().split()))
	for t in ts[1:]: a[t] = 1
	ts = list(map(int, input().split()))
	for t in ts[1:]: b[t] = 1
	for j in range(n):
		for z in range(5):
			for y in range(5):
				for x in range(5):
					s = 0;
					for i in range(26):
						xx, yy, zz = x+mv[i][0], y+mv[i][1], z+mv[i][2]
						if xx >= 0 and xx < 5 and yy >= 0 and yy < 5 and zz >= 0 and zz < 5:
							s += arr[j&1][zz][yy][xx] & 1
					if arr[j&1][z][y][x] & 1: arr[1-(j&1)][z][y][x] = b[s]
					else: arr[1-(j&1)][z][y][x] = a[s]
	if cno: print()
	cno += 1
	print("Case ", cno, ":", sep='')
	for z in range(5):
		if z > 0: print()
		for y in range(5): print(*arr[n&1][z][y], sep='')