Fișierul intrare/ieșire | secvp.in, secvp.out | Sursă | ONI 2013 clasa a 7-a |
---|---|---|---|
Autor | Eugen Nodea | Adăugată de | Ciprian Ionescu • cip_ionescu |
Timp de execuție pe test | 0.5 sec | Limită de memorie | 4096 KB |
Scorul tău | N/A | Dificultate | N/A |
Vezi soluțiile trimise | Statistici
Secvp (clasa a 7-a)
Se consideră un șir cu N numere naturale a1, a2,…, aN. Asupra unui element ai, din șir, se pot efectua operații de incrementare (adunare cu 1: ai=ai+1) sau decrementare (scădere cu 1: ai=ai-1). Fiecare element din șir poate fi incrementat sau decrementat de oricâte ori.
Cerință
Dat fiind șirul celor N numere naturale, să se determine:
a. numărul total minim de operații necesare pentru a transforma toate numerele din șir în numere prime;
b. numărul minim de operații (incrementări și decrementări) ce trebuie să fie efectuate asupra elementelor șirului astfel încât să existe o secvență de lungime K formată numai din numere prime.
Date de intrare
Fișierul de intrare secvp.in conține pe prima linie numerele naturale N și K, iar pe următoarea linie N numere naturale. Numerele scrise pe aceeași linie sunt separate prin spații.
Date de ieșire
Fișierul de ieșire secvp.out conține pe prima linie un număr natural T, reprezentând numărul total minim de operații necesare pentru a transforma toate numerele din șir în numere prime. Pe a doua linie vor fi scrise două numere naturale separate prin spațiu minK nrsK, unde minK reprezintă numărul minim de operații ce trebuie să fie efectuate asupra elementelor șirului astfel încât să existe o secvență de lungime K formată numai din numere prime, iar nrsK reprezintă numărul de secvențe de lungime K care se pot obține cu același număr minK de operații de incrementare/decrementare.
Restricții
- 2 ≤ K ≤ N ≤ 100 000
- 0 ≤ ai ≤ 1 000 000, pentru 1 ≤ i ≤ N
- O secvență din șir este formată din elemente aflate pe poziții consecutive în șirul dat.
- 1 nu este număr prim.
- Pentru determinarea corectă a valorii T se acordă 30% din punctajul pe test. Pentru determinarea corectă a valorilor T și minK se acordă 70% din punctajul pe test. Punctajul integral se acordă pentru determinarea corectă a tuturor celor 3 valori.
Exemplu
secvp.in | secvp.out | Explicații |
---|---|---|
7 3 15 3 8 26 22 10 14 |
9 3 2 |
Pentru a transforma 15 în număr prim sunt necesare 2 incrementări Pentru a transforma 3 în număr prim sunt necesare 0 operații Pentru a transforma 8 în număr prim e necesară 1 decrementare Pentru a transforma 26 în număr prim sunt necesare 3 decrementări Pentru a transforma 22 în număr prim e necesară 1 incrementare Pentru a transforma 10 în număr prim e necesară 1 incrementare Pentru a transforma 14 în număr prim e necesară 1 decrementare Numărul total de operații necesare este 9. Numărul minim de operații necesare pentru a obține o secvență de lungime K este 3. Cele două secvențe de lungime K ce necesită 3 operații sunt a1, a2, a3 și a5, a6, a7. |