== include(page="template/taskheader" task_id="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: $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.
Poveste si cerinta...
h2. 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, $NrBile{~i~}$ si $Numar{~i~}$, cu semnificatia de mai sus.
Fisierul de intrare $plus.in$ ...
h2. Date de iesire
In fisierul de iesire $plus.out$ va contine un singur numar intreg reprezentand numarul de aranjamente distincte.
In fisierul de iesire $plus.out$ ...
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 |
| 1
1 0
1 -1
2 1
| 4
|
| 0
1 -1
2 -1
3 -1
| 1
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
|
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") ==
