Question

1) Într-un institut de geologie se folosesc mai multe tipuri de roci pentru analize spectrale. Rocile sunt păstrate în n recipiente, numerotate distinct de la 1 la n, în ordinea colectării. Pentru efectuarea unui experiment se alege numărul maxim de roci, în ordinea în care au fost colectate, astfel încât numerele de minerale din compoziţia rocilor alese să fie consecutive, ordonate strict crescător.

Cerinţă

Dat fiind n, numărul de roci şi numărul de minerale conţinute de fiecare rocă, în ordinea colectării acestora, să se determine numărul minim de experimente care se pot efectua astfel încât să fie folosite toate rocile.

Fişierul de intrare conţine pe prima linie un număr natural n reprezentând numărul de roci. Pe cea de a doua linie se află n numere naturale nenule, separate prin câte un spaţiu, m1 m2 … mn, reprezentând numărul de minerale conţinute de fiecare rocă.

Date de ieşire
Fişierul de ieşire va conţine o singură linie pe care va fi scris un număr natural G reprezentând numărul minim de grupe de roci care se pot forma.

Restricţii
■0 ■ 0 ■ Numărul de minerale conţinute poate fi acelaşi pentru roci diferite.
■ O rocă poate fi folosită într-o singură grupă.

Exemplu

date.in
7
3 10 4 4 5 11 6
date.out
3

2)De ziua ei Mariuca îsi invita prietenii la pizza. Nici unul dintre prietenii Mariucai nu poate mânca o pizza întreaga, dar fiecare dintre ei stie exact cât poate mânca (un sfert, o jumatate sau trei sferturi) si insista sa-si primeasca pizza într-o singura felie.

Cerinta
Scrieti un program care sa determine numarul minim de pizza pe care Mariuca trebuie sa le comande astfel încât fiecare copil sa îsi primeasca bucata de pizza dorita.

Date de intrare
Fisierul de intrare contine pe prima linie un numar natural N reprezentând numarul de prieteni pe care Mariuca îi invita la pizza. Pe urmatoarele N linii sunt descrise preferintele celor N copii, câte o preferinta pe o linie. Linia i+1 va contine o fractie (1/4, 1/2 sau 3/4) care reprezinta dimensiunea feliei pe care o doreste copilul i.

Date de iesire
Fisierul de iesire va contine o singura linie pe care va fi scris un singur numar natural, reprezentând numarul minim de pizza pe care Mariuca trebuie sa le comande.

Restrictii
1 <= N <= 10000
Exemple


date.in
3
1/2
3/4
3/4
date.out
3

date.in
6
3/4
1/2
3/4
1/2
1/4
1/2
date.out
4

Answer 1

Prima problema:

#include <fstream>
#include <algorithm>
#include <vector>
using namespace std;
ofstream fout("prob.out");
ifstream fin("prob.in");
const int NMAX = 10000;

int n, x, nr, Max, poz_init;
int lg[NMAX], poz[NMAX];
vector<int> v;

void lis()
{
    for(int i=n-1; i>=0; i--) {
        for(int j=i+1; j<n; j++)
            if(v[i] < v[j] && lg[i] <= lg[j])
                lg[i] = lg[j] + 1, poz[i] = j;
        if(Max < lg[i]) Max = lg[i], poz_init = i;
    }
    nr++;
}

void sterge()
{
    int k = 0;

    for(int i=poz_init; i != -1; i = poz[i]) {
        v.erase(v.begin() + i + k);
        k--;
    }
    n += k;
}

int main()
{
    fin >> n;
    for(int i=0; i<n; i++) fin >> x, v.push_back(x);

    while(!v.empty()) {
        fill(lg, lg + n, 1), fill(poz, poz + n, -1);
        Max = poz_init = 0;
        lis();
        sterge();
    }

    fout << nr << '\n';
    return 0;
}

A doua problema: (data viitoare cand pui mai multe probleme la un loc, ofera si tu mai multe puncte :)) )

#include <fstream>
#include <algorithm>
#include <vector>
using namespace std;
ofstream fout("date.out");
ifstream fin("date.in");

int n, sol;
vector<float> v;

void citire()
{
    int x, y;

    fin >> n;
    for(int i=1; i<=n; i++) {
        float nr;
        fin >> x;
        fin.get();
        fin >> y;
        nr = (float)x / y;
        v.push_back(nr);
    }

    sort(v.begin(), v.end());
}

void rezolva()
{
    float suma = 0;

    while(!v.empty()) {
        float aux = v.front();

        if(aux + suma >= 1) sol++, suma = 0;
        else {
            suma += aux;
            v.erase(v.begin());
        }
    }

    fout << sol << '\n';
}

int main()
{
    citire();
    rezolva();
    return 0;
}