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 |
Vezi solutiile trimise | Statistici
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 (a1, a2, .. ak) unde ai reprezinta cantitatea de plante de tipul i folosita in mixtura. Se stie ca pentru orice amestec valid, a1 + a2 + ... + ak 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 (a1, a2, .. ak) , un experiment (b1, b2, .. bk) cu a1 ≤ b1, a2 ≤ b2, ... ak ≤ bk 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 cowfood.in contine trei numere naturale K, S si N.
Liniile 2 .. N + 1 contin cate K numere (a1, a2, .. ak) ce reprezinta cate un experiment despre care se stie sigur ca a dat gres.
Date de Iesire
Fisierul de iesire cowfood.out 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
cowfood.in | cowfood.out |
---|---|
2 5 2 1 3 3 1 | 4 |
Explicatii
Cele 4 amestecuri care mai pot fi incercate sunt (1, 1), (1, 2), (2, 1), (2, 2).