# PBinfo #4400 – primprim – Rezolvare C++

Sursa: Codul lui Andrei
Limbaj: C++
Autor rezolvare: deivid

## Enunț

Pentru un număr natural a definim costul ca fiind valoarea absolută (modulul) diferenței dintre a și numărul prim cel mai apropiat de a. Asupra unui șir de n numere naturale, situate pe poziții numerotate de la 1 la n, se aplică, în ordine, o succesiune de q operații. O operație constă dintr-o înlocuire și o afișare și este descrisă sub forma i x p, cu semnificația:


mai întâi înlocuim cu x elementul din șir de pe poziția i;
apoi afișăm suma minimă totală a costurilor unor elemente convenabil selectate de pe p poziții distincte din șir.

Cerința
Cunoscând n și cele n elemente ale șirului, scrieți un program care să determine:
1. suma costurilor tuturor elementelor din șirul dat;
2. rezultatele afișate în urma aplicării fiecăreia dintre cele q operații, date în forma precizată.

Date de intrare
Fișierul de intrare primprim.in conține pe prima linie un număr natural C, reprezentând cerința care trebuie să fie rezolvată (1 sau 2), pe a doua linie numărul natural n, cu semnificația din enunț, iar pe a treia linie cele n elemente din șir, în ordinea din șir. Dacă C = 2, pe a patra linie se află numărul natural q, reprezentând numărul de operații, iar pe următoarele q linii se află cele q operații, câte o operație pe linie, în forma descrisă în enunț. Numerele scrise pe aceeași linie sunt separate prin câte un spațiu.

Date de ieșire
Dacă C = 1, fișierul de ieșire primprim.out va conține o singură linie pe care va fi afișată suma costurilor tuturor elementelor din șir. Dacă C = 2, fișierul de ieșire primprim.out va conține q linii, pe linia i fiind scris rezultatul afișat după executarea celei de a i-a operații din fișierul de intrare.

Restricții și precizări

1 ≤ q ≤ 2 ∗ 100.000
1 ≤ i, p ≤ n ≤ 1.000.000; 1 ≤ x ≤ 1.000.000
Elementele șirului sunt numere naturale nenule mai mici sau egale cu 1.000.000.
Datorită dimensiunilor mari ale fișierelor, nu au putut fi adăugate toate.

Exemplul 1:
primprim.in

1
5
8 1 3 5 9
primprim.out

4
Explicație
C = 1, n = 5, iar șirul este 8, 1, 3, 5, 9. Costurile elementelor sunt, în ordine, 1, 1, 0, 0, 2, deci suma este 4.

Exemplul 2:
primprim.in

2
5
8 1 3 5 9
3
2 6 4
3 5 2
5 12 5
primprim.out

2
0
3
Explicație
C = 2, n = 5, iar șirul inițial este 8, 1, 3, 5, 9. Se aplică șirului 3 operații. După prima operație, pentru care i = 2, x = 6 și p = 4, șirul devine 8, 6, 3, 5, 9. Suma minimă totală se obține dacă selectăm valorile de pe pozițiile 1, 2, 3 și 4, costurile fiind 1 + 1 + 0 + 0 = 2. După a doua operație, pentru care i = 3, x = 5 și p = 2, șirul devine 8, 6, 5, 5, 9. Selectăm valorile de pe pozițiile 3 și 4 (acestea având costul 0). După a treia operație, pentru care i = 5, x = 12 și p = 5, șirul devine 8, 6, 5, 5, 12. Selectăm toate valorile, deci suma este 1 + 1 + 0 + 0 + 1 = 3.

## Cod sursă C++

```cpp
/*
primprim - Stefan Dascalescu
*/
#include <fstream> 
#include <cmath>
using namespace std; 
ifstream fin("primprim.in"); 
ofstream fout("primprim.out"); 
int vals[1000002];
int primes[200002], cnt;
int ans[1100002];
bool pr[1100002];
int fr[202];
int main()  
{  
    int c; 
    fin >> c; 
    int n, a = 1100000, i, j; 
    fin >> n; 
    for(i = 1; i <= n; i++) 
        fin >> vals[i]; 
    // precalculam raspunsul optim pentru fiecare numar de la 1 la a folosind ciurul lui Eratostene 
    for(i = 2; i <= a; i++) 
    { 
        if(pr[i] == 0) 
        { 
			primes[cnt++] = i;
            for(j = i+i; j <= a; j += i) 
                pr[j] = 1; 
        } 
    } 
    int poz = -1; 
    // parcurg valorile de la 1 la a pentru a afla raspunsul optim dupa ce am aflat numerele prime 
    ans[1] = 1; 
    for(i = 2; i <= a; i++) 
    { 
        if(pr[i] == 0) 
            poz++; 
        ans[i] = abs(i - primes[poz]); 
        if(poz + 1 < cnt) 
            ans[i] = min(ans[i], abs(i - primes[poz+1])); 
    } 
    // voi folosi vector de frecventa pentru a tine aceste diferente, care de altfel sunt destul de mici 
    for(i = 1; i <= n; i++) 
        fr[ans[vals[i]]]++; 
    if(c == 1) 
    { 
        int total = 0;           
        for(i = 1; i <= n; i++) 
            total += ans[vals[i]]; 
        fout << total; 
        return 0; 
    } 
    int q; 
    fin >> q; 
    for(i = 1; i <= q; i++) 
    { 
        int a, b, p; 
        fin >> a >> b >> p; 
        fr[ans[vals[a]]]--; 
        vals[a] = b; 
        fr[ans[vals[a]]]++; 
        int dif = 0; 
        int sol = 0; 
        // la fiecare pas parcurg vectorul de frecventa pana cand dau de p diferente 
        while(p) 
        { 
            sol += min(p, fr[dif]) * dif; 
            p -= min(p, fr[dif]); 
            dif++; 
        } 
        fout << sol << '\n'; 
    } 
    return 0; 
}
```

## Resurse

- [Pagina originală](https://codulluiandrei.ro/rezolvari/pbinfo/4400)
- [Sursa C++](https://codulluiandrei.ro/rezolvari/pbinfo/4400/cod.cpp)
- [Sursa pe GitHub](https://raw.githubusercontent.com/codulluiandrei/pbinfo/main/pbinfo-4400/main.cpp)
- [Cursuri de informatică pentru BAC](https://codulluiandrei.ro/academia/info-curs/pachet-cpp/)