0549 - Epidemie
Cerința
Într-o țară locuiesc n
persoane. Anumite perechi de persoane se cunosc între ele și se cunosc aceste perechi. Relația de cunoaștere între două persoane este reciprocă.
În țară izbucnește o epidemie (nu este mortală, doar foarte contagioasă). Dacă persoana A
este bolnavă și cunoaște persoana B
, se va îmbolnăvi și aceasta, după o perioadă de incubație a bolii de 1
zi. Inițial sunt bolnave k
persoane cunoscute. Se cere să se determine după câte zile sunt bolnave toate cele n
persoane.
Date de intrare
Fișierul de intrare epidemieIN.txt
conține pe prima linie numerele n m
, reprezentând numărul persoanelor și numărul perechilor de persoane care se cunosc reciproc. Urmează m
linii cu câte două numere i j
, cu semnificația: persoanele i
și j
se cunosc. Pe următoarea linie se află numărul k
de persoane infectate inițial, iar pe ultima linie se află k
numere distincte cuprinse între 1
și n
, reprezentând aceste persoane.
Date de ieșire
Fișierul de ieșire epidemieOUT.txt
va conține pe prima linie numărul Z
, reprezentând numărul de zile după care toate cele n
persoane sunt infectate.
Restricții și precizări
1 ≤ n ≤ 1000
1 ≤ m ≤ n*(n-1)/2
1 ≤ i , j ≤ n
1 ≤ k ≤ n
- ziua inițială va fi luată în considerare
- graful asociat acestei populații este conex
Exemplul 1
epidemieIN.txt
10 12 1 2 1 7 1 10 2 4 2 5 2 6 3 4 4 5 5 6 7 8 8 10 9 10 2 4 8
epidemieOUT.txt
3
Explicație
În prima zi se îmbolnăvesc persoanele: 4 8
. În ziua a doua se infectează 2 3 5 7 10
. În ziua a treia se infectează 1 6 9
.
Exemplul 2
epidemieIN.txt
4 5 1 2 2 3 3 4 4 1 1 3 2 1 5
epidemieOUT.txt
Datele nu corespund restrictiilor impuse
Rezolvare
from collections import defaultdict, deque
def citeste_input(file_path):
with open(file_path, 'r') as file:
n, m = map(int, file.readline().split())
cunostinte = defaultdict(list)
for _ in range(m):
i, j = map(int, file.readline().split())
cunostinte[i].append(j)
cunostinte[j].append(i)
k = int(file.readline())
persoane_infectate = set(map(int, file.readline().split()))
return n, m, cunostinte, k, persoane_infectate
def verifica_restrictii(n, m, cunostinte, k, persoane_infectate):
if not (1 <= n <= 1000) or not (1 <= m <= n*(n-1)//2) or not (1 <= k <= n):
return False
for i, j in cunostinte.items():
for vecin in j:
if not (1 <= i <= n) or not (1 <= vecin <= n):
return False
if any(persoana <= 0 or persoana > n for persoana in persoane_infectate):
return False
return True
def rezolva(n, cunostinte, k, persoane_infectate):
zile = 0
infectate = set(persoane_infectate)
queue = deque(persoane_infectate)
while queue:
zile += 1
for _ in range(len(queue)):
persoana = queue.popleft()
for vecin in cunostinte[persoana]:
if vecin not in infectate:
infectate.add(vecin)
queue.append(vecin)
return zile
def scrie_output(file_path, zile):
with open(file_path, 'w') as file:
file.write(str(zile))
if __name__ == "__main__":
input_file = "epidemieIN.txt"
output_file = "epidemieOUT.txt"
n, m, cunostinte, k, persoane_infectate = citeste_input(input_file)
if verifica_restrictii(n, m, cunostinte, k, persoane_infectate):
zile = rezolva(n, cunostinte, k, persoane_infectate)
scrie_output(output_file, zile)
else:
with open(output_file, 'w') as file:
file.write("Datele nu corespund restrictiilor impuse")