2405 - politic

Sursa: 2405 - politic

Î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 ≤ 20.000
numerele din șir sunt mai mici sau egale cu 30.000

Exemplu

Intrare: 10; 1 2 3 5 6 8 10 11 14 15
Ieșire: 5; 4

Rezolvare

Rezolvare ver. 1

2405 - politic

def read_input():

   n = int(input())
   parties = list(map(int, input().split()))
   return n, parties

def solve(n, parties):

   # numărul de partide
   num_parties = 0
   for i in range(n):
       if i == 0 or parties[i] - parties[i-1] > 1:
           num_parties += 1
   # numărul de coaliții majoritare
   num_majority_coalitions = 0
   for i in range(num_parties):
       for j in range(i+1, num_parties):
           if parties[j] - parties[i] == j - i:
               # partidele i și j pot forma o coaliție
               left = i-1 if i > 0 else None
               right = j+1 if j < num_parties-1 else None
               # verificăm dacă toate partidele între i și j sunt în coaliție
               if (left is None or parties[i] - parties[left] > 1) and (right is None or parties[right] - parties[j] > 1):
                   # am găsit o coaliție majoritară
                   num_majority_coalitions += 1
   return num_parties, num_majority_coalitions

def validate_output(expected, actual):

   assert expected == actual, f"Expected {expected}, but got {actual}"

if __name__ == '__main__':

   n, parties = read_input()
   num_parties, num_majority_coalitions = solve(n, parties)
   print(num_parties)
   print(num_majority_coalitions)

</syntaxhighlight>

Explicatie Rezolvare

Funcția read_input citește datele de intrare și le returnează sub forma unei perechi (n, parties), unde n este numărul de deputați, iar parties este lista cu orientările politice ale acestora. Funcția solve primește datele de intrare și calculează numărul de partide și numărul de coaliții majoritare. Pentru a calcula numărul de partide, parcurgem lista parties și numărăm câte ori întâlnim un număr care nu este consecutiv cu ultimul număr întâlnit. Pentru a calcula numărul de coaliții majoritare, parcurgem toate perechile de partide care pot forma o coaliție (adică două partide a căror diferență este egală cu diferența dintre pozițiile lor în listă) și verificăm dacă toate partidele între ele sunt în coaliție. Funcția validate_output validează rezultatul returnat de funcția solve, comparându-l cu rezultatul așteptat. În funcția main, citim datele de intrare, rezolvăm problema apelând funcția solve și afișăm rezultatul. Această soluție are complexitatea O(N^2), unde N este numărul de deputați din parlament. Pentru valorile maxime ale lui N (20.000), această soluție ar