Rezolvare completă PbInfo #2156 Adlic

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:

  1. 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).
  2. 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

Cum e corect?

cout < "As la info"; cout << "As la info"; cout >> "As la info";

Felicitări! Poți mai mult?

Avem sute de probleme pentru tine, fiecare cu explicații ușor de înțeles.

Greșit, dar nu-i bai!

Antrenează-te cu sutele de probleme pe care ți le-am pregătit. Îți explicăm fiecare problemă în parte.

Rezolvare

Iată rezolvarea de 100 de puncte pentru problema Adlic:

// 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;
}

Atenție

Enunțurile afișate pe această pagină aparțin exclusiv site-ului PbInfo. Astfel, pentru ștergerea conținutului, puteți să ne contactați la adresa Adresa de email.

Rezolvarea problemei #2156 Adlic

Pe această pagină găsești rezolvarea de 100 de puncte pentru problema #2156 Adlic de pe PbInfo.ro. Atenție: nu încurajăm copiatul codului! Totuși, credem cu tărie că analizarea unei soluții corecte este o metodă foarte ușoară de a învăța informatică, astfel că oferim sursele pentru peste 1500 de probleme de pe platforma PbInfo.ro.

Pentru rezolvări PbInfo de la peste 1500 de probleme, vă invităm să intrați pe site-ul nostru!