Diferențe pentru problema/secvente între reviziile #17 si #24

== include(page="template/taskheader" task_id="secvente") ==

Mariei îi plac numerele prime și puterile numerelor prime. Pornind de la un număr prim p, ea construiește noi numere, fiecare număr construit fiind un produs de forma p[^y^] (y numar natural nenul) sau q*p[^m^], m număr natural și q un număr prim, numindu-le numere p-prime. De exemplu, numerele 2, 3, 4, 5, 6, 7, 8, 10, 12, 13, 14, 16, 17 sunt primele 13 numere 2-prime deoarece 2=2[^1^], 3=3*2[^0^], 4=2[^2^], 5=5*2[^0^], 6=3*2[^1^], 7=7*2[^0^], 8=2[^3^], 10=5*2[^1^], 12=3*2[^2^], 13=13*2[^0^], 14=7*2[^1^], 16=2[^4^], 17=17*2[^0^].
Într-o zi Maria a găsit o foaie de hârtie, pe care era scris un șir format din n numere naturale nenule. Cum pe lângă numerele p-prime ea este pasionată și de secvențe, și-a pus următoarea întrebare: câte secvențe sunt pe foaie cu următoarele proprietăți:

_Notă: această problemă este punctată diferit față de original, deoarece distribuția celor 100p la cele 17 teste s-a pierdut._
 
Mariei îi plac numerele prime și puterile numerelor prime. Pornind de la un număr prim *p*, ea construiește noi numere, fiecare număr construit fiind un produs de forma p[^y^] (y∈ℕ, y≠0) sau q·p[^m^], m∈ℕ și *q* un număr prim, numindu-le numere p-prime. De exemplu, numerele 2, 3, 4, 5, 6, 7, 8, 10, 12, 13, 14, 16, 17 sunt primele 13 numere 2-prime deoarece 2=2[^1^], 3=3·2[^0^], 4=2[^2^], 5=5·2[^0^], 6=3·2[^1^], 7=7·2[^0^], 8=2[^3^], 10=5·2[^1^], 12=3·2[^2^], 13=13·2[^0^], 14=7·2[^1^], 16=2[^4^], 17=17·2[^0^].
 
Într-o zi Maria a găsit o foaie de hârtie, pe care era scris un șir format din *n* numere naturale nenule. Cum pe lângă numerele p-prime ea este pasionată și de secvențe, și-a pus următoarea întrebare: câte secvențe sunt pe foaie cu următoarele proprietăți:

* conțin exact k numere p-prime;
* încep și se termină cu un număr p-prim.

h2. Cerință

Scrieți un program care să citească mai multe seturi de date, fiecare set fiind format din numerele n, p, k, cu semnificațiile din enunț, și șirul cu n elemente a1, a2, a3, ... an, numerele Mariei. Programul va determina pentru fiecare set de date numărul secvențelor ce conțin exact k numere p-prime, precum și pozițiile de început și de final ale acestor secvențe în șirul din set.

Scrieți un program care să citească mai multe seturi de date, fiecare set fiind format din numerele *n*, *p*, *k*, cu semnificațiile din enunț, și șirul cu *n* elemente a[~1~], a[~2~], a[~3~], ..., a[~n~], numerele Mariei. Programul va determina pentru fiecare set de date numărul secvențelor ce conțin exact *k* numere p-prime, precum și pozițiile de început și de final ale acestor secvențe în șirul din set.

h2. Date de intrare

Pe prima linie a fișierului $secvente.in$ se află numărul D reprezentând numărul de seturi de date din fișier. Seturile de date sunt scrise în fișier pe linii succesive. Pentru fiecare set de date, prima linie conține câte trei numere naturale: n (numărul de elemente de pe foaie), p și k (cu semnificația din enunț), separate prin câte un spațiu, iar fiecare dintre următoarele n linii conține câte un număr natural al șirului a1, a2, a3, ... an, numerele din șirul Mariei.

