Fişierul intrare/ieşire:	iopds.in, iopds.out	Sursă	Algoritmiada 2010, Runda 1
Autor	Stefan Alexandru Filip	Adăugată de	Stefan-Alexandru Filip •Prostu
Timp execuţie pe test	0.05 sec	Limită de memorie	20480 kbytes
Scorul tău	N/A	Dificultate	N/A

Vezi solutiile trimise | Statistici

Iopds

Dubota are probleme cu somnul, aceasta oaie se viseaza subsir si e stresata pentru ca nu isi stie valorile. In timpul visului se plimba pe o poteca de lungul careia sunt N marcaje cu numere reale iar in dreptul fiecarui marcaj se intreaba daca numarul trecut acolo ii poate apartine sau nu, sau ce in conditii ar face parte. Dubota sta si se gandeste bine si isi da seama, ca prin vis, ca este un subsir care respecta proprietatea:
A * X_i² + B * X_i-1² + C * X_i * X_i-1 > 0
Atunci Dubota isi da seama ca sunt mai multe modalitati prin care numerele de pe borne pot respecta formula.
Fiind date numerele A, B, C, si stiind sirul V_i de N numere (reprezentand valorile trecute pe borne), ajutati-o pe Dubota sa determine cate subsiruri respecta proprietatea sa.

Date de intrare

Fişierul de intrare iopds.in contine pe prima linie 3 numere reale, A, B, si C. Pe a doua linie se afla un intreg, N. Pe a treia linie sa gasesc N numere reale reprezentant sirul V.

Date de ieşire

În fişierul de ieşire iopds.out numarul de subsiruri care respecta proprietatea lui Dubota. Pentru ca aceasta valoare poate sa fie foarte mare, il veti scrie modulo 333019.

Restricţii

• -1000 ≤ A, B, C ≤ 1000
• 1 ≤ N ≤ 2000
• -10000 ≤ V_i ≤ 10000
• Valorile lui V_i sunt date cu o precizie de 3 zecimale
• Considerand ca sirul dat este V=(v₁,v₂...v_N), se numeste subsir al lui V un sir X=(x_i1,x_i2...x_iN) cu proprietatea 1 ≤ i₁ < i₂ < ... < i_K ≤ N.
• In cazul de fata, un subsir are minim 2 elemente.
• Pentru 30% din teste N < 12.
• Pentru 30% din teste A = B = 0.000.

Exemplu

Explicaţie

Valorile ingrosate reprezinta un subsir:

1. 3.000 4.000 -1.000 -1.000 0.000 -2.000
2. 3.000 4.000 -1.000 -1.000 0.000 -2.000
3. 3.000 4.000 -1.000 -1.000 0.000 -2.000
4. 3.000 4.000 -1.000 -1.000 0.000 -2.000
5. 3.000 4.000 -1.000 -1.000 0.000 -2.000
6. 3.000 4.000 -1.000 -1.000 0.000 -2.000

Cum se trimit solutii?