Enunțul problemei secvp, de clasa a 7-a, dată în 2013 la ONI, se găsește pe .campion.

Rezumat secvp

Avem un șir de n numere naturale, iar asupra fiecăruia se pot aplica de mai multe ori operațiile de incrementare și de decrementare. Trebuie să aflăm:

  • numărul total minim de operații după care toate numerele din șir vor fi prime
  • numărul minim de operații ce trebuie efectuate pentru a obține o secvență de lungime k formată numai din numere prime și numărul de astfel de secvențe

Soluție secvp

Pentru prima cerință vom parcurge șirul, iar pentru fiecare număr, calculăm modulul diferenței dintre el și cel mai apropiat număr prim de acesta. Pentru asta vom folosi o funcție minInc în care iterăm pe i de la 0 în sus până când x - i sau x + i este prim. Reținem valorile găsite într-un vector inc de dimensiune NMAX (pentru a doua cerință). Pe parcurs, pentru a afla răspunsul primei cerințe, calculăm suma acestor rezultate.

La a doua cerință practic trebuie să determinăm suma minimă pe care o poate avea o secvență de lungime k și câte astfel de secvențe există în vectorul nostru.

Vom folosi Ciurul lui Eratostene pentru a testa mai apoi în $O(1)$ primalitatea numerelor.

Sursă C++ secvp

Dacă ai vreo nedumerire cu privire la problema secvp, lasă un comentariu și te voi ajuta 🙂

Îți place conținutul acestui site?

Dacă vrei să mă susții în întreținerea server-ului și în a scrie mai multe articole de calitate pe acest blog, mă poți ajuta printr-o mică donație. Află aici cum o poți face!