# PBinfo #2156 – Adlic – Rezolvare C++

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

## Enunț

Pentru următorul an școlar admiterea celor N elevi în liceu se va face pe baza unor evaluări complexe. Fiecare dintre viitorii elevi ai clasei a IX-a va primi, în urma testelor și probelor pe care le va susține, un punctaj (număr natural nenul) cu care va participa la admiterea electronică.

Repartizarea fiecărui elev în clase se face în ordinea înscrierii respectând criteriile:


Primul elev se repartizează în clasa cu numărul de ordine 1.
În clasa în care este repartizat un elev  nu există, până la momentul repartizării sale, nici un punctaj mai mare decât al său.
Numărul claselor să fie cât mai mic posibil.

Cerințe
Determinaţi:


Punctajul primului elev care nu ar mai putea fi repartizat în prima clasă în condițiile în care toți elevii își doresc să fie repartizați în prima clasă(se aplică doar la cerința 1).
Numărul claselor ce se vor forma respectând criteriile.

Date de intrare
Fișierul de intrare adlic.in conține pe primul rând numărul C a cărui valoare poate fi 1 sau 2, apoi separat de un spațiu numărul natural N.

Pe liniile următoare se găsesc cele N punctaje ale elevilor în ordinea înscrierii, numere naturale nenule despărțite prin câte un spațiu. 

Date de ieșire
Dacă C=1, atunci în fişierul de ieşire adlic.out se va scrie soluția cerinței 1.
Dacă C=2, atunci în fişierul de ieşire adlic.out se va scrie soluția cerinței 2.

Restricții și precizări

Punctajele elevilor vor avea cel mult șase cifre
1 ≤ N ≤ 1 000 000 
Pentru cerința 1 se garantează existența soluției
Pentru 20% din punctaj cerinţa va fi C = 1
Pentru alte 20% din punctaj cerinţa va fi C = 2 și N ≤ 1000
Pentru restul testelor C = 2 și N ≤ 1 000 000

Exemplul 1
adlic.in

1 9
4 2 4 2 7 10 9 11 8
adlic.out

2
Explicație
4 se repartizează în prima clasă, iar 2 trebuie repartizat în cea de-a doua clasă

Exemplul 2
adlic.in

2 9
4 2 4 2 7 10 9 11 8
adlic.out

3
Explicație
O soluție posibilă este cea în care se formează clasele:

4 4 7 9 
2 2 10 11
8

## Cod sursă C++

```cpp
// Autor: Mihai Enache
#include <fstream>
using namespace std;
const int MAX_N = 1000002;
int N, cerinta;
int punctaje[MAX_N], ultim[MAX_N];
int main() {
    ifstream f("adlic.in");
    ofstream g("adlic.out");
    f >> cerinta >> N;
    for(int i = 1; i <= N; ++i) {
        f >> punctaje[i];
    }
    if(cerinta == 1) {
        int maxP = 0;
        int ans = 0;
        for(int i = 1; i <= N; ++i) {
            if(punctaje[i] < punctaje[i - 1]) {
                ans = punctaje[i];
                break;
            }
        }
        g << ans << "\n";
    }
    else {
        int nrClase = 0;
        for(int i = 1; i <= N; ++i) {
            int l = 1;
            int r = nrClase;
            int clasa = 0;
            while(l <= r) {
                int m = (l + r) / 2;
                if(ultim[m] <= punctaje[i]) {
                    clasa = m;
                    r = m - 1;
                }
                else {
                    l = m + 1;
                }
            }
            if(clasa) {
               ultim[clasa] = punctaje[i];
            }
            else {
                ++nrClase;
                ultim[nrClase] = punctaje[i];
            }
        }
        g << nrClase << "\n";
    }
    f.close();
    g.close();
    return 0;
}
```

## Resurse

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