politic

Politic

== include(page="template/taskheader" task_id="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.)

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.

h2. 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

* 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

h2. Exemplu

== include(page="template/taskfooter" task_id="politic") ==

1923