3523 - John

Cerinta

Un canadian deține o firmă cu n muncitori. Fiecare din aceștia lucrează la m case, codificate prin numere naturale. Canadianul dorește să afle:

1) numărul maxim de muncitori care lucrează la aceeași casă

2) numărul maxim de case la care lucreaza simultan cel putin doi muncitori

Date de intrare

Programul citește de la tastatură numerele n, m, iar apoi n * m numere naturale. Primele m numere reprezintă indicii caselor la care lucrează muncitorul 1, următoarele m numere reprezintă indicii caselor la care lucrează muncitorul 2, …, ultimele m numere reprezintă indicii caselor la care lucrează muncitorul n.

Date de iesire

Programul va afișa pe ecran raspunsurile la cele două cerințe.

Restrictii si precizari

• n, m, numărul de case la care se lucrează sunt mai mici decât 1.001
• cele n * m numere citite vor fi mai mici decât 1.000.000.001

Exemplul 1

Intrare

3 3

1 2 3

2 3 4

3 4 5

Iesire

Datele introduse corespund restrictiilor impuse

3

2

Exemplul 2

Intrare

3 3

5.2 100 7.9

0 2 17

-3 9 10.7

Iesire

Datele introduse nu corespund restrictiilor impuse

Rezolvare

<syntaxhighlight lang="python3" line="1"> def max_muncitori_pe_o_casa(numar_muncitori, indici_case):

   frecventa_case = {}
   for indice_casa in indici_case:
       if indice_casa not in frecventa_case:
           frecventa_case[indice_casa] = 0
       frecventa_case[indice_casa] += 1

   return max(frecventa_case.values())

def max_case_cu_muncitori(n, m, indici_case_muncitori):

   frecventa_case = {}
   for indici_case in indici_case_muncitori:
       for indice_casa in indici_case:
           if indice_casa not in frecventa_case:
               frecventa_case[indice_casa] = 0
           frecventa_case[indice_casa] += 1

   numar_maxim_case = 0
   for frecventa in frecventa_case.values():
       if frecventa >= 2:
           numar_maxim_case += 1

   return numar_maxim_case

1. Citire date de intrare

n = int(input("Introduceti numarul de muncitori (n): ")) m = int(input("Introduceti numarul de case (m): "))

indici_case_muncitori = [] for i in range(n):

   indici_casa_muncitor = list(map(int, input(f"Introduceti indicii caselor pentru muncitorul {i + 1}, separati prin spatiu: ").split()))
   indici_case_muncitori.append(indici_casa_muncitor)

1. Calcul si afisare raspunsuri

max_muncitori_pe_o_casa_result = max_muncitori_pe_o_casa(n, indici_case_muncitori[0]) max_case_cu_muncitori_result = max_case_cu_muncitori(n, m, indici_case_muncitori)

print(f"Numarul maxim de muncitori care lucreaza la aceeasi casa este: {max_muncitori_pe_o_casa_result}") print(f"Numarul maxim de case la care lucreaza simultan cel putin doi muncitori este: {max_case_cu_muncitori_result}")

</syntaxhighlight>

Explicatie

Toți cei 3 muncitori lucrează la casa 3. Intersecția dintre oricare 2 muncitori este mai mică sau egală cu 2.