AntalKrisztian: Pagină nouă: == 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 din...

2023-12-29T18:01:46Z

Pagină nouă: == 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 din...

New page

== 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 &les; n &les; 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
<br>
== Explicație ==
Pot fi alese, de exemplu, spectacolele: '''3 6''', '''6 9''', '''10 11''', '''11 14''' și '''14 17'''.
<br>
== Exemplul 2 ==
; spectacolein.txt
igrij
; spectacoleout.txt
Datele de intrare nu corespund restrictiilor impuse.
<br>
== Rezolvare ==
<syntaxhighlight lang="python" line>
# 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")

# 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>

0353 - Spectacole - Revision history