Ježko Pichliač ide na dovolenku do exotickej krajiny -- Aburdistanu. V Aburdistane je svetovo preslávených pamiatok a Ježko by ich chcel postupne navštíviť všetky. O každej pamiatke vie, koľko radosti z výletu mu daná pamiatka pridá, keď ju navštívi. Toto číslo môže byť aj záporné.
Ježko si chce teraz naplánovať svoj výlet. Nezáleží mu, v akom poradí navštívi pamiatky, chce však každú navštíviť práve raz a chce, aby v žiadnom momente neklesla jeho radosť z výletu pod . Na začiatku má samozrejme radosť . Pomôžte mu zistiť, koľkými rôznymi spôsobmi si vie naplánovať svoj výlet.
Na vstupe dostanete počet pamiatok a tiež čísel -- množstvo radosti, ktoré nám pridá návšteva pamiatky . Zistite počet rôznych spôsobov návštevy všetkých pamiatok tak, aby v žiadnom momente nebola Ježkova radosť záporná.
Na prvom riadku je číslo () -- počet pamiatok v Aburdistane.
Na druhom riadku je celých čísel () -- množstvo radosti získanej pri návšteve -tej pamiatky.
Vypíšte jedno celé číslo -- počet rôznych možností.
3
1 -2 2
3
Ježko nemôže začať návštevou druhej pamiatky, lebo jeho radosť by hneď klesla pod . Ak začne prvou pamiatkou, ako ďalšia musí nasledovať tretia, takže máme jednu možnosť . Ak začne treťou, obe zvyšné možnosti sú prijateľné, teda a . Dokopy máme rôzne výlety.
5
-540 817 331 366 -253
50