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.

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

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

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.

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

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.

h2. Restrictii

* $1 ≤ N ≤ 20000$
* numerele din sir sunt mai mici sau egale cu 30000
* 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

* $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

h2. Exemplu

table(example). |_. politic.in |_. politic.out |

table(example). |_. $politic.in$ |_. $politic.out$ |

| 10
1 2 3 5 6 8 10 11 14 15
| 5

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

1923