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

2023-12-13T16:49:57Z

Pagină nouă: = Cerința = Într-o țară locuiesc <code>n</code> 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 <code>A</code> este bolnavă și cunoaște persoana <code>B</code>, se va îmbolnăvi și aceasta, după o perioadă de incubație a bolii de <code>1</code> zi. Inițial sunt bolna...

New page

= Cerința =
Într-o țară locuiesc <code>n</code> 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 <code>A</code> este bolnavă și cunoaște persoana <code>B</code>, se va îmbolnăvi și aceasta, după o perioadă de incubație a bolii de <code>1</code> zi. Inițial sunt bolnave <code>k</code> persoane cunoscute. Se cere să se determine după câte zile sunt bolnave toate cele <code>n</code> persoane.

= Date de intrare =
Fișierul de intrare <code>epidemieIN.txt</code> conține pe prima linie numerele <code>n m</code>, reprezentând numărul persoanelor și numărul perechilor de persoane care se cunosc reciproc. Urmează <code>m</code> linii cu câte două numere <code>i j</code>, cu semnificația: persoanele <code>i</code> și <code>j</code> se cunosc. Pe următoarea linie se află numărul <code>k</code> de persoane infectate inițial, iar pe ultima linie se află <code>k</code> numere distincte cuprinse între <code>1</code> și <code>n</code>, reprezentând aceste persoane.

= Date de ieșire =
Fișierul de ieșire <code>epidemieOUT.txt</code> va conține pe prima linie numărul <code>Z</code>, reprezentând numărul de zile după care toate cele <code>n</code> persoane sunt infectate.

= Restricții și precizări =

* <code>1 ≤ n ≤ 1000</code>
* <code>1 ≤ m ≤ n*(n-1)/2</code>
* <code>1 ≤ i , j ≤ n</code>
* <code>1 ≤ k ≤ n</code>
* ziua inițială va fi luată în considerare
* graful asociat acestei populații este conex

= Exemplul 1 =
<code>epidemieIN.txt</code>
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
<code>epidemieOUT.txt</code>
3

= Explicație =
În prima zi se îmbolnăvesc persoanele: <code>4 8</code>. În ziua a doua se infectează <code>2 3 5 7 10</code>. În ziua a treia se infectează <code>1 6 9</code>.

== Exemplul 2 ==
<code>epidemieIN.txt</code>
4 5
1 2
2 3
3 4
4 1
1 3
2
1 5
<code>epidemieOUT.txt</code>
Datele nu corespund restrictiilor impuse

== Rezolvare ==
<syntaxhighlight lang="python3" line="1">
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")

</syntaxhighlight>

0549 - Epidemie - Revision history