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

Fişierul bac.txt conţ ine un şir de cel pu ţin trei şi cel mult 1000000 de numere naturale cu cel mult nouă cifre. Numerele din şir sunt separate prin câte un spa ţiu.
Se cere să se afişeze pe ecran, separate printr-un spa ţiu, două numere distincte, anume cel mai mic număr par cu două cifre şi cel mai mare număr par cu două cifre care NU fac parte din şir.
Dacă nu există două astfel de valori, pe ecran se afisează mesajul Nu exista.
Pentru determinarea numerelor cerute se utilizează un algoritm eficient din punctul de vedere al timpului de executare.

Exemplu: dacă fişierul bac.txt con ţine valorile

7 2 40 5 10 15 11 12 18 350

se afişează pe ecran numerele 14 98.

Arată Soluţia

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

ifstream in("bac.txt");

// Vector in care memorez nr pare de 2 cifre gasite in sir
bool pare[45];

int main()
{
    int x, a = 0, b = 0;
    while (in >> x)
    {
        if (x / 100 == 0 && x % 2 == 0) {
            pare[(x - 10) / 2] = true;
        }
    }

    for (int i = 0; i < 45; i++)
        if (pare[i] == false) {
            a = i*2 + 10;
            break;
        }
    for (int i = 44; i >= 0; i--)
        if (pare[i] == false) {
            b = i*2 + 10;
            break;
        }

    if (a == b || a == 0) cout << "Nu exista";
    else cout << a << ' ' << b;

    return 0;
}

Complexitatea algoritmului este `O(n)` (liniar).