== include(page="template/taskheader" task_id="plus") ==
Poveste si cerinta...
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: $NrBile{~1~}, NrBile{~2~}, NrBile{~3~}$. Toate bilele de tipul $i$ au inscrise pe ele acelasi numar intreg $Numar{~i~}$. 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.
h2. Date de intrare
Fisierul de intrare $plus.in$ ...
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, $NrBile{~i~}$ si $Numar{~i~}$, cu semnificatia de mai sus.
h2. Date de iesire
In fisierul de iesire $plus.out$ ...
In fisierul de iesire $plus.out$ va contine un singur numar intreg reprezentand numarul de aranjamente distincte.
h2. Restrictii
* $... ≤ ... ≤ ...$
* $-1 ≤ Numar{~i~} ≤ 1$
* $0 ≤ S, NrBile{~i~} ≤ 100000$
* Pentru 40% din teste $0 ≤ S, NrBile{~i~} ≤ 300$
* Pentru *inca* 30% din teste $0 ≤ S, NrBile{~i~} ≤ 5000$
* Algorel va recomanda sa folositi numere intregi pe 64 de biti
h2. Exemplu
table(example). |_. plus.in |_. plus.out |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
| 1
1 0
1 -1
2 1
| 4
|
| 0
1 -1
2 -1
3 -1
| 1
|
h3. 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.
== include(page="template/taskfooter" task_id="plus") ==
