Atenţie! Aceasta este o versiune veche a paginii, scrisă la 2007-03-19 18:59:26.
Revizia anterioară   Revizia următoare  

 

Fişierul intrare/ieşire:cuburi.in, cuburi.outSursă.campion 2007
AutorDaniel PasailaAdăugată dedanielpDaniel Pasaila danielp
Timp execuţie pe test0.1 secLimită de memorie20096 kbytes
Scorul tăuN/ADificultatenormalnormalnormalnormalnormal

Vezi solutiile trimise | Statistici

Cuburi

Lui Johnie ii place sa se joace cu 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. Lui Johnie ii place sa isi dispuna cuburile pe N nivele, 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

Determinati numarul de blocuri frumoase ce se pot construi. Rezultatul trebuie afisat modulo 10000.

Date de intrare

Fisierul cuburi.in contine pe prima linie doua numere, N si K.

Date de iesire

Fisierul cuburi.out contine numarul cerut, modulo 10000.

Restrictii

  • 1 ≤ N ≤ 40
  • 1 ≤ K ≤ 4 * N 

Exemplu

cuburi.incuburi.out
3 12
1
4 15
17
6 15
2244

Explicatie

  • Testul 1: Exista un singur bloc, cu toate cuburile albe.
  • Testul 2: 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.
Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?