| Fişierul intrare/ieşire: | plus.in, plus.out | Sursă | Stelele Informaticii 2007, clasele 9-10 |
| Autor | Silviu-Ionut Ganceanu | Adăugată de |  Silviu-Ionut Ganceanu •silviug |
| Timp execuţie pe test | 0.05 sec | Limită de memorie | 20480 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Plus
De data aceasta Algorel are de a face numai cu trei tipuri de bile cu care trebuie sa impodobeasca bradul. Normal, si acum Algorel stie cate bile are din fiecare tip: NrBile1, NrBile2, NrBile3. Toate bilele de tipul i au inscrise pe ele acelasi numar intreg Numari. Pentru amuzamentul lui, Algorel a decis sa impodobeasca bradul astfel incat suma numerelor inscrise pe bilele agatate in pom sa fie exact S. Pentru ca poate gasi destul de rapid un astfel de aranjament si pentru ca nu are ce face pana vine Mosul, el s-a decis sa numere cate astfel de aranjamente exista. Doua aranajemente se considera identice daca folosesc exact acelasi numar de bile din fiecare tip.
Date de intrare
Fisierul de intrare plus.in contine pe prima linie un numar intreg S reprezentand suma numerelor inscrise pe bile dintr-un aranjament valid. Urmatoarele 3 linii descriu tipurile de bile: linia i+1 contine doua numere intregi separate printr-un spatiu, NrBilei si Numari, cu semnificatia de mai sus.
Date de iesire
In fisierul de iesire plus.out va contine un singur numar intreg reprezentand numarul de aranjamente distincte.
Restrictii
- -1 ≤ Numari ≤ 1
- 0 ≤ S, NrBilei ≤ 100000
- Pentru 40% din teste 0 ≤ S, NrBilei ≤ 300
- Pentru inca 30% din teste 0 ≤ S, NrBilei ≤ 5000
- Algorel va recomanda sa folositi numere intregi pe 64 de biti
Exemplu
| plus.in | plus.out |
|---|---|
| 1 1 0 1 -1 2 1 | 4 |
| 0 1 -1 2 -1 3 -1 | 1 |
Explicatie
Aranjamentele posibile pentru primul test sunt urmatoarele (fiecare aranjament este specificat prin numarul de bile folosite din fiecare tip):
- aranjament 1: 0, 0, 1
- aranjament 2: 1, 0, 1
- aranjament 3: 0, 1, 2
- aranjament 4: 1, 1, 2
Ultimul aranjament respecta regula deoarece 1*0 + 1*-1 + 2*1 = 1.
Pentru cel de-al doilea test exista un singur arajament cu suma 0: cel in care nu punem nicio bila in pom.
