Fișierul intrare/ieșire politic.in, politic.out Sursă ONI 2007 clasa a 7-a
Autor Victor Manz Adăugată de avatar isa_mirica_mihai Mirica Matei Mihai isa_mirica_mihai
Timp de execuție pe test 0.1 sec Limită de memorie 3072 KB
Scorul tău N/A Dificultate stea de rating de tip fullstea de rating de tip emptystea de rating de tip emptystea de rating de tip emptystea de rating de tip empty
open book Poți vedea testele pentru această problemă accesând atașamentele .

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

Pe prima linie a fișierului de intrare politic.in se află un număr natural nenul N, reprezentând numărul de deputați din parlament.
Pe a doua linie se află N numere naturale nenule separate prin câte un spațiu, ordonate strict crescător, reprezentând doctrinele parlamentarilor.

Date de ieșire

Prima linie a fișierului de ieșire politic.out va conține un număr natural nenul X, reprezentând numărul de partide din parlament, iar a doua linie va conține un alt număr natural nenul Y, care reprezintă numărul de coaliții majoritare care se pot forma.

Restricții și precizări

  • 0 < N ≤ 20 000
  • numerele din șir sunt mai mici sau egale cu 30000
  • pentru determinarea corectă a numărului de partide parlamentare se acordă 30% din punctaj, iar pentru afișarea corectă a numărului de variante de coaliție majoritară se acordă 70% din punctaj

Exemplu

politic.in politic.out Explicație
10
1 2 3 5 6 8 10 11 14 15
5
4
Partidele parlamentare sunt: P1=(1,2,3), P2=(5,6), P3=(8), P4=(10,11) și P5=(14,15).
 
Variantele de coaliție majoritară sunt :
P1+P2+P3, P1+P2+P3+P4, P1+P2+P3+P4+P5, P2+P3+P4+P5.

Explicație

Trebuie să te autentifici pentru a trimite soluții. Click aici

Indicii de rezolvare

Arată 4 categorii