Školsko natjecanje 2011. godine za 3. i 4. razred Srednje Škole - 3. zadatak

Marin i Stipe su se zaposlili kao šegrti kod jednog majstora - keramičara. Kako su se pokazali dobrim radnicima majstor im sve češće dopušta da samostalno rade u određenom dijelu prostorije u kojoj postavljaju pločice.

Majstor im zada jedan pravokutnik visine N decimetara i širine M decimetara, te im da K pločica jednake visine – 1 dm, ali različitih širina.

Stipe i Marin uvijek uspješno obave svoj zadatak, bez većih problema, ali svaki puta pločice poslože drugačijim rasporedom. Stoga su se zapitali na koliko načina mogu posložiti pločice u pravokutni dio prostorije koji im zadao majstor, koristeći svih K pločica koje su im na raspolaganju na način da popune cijeli zadani pravokutnik.

Napomena: Pločice uvijek postavljaju u vodoravnom položaju.

ULAZNI PODACI

U prvom retku se nalaze tri prirodna boja N, M i K (1 ≤ N, M, K ≤ 16) koji redom predstavljaju visinu i širinu pravokutnika, te broj pločica koje su na raspolaganju Marinu i Stipi. U slijedećih K redova se nalazi po jedan prirodan broj L (1 ≤L ≤ 16), koji predstavlja širinu i-te pločice u decimetrima.

IZLAZNI PODACI

Potrebno je ispisati u prvom i jedinom retku broj načina na koji Stipe i Marin mogu posložiti pločice tako da cijeli pravokutnik bude popunjen.

PRIMJERI TEST PODATAKA

ulaz

1 2 2
1
1

izlaz

2

ulaz

1 6 3
1
2
3

izlaz

6

ulaz

2 2 4
1
1
1
1

izlaz

24

Pojašnjenje prvog primjera: Ubacivanjem u 4. stupac igrač 1 ostvaruje niz od četiri svoja žetona dijagonalno i pobjeđuje. Pobjedu bi ostvario i ubacivanjem u 7. stupac, ali niz „4“ leksikografski je manji od niza „7“.

Pojašnjenje drugog primjera: Igrač 1 ubacuje u 6. stupac, nakon čega igrač 2 ubacuje u 7. stupac, čime omogućuje igraču 1 da ubacivanjem u 7. stupac ostvari vodoravni niz od četiri svoja žetona.

Pojašnjenje trećeg primjera: Niz „121“ nije ispravan jer bi u tom slučaju igrač 2 pobijedio nakon drugog poteza.