0353 - Spectacole

Cerinţa

La un festival sunt programate n spectacole. Pentru fiecare se cunoaște momentul de început și momentul de sfârșit, exprimate prin numere naturale. Un spectator dorește să urmărească cât mai multe spectacole în întregime.

Determinați numărul maxim de spectacole care pot fi urmărite, fără ca acestea să se suprapună.

Date de intrare

Fişierul de intrare spectacolein.txt conţine pe prima linie numărul n. Pe fiecare dintre următoarele n linii se află câte două numere naturale X Y, reprezentând momentul de început și momentul de sfârșit al unui spectacol.

Date de ieşire

Fişierul de ieşire spectacoleout.txt va conţine pe prima linie numărul S, reprezentând numărul maxim de spectacole care pot fi urmărite, fără să se suprapună.

Restricții și precizări

• 1 ⩽ n ⩽ 100
• momentele de început și sfârșit ale spectacolelor sunt numere naturale mai mici decât 1.000.000
• pentru fiecare spectacol, X < Y
• dacă momentul de început al unui spectacol și momentul de sfârșit al altui spectacol coincid, pot fi urmărite ambele spectacole

Exemplul 1

spectacolein.txt

10
5 14
14 17
8 13
13 15
15 17
3 6
4 7
6 9
11 14
10 11

spectacoleout.txt

Datele de intrare corespund restrictiilor impuse.
5

Explicație

Pot fi alese, de exemplu, spectacolele: 3 6, 6 9, 10 11, 11 14 și 14 17.

Exemplul 2

spectacolein.txt

igrij

spectacoleout.txt

Datele de intrare nu corespund restrictiilor impuse.

Rezolvare

<syntaxhighlight lang="python" line>

1. Funcția de validare verifică dacă datele de intrare sunt în intervalul specificat

def validare(n_validare, spectacole_validare):

   # Verificăm dacă n este în intervalul 1-100
   if n_validare < 1 or n_validare > 100:
       raise ValueError  # Ridicăm o eroare dacă n nu este în intervalul 1-100
   for spectacol in spectacole_validare:    # Parcurgem lista de spectacole
       # Verificăm dacă momentele de început și sfârșit ale spectacolelor sunt în intervalul specificat
       if spectacol[0] >= 1000000 or spectacol[1] >= 1000000 or spectacol[0] >= spectacol[1]:
           raise ValueError
   file_out.write("Datele de intrare corespund restrictiilor impuse.\n")

1. Funcția numar_spectacole determină numărul maxim de spectacole care pot fi urmărite, fără ca acestea să se suprapună

def numar_spectacole(n_numar, spectacole_numar):

   # Sortăm spectacolele în funcție de momentul de sfârșit
   spectacole_numar.sort(key=lambda x: x[1])
   # Inițializăm numărul de spectacole cu 1
   nr_spectacole = 1
   # Inițializăm momentul de sfârșit al ultimului spectacol urmărit
   sfarsit_ultim = spectacole_numar[0][1]
   # Parcurgem lista de spectacole
   for i in range(1, n_numar):
       if spectacole_numar[i][0] >= sfarsit_ultim:
           # Urmărim spectacolul curent
           nr_spectacole += 1
           sfarsit_ultim = spectacole_numar[i][1]
   return nr_spectacole

if __name__ == '__main__':

   file_in = open("spectacolein.txt", "r")
   file_out = open("spectacoleout.txt", "w")

   try:
       # Citim numărul de spectacole
       n_main = int(file_in.readline())
       # Citim momentele de început și sfârșit ale spectacolelor
       spectacole_main = [list(map(int, file_in.readline().split())) for _ in range(n_main)]
       # Validăm datele de intrare
       validare(n_main, spectacole_main)
       # Determinăm numărul maxim de spectacole care pot fi urmărite
       nr_spectacole_main = numar_spectacole(n_main, spectacole_main)
       # Scriem numărul maxim de spectacole care pot fi urmărite în fișierul de ieșire
       file_out.write(str(nr_spectacole_main) + '\n')

   # Dacă datele de intrare nu sunt valide, afișăm un mesaj de eroare
   except ValueError:
       file_out.write("Datele de intrare nu corespund restrictiilor impuse.")
   # Dacă datele de intrare sunt incomplete, afișăm un mesaj de eroare
   except IndexError:
       file_out.write("Datele de intrare nu corespund restrictiilor impuse.")

</syntaxhighlight>