Fişierul intrare/ieşire:cowfood.in, cowfood.outSursăpreONI 2006 Runda 3
AutorAdrian VladuAdăugată de
Timp execuţie pe test0.45 secLimită de memorie65536 kbytes
Scorul tăuN/ADificultatenormalnormalnormalnormalnormal

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.incowfood.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).

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content