Fişierul intrare/ieşire:icrisop.in, icrisop.outSursăad-hoc
AutorAlexandru TacheAdăugată deswift90Ionut Bogdanescu swift90
Timp execuţie pe test1.4 secLimită de memorie65536 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Icrisop

Intr-un tinut indepartat, Regele Spiderman incearca din rasputeri sa creeze icrisopul magic. El are la dispozitie N tipuri de icrisop fiecare cu un anumit grad de magie, pana in 100. Pentru a obtine icrisopul magic el trebuie sa combine icrosupurile intr-o anumita ordine astfel incat suma gradelor de magie sa fie fix S. Regele Spiderman va cere sa aflati in cate moduri se poate obtine icrisopul de gradul magic S, modulo 666013, considerand ca exista un numar nelimitat de icrisop din fiecare tip si ca ordinea in care sunt adaugate icrosopurile conteaza. De exemplu pentru S = 2, N = 3 si tipurile de icrisop cu gradul de magie 1,1,2 raspunsul este 5 (tip1 + tip1, tip1 + tip 2, tip 2 + tip 1, tip 2 + tip 2, tip 3).

Date de intrare

Fisierul de intrare icrisop.in contine pe prima linie N si S, iar pe urmatoarele N linii cate un numar reprezentand gradul de magie al fiecarui tip de icrisop.

Date de ieşire

In fisierul de iesire icrisop.out veti afisa numarul de moduri in care se poate forma icrisopul magic, de magie S, modulo 666013.

Restricţii

  • 1 ≤ N ≤ 30 000
  • 1 ≤ gradul de magie al oricarui icrisop ≤ 100
  • S incape pe un intreg de 32 de biti cu semn.
  • Pentru 20% din teste S ≤ 100000

Exemplu

icrisop.inicrisop.out
3 2
1
2
1
5

Explicaţie

Urmatoarele combinatii sunt posibile: tip1+tip1, tip3+tip3, tip1+tip3, tip3+tip1, tip2

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content