2644 - clase

From Bitnami MediaWiki
Revision as of 22:18, 4 January 2024 by Brianna Waltner (talk | contribs) (Pagină nouă: == Cerinţa == Într-o școală sunt '''n''' clase, fiecare având un număr diferit de elevi. Școală primește '''m''' pachete cu cărți, fiecare cu un număr diferit de cărți. Pentru ca o clasa să primească un pachet, numărul elevilor din acea clasa trebuie să fie egal cu numărul cărților din pachet. Să se determine câte clase primesc un pachet de cărți. == Date de intrare == Fișierul de intrare '''clasein.txt''' va avea pe prima linie numărul '''n''', iar...)
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)

Cerinţa[edit | edit source]

Într-o școală sunt n clase, fiecare având un număr diferit de elevi. Școală primește m pachete cu cărți, fiecare cu un număr diferit de cărți. Pentru ca o clasa să primească un pachet, numărul elevilor din acea clasa trebuie să fie egal cu numărul cărților din pachet. Să se determine câte clase primesc un pachet de cărți.

Date de intrare[edit | edit source]

Fișierul de intrare clasein.txt va avea pe prima linie numărul n, iar pe următoarea linie n numere naturale ordonate crescător, separate prin spații, reprezentând numărul de elevi din fiecare clasa. Pe următoarea linie numărul m, și pe următoarea linie m numere, reprezentând numărul de cărți din fiecare pachet.

Date de ieșire[edit | edit source]

Fișierul de ieșire claseout.txt va conține pe prima linie numărul de clase care primesc pachete cu cărți.

Restricţii şi precizări[edit | edit source]

  • 1 ⩽ n, m ⩽ 10.000
  • într-un pachet sunt maximum 1.000.000.000.000 cărți.
  • într-o clasă sunt maximum 1.000.000.000.000 elevi.

Exemplul 1[edit | edit source]

clasein.txt
5
16 17 20 24 30
4
78 20 17 74
claseout.txt
Datele de intrare corespund restrictiilor impuse
2

Exemplul 2[edit | edit source]

clasein.txt
100000
16 17 20 24 30
4
78 20 17 74
claseout.txt
Datele de intrare nu corespund restrictiilor impuse

Rezolvare[edit | edit source]

<syntaxhighlight lang="python" line> def binary_search(arr, x):

   low = 0
   high = len(arr) - 1
   while low <= high:
       mid = (high + low) // 2
       if arr[mid] < x:
           low = mid + 1
       elif arr[mid] > x:
           high = mid - 1
       else:
           return mid
   return -1

with open('clasein.txt', 'r') as fin:

   n = int(fin.readline().strip())
   if n < 1 or n > 10000:
       print("Datele de intrare nu corespund restrictiilor impuse")
       exit(1)
   students = sorted(list(map(int, fin.readline().split())))
   if any(s < 1 or s > 1000000000000 for s in students):
       print("Datele de intrare nu corespund restrictiilor impuse")
       exit(1)
   m = int(fin.readline().strip())
   if m < 1 or m > 10000:
       print("Datele de intrare nu corespund restrictiilor impuse")
       exit(1)
   books = sorted(list(map(int, fin.readline().split())))
   if any(b < 1 or b > 1000000000000 for b in books):
       print("Datele de intrare nu corespund restrictiilor impuse")
       exit(1)

print("Datele de intrare corespund restrictiilor impuse")

count = 0 for s in students:

   index = binary_search(books, s)
   if index != -1:
       count += 1
       books.pop(index)

with open('claseout.txt', 'w') as fout:

   fout.write(str(count))

</syntaxhighlight>

Explicatie[edit | edit source]

Doar clasa cu 20 de elevi și cea cu 17 elevi vor primi pachete cu cărți.