# PBinfo #4423 – secv2 – Rezolvare C++

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

## Enunț

Gigel participă la un concurs de matematică și informatică și îi plac foarte mult numerele prime și secvențele. 

Tocmai a găsit un șir cu N elemente numere naturale și un număr K. Dezamăgit că nu toate elementele șirului sunt prime, Gigel vrea să afle care este cea mai lungă secvență din șir care conține cel mult K elemente neprime.

Cerința
Scrieți un program care să determine cea mai lungă secvență de elemente din șir care conține cel mult K numere neprime.

Date de intrare
Fișierul de intrare secv2.in conține pe prima linie numerele N K, iar pe următoarea linie N numere naturale, separate prin spații, reprezentând elementele șirului.

Date de ieșire
Fișierul de ieșire secv2.out va conține două numere naturale, separate printr-un spațiu: L P, unde L este lungimea maximă a secvenței determinate, iar P reprezintă indicele de început al secvenței determinate.

Restricții și precizări

1 ≤ N ≤ 200.000
0 ≤ K ≤ N
elementele șirului sunt mai mici decât 1.000.000
dacă există mai multe secvențe pentru care lungimea este maximă, se va afișa aceea pentru care P este minim
pentru teste în valoare de 20 de puncte, K = 0
pentru teste în valoare de alte 20 de puncte N ≤ 1000
pentru teste în valoare de alte 20 de puncte N ≤ 200.000 și K = 1
șirul conține cel puțin un număr prim

Exemplu:
secv2.in

8 2
10 3 7 6 11 4 9 7
secv2.out

5 1
Explicație
Secvența rezultat este 10 3 7 6 11. O altă secvență de lungime maximă este 3 7 6 11 4, dar indicele de început este mai mare.

## Cod sursă C++

```cpp
#include <iostream>
#include <fstream>
#include <cassert>
using namespace std;
ifstream fin("secv2.in");
ofstream fout("secv2.out");
const int NMAX = 200000 + 5;
int n , k , A[NMAX];
int E[1000001];
int main()
{
	E[0] = E[1] = 1;
	for(int i = 2 ; i * i <= 1000000 ; i ++)
		if(E[i] == 0)
			for(int j = 2 * i  ; j <= 1000000 ; j += i)
				E[j] = 1;
	fin >> n >> k;
	for(int i = 1; i <= n ; i ++)
	{
		int x;
		fin >> x;
		A[i] = E[x];
	}
	int cnt = 0, i = 0, L = 0, I = 0;
	for(int j = 1 ; j <= n ; j ++)
	{
		if(A[j] == 1)
			cnt ++;
		while(cnt > k)
		{
			i ++;
			if(A[i] == 1)
				cnt --;
		}
		if(j - i > L)
			L = j - i , I = i + 1;
	}
	fout << L << " " << I << '\n';
	cout << L << " " << I << '\n';
	return 0;
}
```

## Resurse

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