Lui Johnie ii place sa se
joace construind blocuri din cuburi. El dispune de o infinitate de cuburi albe
(toate cele sase fete colorate in alb) si negre (toate cele sase fete colorate
in negru). Toate cuburile lui au latimea, inaltimea si lungimea de un
metru.
Pentru a construi un bloc, Johnie dispune cuburile pe N
niveluri, fiecare nivel continand 2*2
cuburi. Deci Johnie obtine la sfarsit un bloc cu inaltimea N,
latimea 2 si lungimea 2.
Dupa ce s-a saturat sa construiasca blocuri aleator, Johnie si-a dat seama ca
un bloc este mai frumos daca exista o componenta conexa formata doar din cuburi
albe, ce contine cel putin K
elemente.
Spunem ca doua cuburi
X, Y sunt in aceeasi componenta conexa daca:
• X si Y
sunt asezate pe pozitii adiacente in bloc (au o fata "comuna");
• X este adiacent cu un cub Z,
iar Z este in aceeasi componenta
conexa cu Y.
Cerinta
Determinati numarul de blocuri
frumoase ce se pot construi. Rezultatul trebuie afisat modulo 10000.
Date de intrare
Fisierul de intrare cuburi.in
contine pe prima linie doua numere naturale N
si K, separate prin spatiu, cu
semnificatia din enunt.
Date de iesire
Fisierul de iesire cuburi.out
va contine o singura linie pe care va fi scris numarul de blocuri frumoase ce
se pot construi, modulo 10000.
Restrictii si precizari
•
1 <= N <= 40
• 1 <= K <=
4*N
Exemplu
cuburi.in
cuburi.out
Explicatii
3 12
1
Exista un singur bloc,
cu toate cuburile albe.
cuburi.in
cuburi.out
Explicatii
4 15
17
Exista 17 blocuri,
deoarece sunt valide toate blocurile ce au 15 cuburi colorate in alb si
unul in negru (16 cuburi de acest fel) precum si blocul ce are toate cuburile
colorate in alb.
cuburi.in
cuburi.out
6 15
2244
Daniel
Pasaila
Universitatea "Al.
I Cuza", Iasi
Facultatea de Informatica
danielpasaila@yahoo.com