Fișierul intrare/ieșire secvente.in, secvente.out Sursă OJI 2010 clasa a 8-a
Autor Marius Nicoli Adăugată de avatar francu Cristian Frâncu francu
Timp de execuție pe test 0.5 sec Limită de memorie 2048 KB
Scorul tău N/A Dificultate N/A
open book Poți vedea testele pentru această problemă accesând atașamentele .

Secvențe (clasa a 8-a)

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 py (y∈ℕ, y≠0) sau q·pm, 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=21, 3=3·20, 4=22, 5=5·20, 6=3·21, 7=7·20, 8=23, 10=5·21, 12=3·22, 13=13·20, 14=7·21, 16=24, 17=17·20.

Î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.
    În plus, Maria dorește să știe care este poziția de început și cea de final, pentru fiecare secvență descoperită, relative la șirul scris pe foaia de hârtie.

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.

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.

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.

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; a1, a2, a3, ..., an ∈ ℕ
  • 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.

Exemplu

secvente.in secvente.out Explicatii
2
5 3 2
7
27
4
45
1
3 5 7
3
4
5
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).
Șirul din acest set conține următoarele numere 3-prime:
a1=7 (număr prim), a2=27=33 (putere a lui 3) și a4=45=5·32 (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.
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),
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.

Trebuie să te autentifici pentru a trimite soluții. Click aici

Indicii de rezolvare

Arată 2 categorii