Pe prima linie a fișierului $secvente.in$ se află numărul *D* reprezentând numărul de seturi de date din fișier. Seturile de date sunt scrise în fișier pe linii succesive. Pentru fiecare set de date, prima linie conține câte trei numere naturale: *n* (numărul de elemente de pe foaie), *p* și *k* (cu semnificația din enunț), separate prin câte un spațiu, iar fiecare dintre următoarele n linii conține câte un număr natural al șirului a[~1~], a[~2~], a[~3~], ..., a[~n~], numerele din șirul Mariei.

h2. Date de ieșire

Fișierul $secvente.out$ va conține D soluții corespunzătoare celor D seturi de date. Pentru fiecare soluție prima linie va conține un număr x reprezentând numărul de secvențe ce îndeplinesc proprietățile cerute, iar fiecare dintre următoarele x linii vor conține câte 2 numere naturale, separate printr-un spațiu, reprezentând poziția de început, respectiv de final a fiecărei secvențe, linii ordonate crescător după poziția de început. Dacă în șir nu există o astfel de secvență, prima linie a setului va conține valoarea 0.

Fișierul $secvente.out$ va conține *D* soluții corespunzătoare celor *D* seturi de date. Pentru fiecare soluție prima linie va conține un număr *x* reprezentând numărul de secvențe ce îndeplinesc proprietățile cerute, iar fiecare dintre următoarele *x* linii vor conține câte 2 numere naturale, separate printr-un spațiu, reprezentând poziția de început, respectiv de final a fiecărei secvențe, linii ordonate crescător după poziția de început. Dacă în șir nu există o astfel de secvență, prima linie a setului va conține valoarea 0.

h2. Restricții

* 1 <= D <= 15
* 1 <= k <= n <= 15000
* 2 <= p <= 30000; p este un număr natural prim
* 1<= a1, a2, a3, ... an <=30000

* 1 ≤ *D* ≤ 15
* 1 ≤ *k*, *n* ≤ 15000
* 2 ≤ *p* ≤ 30000; *p* este un număr natural prim
* 1 ≤ a[~1~], a[~2~], a[~3~], ..., a[~n~] ≤ 30000; a[~1~], a[~2~], a[~3~], ..., a[~n~] ∈ ℕ

* Pozițiile din șir sunt numerotate de la 1.
* Numărul 1 nu este p-prim.
* O secvență dintr-un șir este formată din elemente aflate pe poziții consecutive în șirul dat.
h2. Exemplu

table(example).

table(example).

|_. secvente.in |_. secvente.out |_. Explicatii |
| 2
5 3 2

1 2
2 4
0

| Cum D=2, fișierul de intrare conține două seturi de date.
Primul set de date: n=5, p=3, k=2 și a=(7, 27, 4, 45, 1).

| Cum [*D*]=2, fișierul de intrare conține două seturi de date.
Primul set de date: [*n*]=5, [*p*]=3, [*k*]=2 și a=(7, 27, 4, 45, 1).

Șirul din acest set conține următoarele numere 3-prime:

a1=7 (număr prim), a2=27=3[^3^] (putere a lui 3) și a4=45=5*3[^2^] (număr prim înmulțit cu o putere a lui 3).
În șir sunt două secvențe cu câte doua numere 3-prime: a1, a2 respectiv a2, a3, a4.

a[~1~]=7 (număr prim), a[~2~]=27=3[^3^] (putere a lui 3) și a[~4~]=45=5·3[^2^] (număr prim înmulțit cu o putere a lui 3).
În șir sunt două secvențe cu câte doua numere 3-prime: a[~1~], a[~2~] respectiv a[~2~], a[~3~], a[~4~].

Pe prima linie a fișierului de ieșire se va scrie valoarea 2,

iar pe următoarele două linii, pozițiile de început și de final ale celor două secvențe determinate.
Șirul a din al doilea set de date, n=3, p=5, k=7, a=(3, 4, 5),

iar pe următoarele două linii, pozițiile de început și de final ale celor două secvențe determinate.
 
Șirul a din al doilea set de date, [*n*]=3, [*p*]=5, [*k*]=7, a=(3, 4, 5),

nu conține nici o secvență cu proprietatea cerută. Astfel, în fișierul de ieșire, pe cea de-a patra linie,
se va scrie valoarea 0.
|