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.
Exemple
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.