3382 - robot2

Cerinţa

Robotul Vasile s-a angajat la o fabrică de bomboane. El trebuie să ambaleze bomboanele în cutii. Toate bomboanele au formă dreptunghiulară. Două bomboane sunt de tipuri distincte dacă diferă prin cel puţin una dintre dimensiunile laturilor lor. Robotul determină dimensiunile bomboanelor (exprimate în milimetri) şi trebuie să ambaleze bomboanele în cutii astfel încât în orice cutie să existe exact câte o bomboană de fiecare tip. Scrieţi un program care citeşte dimensiunile bomboanelor şi rezolvă următoarele două cerinţe: 1. determină numărul de tipuri distincte de bomboane; 2. determină numărul maxim de cutii de bomboane pe care robotul Vasile le poate obţine din bomboanele existente, respectând condiţiile din enunţ.

Date de intrare

Fișierul de intrare robot.in conţine pe prima linie cerinţa c care trebuie să fie rezolvată (1 sau 2). Pe a doua linie se află numărul natural n, reprezentând numărul de bomboane. Pe următoarele n linii se află dimensiunile bomboanelor, câte o bomboană pe o linie; o linie care descrie o bomboană conţine două numere naturale separate printr-un spaţiu lg1 lg2, reprezentând lungimile laturilor bomboanei.

Date de ieșire

Dacă datele sunt introduse corect, pe ecran: "Datele sunt introduse corect.",fișierul de ieșire robot.out va conţine o singură linie pe care va fi scris un număr natural determinat conform cerinţei c. În cazul în care datele nu respectă restricțiile, se va afișa: "Datele nu corespund restricțiilor impuse.".

Restricţii şi precizări

• 2 ≤ n ≤ 500 000
• 0 < lg1, lg2 < 100

Exemple

Exemplul 1

robot.in

1

7

1 2

3 4

2 1

3 4

5 6

3 4

5 6

Ecran

Datele sunt introduse corect.

robot.out

3

Exemplul 2

robot.in

2

7

1 2

3 4

2 1

3 4

5 6

3 4

5 6

Ecran

Datele sunt introduse corect.

robot.out

2

Exemplul 3

robot.in

30

10

1 2

3 4

-1 5

6 7

8 9

10 11

12 13

14 15

16 17

18 19

Ecran

Datele sunt introduse corect.

robot.out'

nu exista

Rezolvare

<syntaxhighlight lang="python" line="1">

1. 3382 - robot2

from typing import Tuple, List

def validare_date(cerinta: int, nr_bomboane: int, dimensiuni_bomboane: List[Tuple[int, int]]) -> bool:

   """
   Verifică dacă datele de intrare corespund constrângerilor problemei.
   Returnează True dacă datele sunt valide și False altfel.
   """
   if not (1 <= cerinta <= 2):
       return False
   if not (2 <= nr_bomboane <= 500000):
       return False
   for x, y in dimensiuni_bomboane:
       if not (0 < x < 100 and 0 < y < 100):
           return False
   return True

def rezolvare_problema(cerinta: int, nr_bomboane: int, dimensiuni_bomboane: List[Tuple[int, int]]) -> int:

   """
   Rezolvă problema pe baza datelor de intrare și returnează răspunsul.
   """
   bomboane_distincte = [0] * 10002
   for x, y in dimensiuni_bomboane:
       bomboane_distincte[min(x, y) * 100 + max(x, y)] += 1
   if cerinta == 1:
       nr_bomboane_distincte = sum(1 for i in range(100, 10002) if bomboane_distincte[i] != 0)
       return nr_bomboane_distincte
   else:
       nr_maxim_cutii = float('inf')
       for i in range(1, 10002):
           if bomboane_distincte[i] != 0 and bomboane_distincte[i] < nr_maxim_cutii:
               nr_maxim_cutii = bomboane_distincte[i]
       return nr_maxim_cutii

if __name__ == '__main__':

   with open('robot.in', 'r') as f_in, open('robot.out', 'w') as f_out:
       cerinta = int(f_in.readline().strip())
       nr_bomboane = int(f_in.readline().strip())
       dimensiuni_bomboane = [tuple(map(int, line.strip().split())) for line in f_in.readlines()]
       if not validare_date(cerinta, nr_bomboane, dimensiuni_bomboane):
           print('Datele nu corespund restrictiilor impuse.')
           f_out.write('Datele nu corespund restrictiilor impuse.')
       else:
           print('Datele sunt introduse corect.')
           raspuns = rezolvare_problema(cerinta, nr_bomboane, dimensiuni_bomboane)
           f_out.write(str(raspuns))

</syntaxhighlight>

Explicatie

Funcția validare_date(cerinta: int, nr_bomboane: int, dimensiuni_bomboane: List[Tuple[int, int]]) -> bool verifică dacă datele de intrare corespund constrângerilor problemei. Primeste ca parametrii cerinta (1 sau 2), numarul de bomboane si o lista cu dimensiunile bomboanelor. Verifică dacă cerinta este 1 sau 2, dacă numarul de bomboane este cuprins între 2 și 500000 și dacă dimensiunile bomboanelor sunt cuprinse între 0 și 99. Returnează True dacă datele sunt valide și False altfel.

Funcția rezolvare_problema(cerinta: int, nr_bomboane: int, dimensiuni_bomboane: List[Tuple[int, int]]) -> int rezolvă problema pe baza datelor de intrare și returnează răspunsul. Primește aceleași parametrii ca și validare_date. Pentru cerinta 1, determină numărul de tipuri distincte de bomboane prin însumarea tuturor valorilor nenule din lista bomboane_distincte care reprezintă frecvențele cu care apar perechile de dimensiuni de bomboane distincte. Pentru cerinta 2, determină numărul maxim de cutii de bomboane pe care robotul Vasile le poate obține din bomboanele existente, respectând condițiile din enunț, prin determinarea celei mai mici frecvențe a unei perechi de dimensiuni de bomboane distincte care apar cel puțin o dată.

Funcția main() este funcția principală care citește datele de intrare din fișierul robot.in, apelează funcțiile validare_date și rezolvare_problema, și afișează mesaje corespunzătoare în consolă și în fișierul robot.out în funcție de validitatea datelor de intrare și de răspunsul obținut.