Î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ța
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 conține pe prima linie 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
Fișierul de ieșire politic.out va conține pe prima linie 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 ≤ 20000- numerele din șir sunt mai mici sau egale cu
30000
Exemplu
politic.in
10 1 2 3 5 6 8 10 11 14 15
politic.out
5 4
Explicație
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.
Cum e corect?
cout < "As la info";
cout << "As la info";
cout >> "As la info";
Felicitări! Poți mai mult?
Avem sute de probleme pentru tine, fiecare cu explicații ușor de înțeles.
Greșit, dar nu-i bai!
Antrenează-te cu sutele de probleme pe care ți le-am pregătit. Îți explicăm fiecare problemă în parte.
Rezolvare
Iată rezolvarea de 100 de puncte pentru problema politic:
#include <fstream>
using namespace std;
int a[20005], n, k;
int main()
{
int i, j, x, y, cnt, nrDeputati, s;
ifstream fin("politic.in");
fin >> k;
n = 0;
fin >> x;
cnt = 1;
for (i = 2; i <= k; ++i)
{
fin >> y;
if (x + 1 == y) cnt++;
else {a[++n] = cnt; cnt = 1;}
x = y;
}
a[++n] = cnt;
nrDeputati = 0;
for (i = 1; i <= n; ++i)
nrDeputati += a[i];
nrDeputati /= 2;
i = 1;
s = 0;
cnt = 0;
for (j = 0; j<= n; )
{
if (s > nrDeputati)
{
cnt += (n - j + 1);
s -= a[i];
i++;
}
else
{
j++;
s += a[j];
}
}
ofstream fout("politic.out");
fout << n << "\n" << cnt << "\n";
fout.close();
return 0;
}Atenție
Enunțurile afișate pe această pagină aparțin exclusiv site-ului PbInfo. Astfel, pentru ștergerea conținutului, puteți să ne contactați la adresa 
.
Rezolvarea problemei #2405 politic
Pe această pagină găsești rezolvarea de 100 de puncte pentru problema #2405 politic de pe PbInfo.ro. Atenție: nu încurajăm copiatul codului! Totuși, credem cu tărie că analizarea unei soluții corecte este o metodă foarte ușoară de a învăța informatică, astfel că oferim sursele pentru peste 1500 de probleme de pe platforma PbInfo.ro.
Pentru rezolvări PbInfo de la peste 1500 de probleme, vă invităm să intrați pe site-ul nostru!