Fişierul intrare/ieşire:politic.in, politic.outSursăONI 2007, clasa 7
AutorVictor ManzAdăugată depeanutzAndrei Homorodean peanutz
Timp execuţie pe test0.05 secLimită de memorie5120 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Politic

In Tara lui Papura Voda s-au organizat de curand primele alegeri democratice. A rezultat astfel un parlament din care fac parte deputati cu diverse doctrine politice, de stanga sau de dreapta. Acestea sunt descrise prin numere naturale nenule (orientarea politica este cu atat mai de stanga cu cat numarul este mai mic). Parlamentarii s-au asociat in partide politice in functie de doctrina fiecaruia. Oricare doi deputati ale caror doctrine corespund unor numere consecutive fac parte din acelasi partid. Prin urmare, partidele vor fi alcatuite din deputati ale caror doctrine sunt numere consecutive. De exemplu, daca parlamentul are 5 deputati, cu doctrinele 1, 2, 3, 5 si 6 atunci inseamna ca acestia sunt grupati in doua partide: unul format din 1, 2 si 3 si altul din 5 si 6.
Un guvern trebuie sa beneficieze de sustinerea a mai mult de jumatate dintre parlamentari. De exemplu, daca parlamentul este format din 7 deputati, atunci un guvern are nevoie de sustinerea a cel putin 4 deputati.
Pentru a putea guverna, partidele se pot grupa in coalitii. Regula dupa care se asociaza este urmatoarea: doua partide A si B, A avand o doctrina mai de stanga, pot face parte din aceeasi coalitie doar daca din coalitia respectiva fac parte toate partidele a caror doctrina este mai de dreapta decat cea a lui A si mai de stanga decat cea a lui B. De exemplu, daca parlamentul este alcatuit din deputati cu orientarile politice 1,2,4,5,7 si 8, atunci partidul format din 1 si 2 nu se poate asocia cu partidul format din 7 si 8 decat daca din coalitia respectiva face parte si partidul format din 4 si 5.

Cerinta

Fiind dat parlamentul din Tara lui Papura Voda printr-un sir ordonat strict crescator de numere naturale nenule, se cere sa se stabileasca numarul de partide parlamentare si numarul variantelor de coalitie majoritara.

Date de intrare

Pe prima linie a fisierului de intrare politic.in se afla un numar natural nenul N, reprezentand numarul de deputati din parlament.
Pe a doua linie se afla N numere naturale nenule separate prin cate un spatiu, ordonate strict crescator, reprezentand doctrinele parlamentarilor.

Date de iesire

Prima linie a fisierului politic.out va contine un numar natural nenul X, reprezentand numarul de partide din parlament, iar a doua linie va contine un alt numar natural nenul Y, care reprezinta numarul de coalitii majoritare care se pot forma.

Restrictii

  • 1 ≤ N ≤ 20000
  • Numerele din sir sunt mai mici sau egale cu 30 000
  • Pentru determinarea corecta a numarului de partide parlamentare se acorda 30% din punctaj, iar pentru afisarea corecta a numarului de variante de coalitie majoritara se acorda 70% din punctaj

Exemplu

politic.inpolitic.out
10
1 2 3 5 6 8 10 11 14 15
5
4
Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content