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

# 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()