4046 - Parfum

From Bitnami MediaWiki
Revision as of 09:03, 8 April 2023 by Sovago Rares-Andrei (talk | contribs)
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)

Cerinţa[edit | edit source]

Dorești să faci un parfum pentru care vei avea nevoie de X petale de flori. În grădina ta sunt N tipuri de flori, fiecare cu un anumit număr de petale, notat cu count[i]. Odată la T zile, toate florile își vor scutura petalele, urmând ca tu să le colectezi. De asemenea, florile tale au fiecare câte o durată de viață exprimată în zile, notată cu days[i]. Odată ce o floare moare, ea nu mai produce petale. Acum, te ești interesat să găsești valoarea maximă a lui T pentru care s-ar strânge minim X petale de flori după primele Z zile.

Date de intrare[edit | edit source]

Programul citește de la tastatură numerele N, X și Z. Pe umrătoarele N linii se află câte o pereche de valori de forma count[i], days[i].

Date de ieșire[edit | edit source]

Dacă datele sunt introduse corect, pe ecran se va afișa: "Datele sunt introduse corect.", programul va afișa pe valoarea maximă a lui T pentru care se poate produce parfumul după Z zile. În cazul în care datele nu respectă restricțiile, se va afișa pe ecran: "Datele nu corespund restricțiilor impuse.".

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

  • 1 ≤ N ≤ 100 000
  • 1 ≤ count[i] ≤ 1 000 000 000
  • 1 ≤ days[i] ≤ 1 000 000 000
  • 1 ≤ X ≤ 1 000 000 000
  • 1 ≤ Z ≤ 1 000 000 000
  • Se garantează că T maxim este cel mult 1 000 000 000.


Exemple[edit | edit source]

Exemplul 1[edit | edit source]

Intrare
4 20 7
4 5
10 2
6 4
2 10
Ieșire
Datele sunt introduse corect.
2

Exemplul 2[edit | edit source]

Intrare
2 100 10
10 1
1 10
Ieșire
Datele sunt introduse corect.
10

Exemplul 3[edit | edit source]

Intrare
5 10 1000000001
3 5
2 1
1 1
7 6
5 3
Ieșire
Datele nu corespund restricțiilor impuse.



Rezolvare[edit | edit source]

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

  1. 4046 - Parfum

def validare(n, x, z, flowers):

   if not (1 <= n <= 100000 and 1 <= x <= 1000000000 and 1 <= z <= 1000000000):
       return False
   for i in range(n):
       if not (1 <= flowers[i][0] <= 1000000000 and 1 <= flowers[i][1] <= 1000000000):
           return False
   return True


def parfum(n, x, z, flowers):

   tmax = 0
   l = 1
   r = 1000000000
   while l <= r:
       mid = (l + r) // 2
       total_petals = 0
       for i in range(n):
           total_petals += (mid // flowers[i][1]) * flowers[i][0]
       if total_petals >= x * z and mid >= tmax:
           tmax = mid
           l = mid + 1
       else:
           r = mid - 1
   if tmax == 0:
       return -1
   return tmax


def main():

   try:
       n = int(input())
       x, z = map(int, input().split())
       flowers = [list(map(int, input().split())) for _ in range(n)]
   except:
       print("Datele nu corespund formatului cerut.")
       return
   if not validare(n, x, z, flowers):
       print("Datele nu corespund restricțiilor impuse.")
       return
   tmax = parfum(n, x, z, flowers)
   if tmax == -1:
       print("Nu există nicio combinație de flori care să producă atât de mult parfum.")
   else:
       print("Datele sunt introduse corect.")
       print(tmax)


if __name__ == "__main__":

   main()





</syntaxhighlight>

Explicatie[edit | edit source]

Funcția validare(n, x, z, flowers)

Această funcție verifică dacă datele primite ca input sunt valide. Are patru parametri:

n - numărul de flori x - cantitatea minimă de parfum necesară z - cantitatea de parfum produsă de fiecare floare flowers - o listă de n tuple, fiecare tuplă reprezentând o floare. Prima valoare din tuplă reprezintă numărul de petale ale florii, iar a doua valoare reprezintă cantitatea de parfum produsă de floare. Funcția returnează True dacă datele sunt valide și False în caz contrar.

Funcția parfum(n, x, z, flowers)

Această funcție calculează timpul maxim în care poate fi produsă o cantitate minimă de parfum dată. Are patru parametri:

n - numărul de flori x - cantitatea minimă de parfum necesară z - cantitatea de parfum produsă de fiecare floare flowers - o listă de n tuple, fiecare tuplă reprezentând o floare. Prima valoare din tuplă reprezintă numărul de petale ale florii, iar a doua valoare reprezintă cantitatea de parfum produsă de floare. Funcția returnează timpul maxim în care poate fi produsă cantitatea minimă de parfum dată sau -1 dacă nu există nicio combinație de flori care să producă atât de mult parfum.

Funcția main()

Această funcție este funcția principală a programului și este rulată atunci când scriptul Python este executat. Funcția citește datele de intrare de la tastatură, verifică dacă datele sunt valide cu ajutorul funcției validare(), calculează timpul maxim cu ajutorul funcției parfum(), și afișează rezultatul la consolă. Dacă datele de intrare nu corespund formatului cerut, se afișează un mesaj de eroare. Dacă datele nu corespund restricțiilor impuse, se afișează un alt mesaj de eroare.