Bacalaureat 2012 - Problema 4 - Subiectul 3 (Sesiunea speciala)

Fişierul bac.txt conţine pe prima linie un număr natural par n cu cel mult patru cifre, iar pe următoarea linie un şir de n numere naturale cu cel mult nouă cifre. Numerele din şir sunt în ordine crescătoare şi sunt separate prin câte un spaţiu. Se cere să se afişeze pe ecran cel mai mare număr din prima jumătate a şirului care să fie strict mai mic decât oricare număr din a doua jumătate a şirului. Dacă în fişier nu se află o astfel de valoare, pe ecran se afişează mesajul Nu exista. Pentru determinarea numărului cerut se utilizează un algoritm eficient din punctul de vedere al memoriei şi al timpului de executare.

Exemplu: dacă fişierul bac.txt are conţinutul

30
1 3 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 7 10

atunci pe ecran se afişează 3, iar dacă fişierul are conţinutul

6
3 3 3 3 9 15

atunci pe ecran se afişează Nu exista.

Arată Soluţia

Voi folosi variabilele x şi y pentru a reţine ultimele valori distincte citite din fişier, iar variabila r pentru valoarea curentă citită din fişier.
Ideea este să găsim ultimele două valori distincte (dacă există) din prima jumătate a şirului, şi să le comparăm cu prima valoare din a doua jumătate a şirului. În funcţie de rezultat, conform cerinţei problemei, vom afişa mesajele corespunzătoare.

#include <iostream>
#include <fstream>
using namespace std;

ifstream fin("bac.txt");

int main()
{
    int n, x, y, r;
    fin >> n;
    fin >> r; x = y = r;
    for(int i = 2; i <= (n/2 + 1); i++)
    {
        fin >> r;
        if(i == (n/2 + 1)) 
        {
            if(y < r) cout << y;
            else if(x < r) cout << x;
            else cout << "Nu exista";
        }
        else if(r != y) { x = y; y = r; }
    }
    return 0;
}