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

def verificare_date_intrare(n, m, indici_case_muncitori):

   if not (1 <= n <= 1000) or not (1 <= m <= 1000):
       return False
   for indici_case in indici_case_muncitori:
       if len(indici_case) != m or not all(1 <= indice <= 1000000000 for indice in indici_case):
           return False
   return True

1. Citire date de intrare

n = int(input("Introduceți numărul de muncitori (n): ")) m = int(input("Introduceți numărul de case (m): "))

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

   indici_casa_muncitor = list(map(int, input(f"Introduceți indicii caselor pentru muncitorul {i + 1}, separați prin spațiu: ").split()))
   indici_case_muncitori.append(indici_casa_muncitor)

1. Verificare date de intrare

if not verificare_date_intrare(n, m, indici_case_muncitori):

   print("Datele introduse nu corespund restricțiilor impuse")

else:

   # Calcul și afișare rezultate
   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"Numărul maxim de muncitori care lucrează la aceeași casă este: {max_muncitori_pe_o_casa_result}")
   print(f"Numărul maxim de case la care lucrează simultan cel puțin 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.