Fişierul intrare/ieşire:	cowfood.in, cowfood.out	Sursă	preONI 2006 Runda 3
Autor	Adrian Vladu	Adăugată de
Timp execuţie pe test	0.225 sec	Limită de memorie	65536 kbytes
Scorul tău	N/A	Dificultate	4/5

Vezi solutiile trimise | Statistici

Cowfood

Cowfood

Cercetatorii nutritionisti fac experimente asupra amestecului optim de ierburi cu care pot fi hranite vacile. Au adunat K feluri de plante diferite si le-au amestecat, obtinand formule reprezentate prin vectori de forma (a¹, a², .. a[K]) unde a[i] reprezinta cantitatea de plante de tipul i folosita in mixtura. Se stie ca pentru orice amestec valid, a¹ + a² + ... + a[K] nu depaseste niciodata o valoare data S. Toate experimentele desfasurate au esuat insa, deoarece vacile nu au agreat cantitatile de ierburi din amestecurile testate. Mai mult, cercetatorii si-au dat seama ca pentru orice experiment ratat de forma (a¹, a², .. a[K]) , un experiment (b¹, b², .. b[K]) cu a¹ <= b¹, a² <= b², ... a[K] <= b[K] va esua de asemenea.

Cerinta

Fiindca cercetatorii vor sa termine lucrul cat mai curand posibil, este datoria ta sa afli cate experimente care mai au sanse de a se incheia cu succes au ramas.

Date de Intrare

Linia 1 a fisierului de intrare contine trei numere naturale K, S si N.

Liniile 2 .. N + 1 contin cate K numere (a¹, a², .. a[K]) ce reprezinta cate un experiment despre care se stie sigur ca a dat gres.

Date de Iesire

Fisierul de iesire va contine pe prima linie numarul de amestecuri ramase care mai au inca sanse de a fi agreate de vaci modulo 3210121.

Restrictii si precizari

• 2 <= K <= 30
• 2 <= S <= 10 000
• 0 <= N <= 20
• orice mixtura valida contine cel putin doua cantitati nenule de ierburi diferite
• toate valorile date in fisierul de intrare se incadreaza in tipuri intregi pe 16 biti

Exemplu

Cum se trimit solutii?