Fișierul intrare/ieșire	politic.in, politic.out	Sursă	ONI 2007 clasa a 7-a
Autor	Victor Manz	Adăugată de	Mirica Matei Mihai • isa_mirica_mihai
Timp de execuție pe test	0.05 sec	Limită de memorie	3072 KB
Scorul tău	N/A	Dificultate	1.5

Poți vedea testele pentru această problemă accesând atașamentele .

Vezi soluțiile trimise | Statistici

Politic (clasa a 7-a)

În Țara lui Papură Vodă s-au organizat de curând primele alegeri democratice. A rezultat astfel un parlament din care fac parte deputați cu diverse doctrine politice, de stânga sau de dreapta. Acestea sunt descrise prin numere naturale nenule (orientarea politică este cu atât mai de stânga cu cât numărul este mai mic). Parlamentarii s-au asociat în partide politice în funcție de doctrina fiecăruia. Oricare doi deputați ale căror doctrine corespund unor numere consecutive fac parte din același partid. Prin urmare, partidele vor fi alcătuite din deputați ale căror doctrine sunt numere consecutive. (De exemplu, dacă parlamentul are 5 deputați, cu doctrinele 1,2,3,5 și 6, atunci înseamnă că aceștia sunt grupați în două partide: unul format din 1,2 și 3 și altul din 5 și 6.)
Un guvern trebuie să beneficieze de susținerea a mai mult de jumătate dintre parlamentari. De exemplu, dacă parlamentul este format din 7 deputați, atunci un guvern are nevoie de susținerea a cel puțin 4 deputați.
Pentru a putea guverna, partidele se pot grupa in coaliții. Regula după care se asociază este urmatoarea: două partide A și B, A având o doctrină mai de stânga, pot face parte din aceeași coaliție doar dacă din coaliția respectivă fac parte toate partidele a căror doctrină este mai de dreapta decât cea a lui A și mai de stânga decât cea a lui B. De exemplu, dacă parlamentul este alcătuit din deputați cu orientările politice 1,2,4,5,7 și 8, atunci partidul format din 1 și 2 nu se poate asocia cu partidul format din 7 și 8 decât dacă din coaliția respectivă face parte și partidul format din 4 și 5.

Cerință

Fiind dat parlamentul din Țara lui Papură Vodă printr-un șir ordonat strict crescător de numere naturale nenule, se cere să se stabilească numărul de partide parlamentare și numărul variantelor de coaliție majoritară.

Date de intrare

Fișierul de intrare politic.in ...

Date de ieșire

În fișierul de ieșire politic.out ...

Restricții

• ... ≤ ... ≤ ...

Exemplu

Explicație

...