Fișierul intrare/ieșire secvp.in, secvp.out Sursă ONI 2013 clasa a 7-a
Autor Eugen Nodea Adăugată de avatar cip_ionescu 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
open book Poți vedea testele pentru această problemă accesând atașamentele .

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.

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

Indicii de rezolvare

Arată 2 categorii