4046 - Parfum

Cerinţa

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

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

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

• 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

Exemplul 1

Intrare

4 20 7

4 5

10 2

6 4

2 10

Ieșire

Datele sunt introduse corect.

2

Exemplul 2

Intrare

2 100 10

10 1

1 10

Ieșire

Datele sunt introduse corect.

10

Exemplul 3

Intrare

5 10 1000000001

3 5

2 1

1 1

7 6

5 3

Ieșire

Datele nu corespund restricțiilor impuse.

Rezolvare

<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>