Question

Cum se face problema 4?

Answer 1

a) Putem pune in niste vectori pozitiile primului si respectiv ultimului element egal cu o valoare la citire, si apoi folosim acesti vectori sa calculam lungimea maxima, care este mult mai eficient decat sa parcurgem iar vectorul initial(n + 10 parcurgeri (O(n)) vs 11n parcurgeri (1 pentru citire si 10 pentru fiecare numar, e tot O(n), dar mult mai ineficient)).

Daca stiu pozitia primului si ultimului element cu o anumita valoare, atunci lungimea secventei incadrate este $poz_{finala} - poz_{initiala} + 1$.

Astfel pot vedea care este lungimea maxima si apoi parcurg iar acesti vectori cu pozitii sa gasesc secventele respective, afisandu-le valoarea primului termen.

b)

#include <iostream>

#include <fstream>

using namespace std;

int poz_inceput[10], poz_final[10];

int main(){

int n;

ifstream f("bac.in");

int i = 1;

while(f >> n){

if(poz_inceput[n] == 0)

poz_inceput[n] = i;

poz_final[n] = i;

i++;

}

f.close();

//Calculam lungimea maxima

int lungimeMaxima = -1;

for(i = 0; i < 10; i++){

int lungime = poz_final[i] - poz_inceput[i] + 1;

if(lungime > lungimeMaxima)

lungimeMaxima = lungime;

}

cout << lungimeMaxima << '\n';

//Cautam valorile respective

for(i = 0; i < 10; i++){

int lungime = poz_final[i] - poz_inceput[i] + 1;

if(lungime == lungimeMaxima)

cout << i << ' ';

}

return 0;

}