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

Explicatie

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.