Atenţie! Aceasta este o versiune veche a paginii, scrisă la 2009-11-20 08:47:16.
Revizia anterioară   Revizia următoare  

 

Fişierul intrare/ieşire:iopds.in, iopds.outSursăAlgoritmiada 2010, Runda 1
AutorStefan Alexandru FilipAdăugată deProstuStefan-Alexandru Filip Prostu
Timp execuţie pe test0.05 secLimită de memorie20480 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Iopds

Dubota are probleme cu somnul si se viseaza subsir. In vis, oaia noastra merge pe o poteca formata din N caramizi, sarind de pe o caramida pe cealalta. Caramizile au insa scrise pe ele niste valori reale, Vi. Cum Dubota este un subsir, ea are o proprietate, si dupa ce s-a gandit bine, a descoperit ca aceasta este:
A * Xi2 + B * Xi-12 + C * Xi * Xi-1 > 0
Acum oaia nazdravana vrea sa parcurga poteca astfel incat subsirul format de valorile caramizilor pe care sare sa respecte proprietatea sa.
Fiind date numerele A, B, C, si sirul Vi de N numere (reprezentand valorile caramizilor), ajutati-o pe Dubota sa determine in cate feluri poate parcurge poteca.

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 veti afisa 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 ≤ Vi ≤ 10000
  • Valorile lui Vi sunt date cu o precizie de 3 zecimale
  • Considerand ca sirul dat este V=(v1,v2,...,vN), se numeste subsir al lui V un sir (vi1,vi2,...,viK) cu proprietatea 1 ≤ i1 < i2 < ... < iK ≤ N.
  • Se vor numara doar subsirurile ce contin minim 2 elemente.
  • Pentru 30% din teste N < 12.
  • Pentru 30% din teste A = B = 0.000 si C > 0.000.

Exemplu

iopds.iniopds.out
2.000 -1.000 1.000
6
3.000 4.000 -1.000 -1.000 0.000 -2.000
6

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
Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?