# PBinfo #4395 – tema – Rezolvare C++ Sursa: Codul lui Andrei Limbaj: C++ Autor rezolvare: deivid ## Enunț Macarie a primit ca temă la Informatică următorul enunț de problemă: “Se consideră un șir A cu N numere naturale nenule, numerotate începând de la 1 până la N. Numim secvență o succesiune de termeni situați pe poziții consecutive în șir, iar lungimea secvenței o reprezintă numărul de termeni din care este formată. Costul unei secvențe este egal cu produsul dintre suma valorilor prime din secvență și suma celor compuse. Numărul compus este un număr care are cel puțin un divizor natural diferit de 1 și de el însuși, iar un număr este prim dacă are exact doi divizori naturali distincți, pe 1 și pe el însuși.”. Știm că numărul 1 nu este nici număr prim, nici compus, deci nu influențează costul niciunei secvențe în care se găsește. Evident, costul unei secvențe care nu conține niciun număr prim sau al unei secvențe care nu conține niciun număr compus este egal cu 0. De asemenea, suma valorilor prime dintr-o secvență care conține un singur număr prim X este egală cu X; în mod similar, suma valorilor compuse dintr-o secvență care conține un singur număr compus Y este egală cu Y. Cerința Ajutați-l pe Macarie să rezolve următoarele două cerințe ale temei: 1. Să se determine lungimea maximă a unei secvențe din șirul A pentru care costul ei este mai mic sau egal decât un număr natural nenul K. 2. Presupunem că fiecare număr compus din șirul A este înlocuit cu produsul dintre cel mai mic factor prim al său și cel mai mare factor prim al său. Să se determine secvența de lungime maximă din șirul nou obținut, pentru care cel mai mare divizor comun al numerelor din care este formată este diferit de 1. Se vor afișa pozițiile primului și ultimului element din secvență. Dacă sunt mai multe astfel de secvențe de lungime maximă, se va afișa cea pentru care poziția primului său element este maximă. Date de intrare Pe prima linie a fișierului de intrare tema.in se află trei numere naturale nenule C, N și K, în această ordine, separate prin câte un spațiu, unde C este numărul cerinței care trebuie rezolvată (1 sau 2), iar N și K au semnificația din enunț. Pe a doua linie se află N numere naturale nenule, separate între ele prin câte un spațiu, reprezentând, în ordine, termenii șirului A. Date de ieșire Pe prima linie a fișierului de ieșire tema.out: se scrie un număr natural nenul, reprezentând lungimea maximă determinată pentru prima cerință, dacă C = 1; se scriu două numere naturale nenule, separate printr-un spațiu, reprezentând, în ordine, pozițiile primului, respectiv ultimului element din secvența de lungime maximă, determinată conform celei de a doua cerințe, dacă C = 2. Restricții și precizări 2 ≤ N ≤ 100.000 1 ≤ K ≤ 1018; Numărul K nu are niciun rol pentru cerința 2. 1 ≤ A[i] ≤ 1.000.000, pentru fiecare i: 1 ≤ i ≤ N. În cazul ambelor cerințe, există o secvență soluție ce are lungimea cel puțin egală cu 2. Există cel puțin un element diferit de 1 în șirul A. Pentru 10 puncte, C = 1 și N = 2 Pentru 25 puncte, C = 1 și N ≤ 4000 Pentru 15 puncte, C = 1 și 5000 < N Pentru 10 puncte, C = 2 și N = 2 Pentru 25 puncte, C = 2 și N ≤ 4000 Pentru 15 puncte, C = 2 și 5000 < N Exemplul 1: tema.in 1 10 45 10 2 3 1 4 5 8 2 6 3 tema.out 5 Explicație C = 1, N = 10 și K = 45. Secvența (2, 3, 1, 4, 5) = (A2,A3,A4,A5,A6) are costul egal cu (2 + 3 + 5) × 4 = 40. Nu există, în șirul A, o secvență de lungime mai mare și de cost mai mic sau egal decât 45. Exemplul 2: tema.in 2 10 20 1 2 32 4 42 49 7 21 1 63 tema.out 5 8 Explicație C = 2, N = 10 și K = 20. După modificări, șirul A devine: (1, 2, 4, 4, 14, 49, 7, 21, 1, 21). Există două secvențe de lungime maximă pentru care cel mai mare divizor comun (“c.m.m.d.c.”) al numerelor din care sunt formate este diferit de 1: (2, 4, 4, 14) (poziția în șir a primului element este 2, iar c.m.m.d.c.-ul elementelor sale este 2), respectiv (14, 49, 7, 21) (poziția în șir a primului element este 5, iar c.m.m.d.c.-ul elementelor sale este 7). Pentru că sunt două secvențe de lungime maximă, în enunț este precizat că se va alege cea pentru care poziția primului său element este maximă, adică, în acest caz, (14, 49, 7, 21) = (A5,A6,A7,A8). ## Cod sursă C++ ```cpp /* Complexitate: O(ValMax * logValMax + N) Punctaj: 100p */ #include using namespace std; const int NMAX = 1e5 + 5; const int VALMAX = 1e6; const long long KMAX = 1LL*1e18; ifstream f ("tema.in"); ofstream g ("tema.out"); int A[NMAX]; int Task, N; long long K; int fpmax[VALMAX+5];/// fpmax[i] - Cel mai mare factor prim a lui i int fpmin[VALMAX+5];/// fpmin[i] Cel mai mic factor prim a lui i bool compus[VALMAX+5]; void Ciur () { /// determinam pentru fiecare numar cel mai mic si cel mai mare /// factor prim al in timp ce folosind Ciurul lui Eratostene /// determinam numerele prime <= VALMAX /// numarul x este prim atunci compus[x] = false; for (int i = 2; i <= VALMAX; i += 2) { fpmax[i] = fpmin[i] = 2; compus[i] = true; } compus[1] = compus[0] = true; compus[2] = false; for (int i = 3; i <= VALMAX; i += 2) { if (!compus[i]) { fpmin[i] = i; fpmax[i] = i; for (int j = 2*i; j <= VALMAX; j += i) { if (fpmin[j] == 0) fpmin[j] = i; fpmax[j] = i; compus[j] = true; } } } } void Read () { f >> Task >> N >> K; int S = 0; assert (1<= N && N <= 100000 && K <= KMAX && K > 0); for (int i = 1; i <= N; ++ i ) { f >> A[i]; assert (1 <= A[i] && A[i] <= 1000000); S += (A[i]==1? 1: 0); } assert (S < N); } void Solve_1 () { /// pentru fiecare indice curent i, considerat capat dreapta /// al secventei curente determinam indicele de inceput al secventei /// pentru care produsul nu depaseste K. /// Daca produsul este mai mare se renunta la A[st], incrementand st /// si actualizand valoarea produsului /// se va retine lungimea maxima a secventei ce respecta cerinta long long S_prim = 0; long long S_compus = 0; int ans_st = 0, ans_dr = -1; int st = 1; for (int i = 1; i <= N; ++ i ) { if (compus[A[i]] && A[i] > 1) S_compus += 1LL * A[i]; if (!compus[A[i]] && A[i] > 1)S_prim += 1LL * A[i]; while (st <= i && S_prim * S_compus > K) { if (compus[A[st]] && A[st] > 1) S_compus -= A[st]; if (!compus[A[st]] && A[st] > 1) S_prim -= A[st]; ++ st; } if (i - st + 1 > ans_dr - ans_st + 1) { ans_st = st; ans_dr = i; } } g << ans_dr - ans_st + 1 << '\n'; } int st[2][NMAX]; int dr[2][NMAX]; void Solve_2 () { ///Considerand transformarea numerelor deja efectuata determinam pentru fiecare i /// st[0][i] - cel mai mic indice din stanga unde regasim fpmin[A[i]] ca factor in toate elementele dintre acel indice si i /// st[1][i] - cel mai mic indice din stanga unde regasim fpmax[A[i]] ca factor in toate elementele dintre acel indice si i /// dr[0][i] - cel mai mare indice din dreapta unde regasim fpmin[A[i]] ca factor in toate elementele de la i pana la acea pozitie /// dr[1][i] - cel mai mare indice din dreapta unde regasim fpmax[A[i]] ca factor in toate elementele de la i pana la acea pozitie /// Pentru fiecare A[i] lungimea maxima a secventei care il contine si are cmmdc > 1 /// este = max{dr[0][i] - st[0][i] + 1, dr[1][i] - st[1][i] + 1} for (int i = 0; i < 2; ++ i ) for (int j = 1; j <= N; ++ j ) st[i][j] = dr[i][j] = j; for (int i = 2; i <= N; ++ i ) { if (A[i] == 1) { st[0][i] = st[1][i] = i+1; continue; } if (fpmin[A[i]] == fpmin[A[i-1]]) st[0][i] = st[0][i-1]; else if (fpmin[A[i]] == fpmax[A[i-1]]) st[0][i] = st[1][i-1]; else st[0][i] = i; if (fpmax[A[i]] == fpmin[A[i-1]]) st[1][i] = st[0][i-1]; else if (fpmax[A[i]] == fpmax[A[i-1]]) st[1][i] = st[1][i-1]; else st[1][i] = i; } for (int i = N-1; i >= 1; -- i ) { if (A[i] == 1) { dr[0][i] = dr[1][i] = i-1; continue; } if (fpmin[A[i]] == fpmin[A[i+1]]) dr[0][i] = dr[0][i+1]; else if (fpmin[A[i]] == fpmax[A[i+1]]) dr[0][i] = dr[1][i+1]; else dr[0][i] = i; if (fpmax[A[i]] == fpmin[A[i+1]]) dr[1][i] = dr[0][i+1]; else if (fpmax[A[i]] == fpmax[A[i+1]]) dr[1][i] = dr[1][i+1]; else dr[1][i] = i; } int ans_left = 1, ans_right = 0; for (int i = 1; i <= N; ++ i ) { int lg = dr[0][i] - st[0][i] + 1; if (lg > (ans_right - ans_left + 1)) { ans_left = st[0][i]; ans_right = dr[0][i]; } else if (lg == (ans_right - ans_left + 1) && ans_left < st[0][i]) { ans_left = st[0][i]; ans_right = dr[0][i]; } lg = dr[1][i] - st[1][i] + 1; if (lg > (ans_right - ans_left + 1)) { ans_left = st[1][i]; ans_right = dr[1][i]; } else if (lg == (ans_right - ans_left + 1) && ans_left < st[1][i]) { ans_left = st[1][i]; ans_right = dr[1][i]; } } g << ans_left << " " << ans_right << '\n'; } int main () { Ciur(); Read(); if (Task == 1) Solve_1(); else Solve_2(); return 0; } ``` ## Resurse - [Pagina originală](https://codulluiandrei.ro/rezolvari/pbinfo/4395) - [Sursa C++](https://codulluiandrei.ro/rezolvari/pbinfo/4395/cod.cpp) - [Sursa pe GitHub](https://raw.githubusercontent.com/codulluiandrei/pbinfo/main/pbinfo-4395/main.cpp) - [Cursuri de informatică pentru BAC](https://codulluiandrei.ro/academia/info-curs/pachet-cpp/)