Fişierul intrare/ieşire:plus.in, plus.outSursăStelele Informaticii 2007, clasele 9-10
AutorSilviu-Ionut GanceanuAdăugată desilviugSilviu-Ionut Ganceanu silviug
Timp execuţie pe test0.1 secLimită de memorie20480 kbytes
Scorul tăuN/ADificultateN/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.inplus.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.

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content