Gol3d

Game of life 3D

== include(page="template/taskheader" task_id="gol3d") ==

Gigel a inventat un nou joc: game of life 3d. Sa vedem care sunt regulile: jocul se desfasoară in interiorul unui cub impartit in celule cubice, de volum unitar, cu dimensiunile N x N x N (in total N^3^ celule). In fiecare celula poate fi un organism viu sau mort. Jocul consta din urmarirea evolutiei organismelor pentru mai multe generatii. In fiecare generatie noua unele organisme pot deveni vii, altele pot muri dupa regulile urmatoare:

Gigel a inventat un nou joc: game of life 3d. Sa vedem care sunt regulile: jocul se desfasoară in interiorul unui cub impartit in celule cubice, de volum unitar, de dimensiune $NxNxN$ (in total $N^3^$ celule). In fiecare celula exista un organism viu sau mort. Jocul consta din urmarirea evolutiei organismelor pentru mai multe generatii. In fiecare generatie unele organisme evolueaza dupa regulile urmatoare:

* vecinii unei celule aflate la coordonatele (i,j,k) (0 ≤ i, j, k ≤ n-1) sunt acele celule (i',j',k') diferite de (i,j,k), aflate la o distanta mai mica sau egala cu d = [(i + j + k) / 5] + 1 de celula (i,j,k) (se considera parte intreaga inferioara la impartirea la 5); distanta dintre 2 celule (a{~1~},b{~1~},c{~1~}) si (a{~2~},b{~2~},c{~2~}) este max{|a{~1~}-a{~2~}|, |b{~1~}-b{~2~}|, |c{~1~}-c{~2~}|}

* vecinii unei celule aflate la coordonatele $(i,j,k) (0 ≤ i, j, k ≤ n-1)$ sunt acele celule $(i',j',k')$ diferite de $(i,j,k)$, aflate la o distanta mai mica sau egala cu $d = [(i + j + k) / 5] + 1$ de celula $(i,j,k)$ (se considera parte intreaga inferioara la impartirea la 5)

* daca o celula are mai putin de 25% vecini vii, ea va muri de singuratate in generatia urmatoare (in caz ca era vie)

* distanta dintre 2 celule $(a{~1~},b{~1~},c{~1~})$ si $(a{~2~},b{~2~},c{~2~})$ se defineste ca fiind $max{|a{~1~}-a{~2~}|, |b{~1~}-b{~2~}|, |c{~1~}-c{~2~}|}$

* daca o celula are mai mult de 75% vecini vii, ea va muri sufocata in generatia urmatoare (in caz ca era vie)

* daca o celula are strict mai putin de $25%$ vecini vii, ea va muri de singuratate in generatia urmatoare (in caz ca era vie)

* daca o celula are intre 45% si 55% (interval deschis) vecini vii, ea isi va schimba starea (va invia daca era moarta / va muri daca era vie)

* daca o celula are strict mai mult de $75%$ vecini vii, ea va muri sufocata in generatia urmatoare (in caz ca era vie)
 
* daca o celula are intre $45%$ si $55%$ (interval deschis) vecini vii, ea isi va schimba starea (va invia daca era moarta / va muri daca era vie)
 
* daca procentul de vecini vii nu se incadreaza in regulile de mai sus, atunci celula va fi vie in generatia urmatoare indiferent de starea ei in generatia anterioara

* daca procentul de vecini vii nu se incadreaza in regulile de mai sus, atunci celula va fi vie in generatia urmatoare
 

* toate nasterile si mortile dintr-o generatie au loc simultan (altfel spus, modificarea unei celule intr-o generatie nu poate afecta evolutia, in aceeasi generatie, a niciunei alte celule)
Stiind numarul de generatii al jocului, Gigel va roaga sa calculati pentru fiecare generatie numarul de organisme vii.
h2. Date de intrare

Fisierul de intrare $gol3d.in$ va contine pe prima linie doua numere naturale: N si G reprezentand dimensiunea cubului si numarul de generatii al jocului (incluzand-o si pe prima). Apoi, pentru fiecare i de la 0 la N-1 se dau cate N linii cu cate N elemente fiecare - elementul (j,k) din matrice va reprezenta starea organismului din celula (i,j,k) din prima generatie. Dupa fiecare matrice, mai putin ultima, va fi o linie goala. Se va folosi urmatoarea codificare: 0 - organism mort, 1 - organism viu.

Fisierul de intrare $gol3d.in$ va contine pe prima linie doua numere naturale: $N$ si $G$ reprezentand dimensiunea cubului si numarul de generatii al jocului (incluzand-o si pe prima). Apoi, pentru fiecare $i$ de la $0$ la $N-1$ se dau cate $N$ linii cu cate $N$ elemente fiecare - elementul $(j,k)$ din matrice va reprezenta starea organismului din celula $(i,j,k)$ in prima generatie. Dupa fiecare matrice, mai putin ultima, va fi o linie goala. Se va folosi urmatoarea codificare: $0$ - organism mort, $1$ - organism viu.

h2. Date de ieşire

In fisierul de iesire $gol3d.out$ va contine pe o singura linie G numere reprezentand numarul de organisme vii dupa fiecare generatie.

In fisierul de iesire $gol3d.out$ va contine pe o singura linie $G$ numere reprezentand numarul de organisme vii dupa fiecare generatie.

h2. Restrictii

* $1 ≤ N ≤ 64$

* $2 ≤ N ≤ 64$

* $1 ≤ G ≤ 100$
h2. Exemplu

h3. Explicatie

Prima generatie este chiar cea initiala unde avem numai 2 organisme vii. Urmatoarea generatie arata in modul urmator:

Prima generatie este chiar cea initiala unde avem numai $2$ organisme vii. Urmatoarea generatie va fi:
 
$1 0$
$1 1$

1 0
1 1

$1 1$
$1 0$

1 1
1 0

Toate celulele sunt vecine una cu alta (deoarece $d$-ul calculat dupa formula din enunt da $1$ intotdeauna). Organismele din celulele $(1,1,1)$ si $(0,0,1)$ au cate un vecin viu din $7$ (deci mai putin de $25%$) si mor de singuratate. Celelalte celule au $2$ vecini vii din $7$, deci ~28% si vor fi vii conform penultimei reguli a jocului.

== include(page="template/taskfooter" task_id="gol3d") ==

3571