1063 - Arme

Cerința

Într-un joc video, un jucător trebuie să colecteze arme de diferite tipuri pentru a-și îmbunătăți arsenalul. Fiecare tip de armă are o anumită valoare, iar jucătorul dorește să maximizeze suma valorilor armelor colectate, respectând o limită de greutate pe care o poate transporta. Sarcina ta este să implementezi un program care să determine setul optim de arme pe care jucătorul le poate colecta pentru a maximiza valoarea totală, utilizând o metodă greedy.

Date de intrare

Programul citește de la tastatură:

Un număr întreg n reprezentând numărul de tipuri de arme. O listă de n perechi de numere întregi, fiecare pereche reprezentând greutatea și valoarea unei arme. Un număr întreg W reprezentând limita de greutate pe care jucătorul o poate transporta.

Date de ieșire

Pe ecran se va afișa valoarea totală maximă a armelor pe care jucătorul le poate colecta, respectând limita de greutate.

Restricții și precizări

• 1 ⩽ n ⩽ 100
• 1 ⩽ w ⩽ 1000
• Greutatea și valoarea fiecărei arme sunt numere întregi pozitive

Exemplu 1

Intrare

4
2 3
3 4
4 5
5 6
5

Iesire

7

Exemplu 2

Intrare

3
1 1
3 4
4 5
5

Iesire

6

Rezolvare

def citeste_date():
    try:
        n = int(input("Introduceți numărul de tipuri de arme (n): "))
        arme = []
        for _ in range(n):
            greutate, valoare = map(int, input().strip().split())
            arme.append((greutate, valoare))
        W = int(input("Introduceți limita de greutate (W): "))
        return n, arme, W
    except ValueError:
        return None, None, None

def valideaza_date(n, arme, W):
    if not (1 <= n <= 100):
        return False
    if not (1 <= W <= 1000):
        return False
    if not all(isinstance(greutate, int) and isinstance(valoare, int) and greutate > 0 and valoare > 0 for greutate, valoare in arme):
        return False
    return True

def calculeaza_valoare_maxima(n, arme, W):
    arme.sort(key=lambda x: x[1]/x[0], reverse=True)
    greutate_totala = 0
    valoare_totala = 0

    for greutate, valoare in arme:
        if greutate_totala + greutate <= W:
            greutate_totala += greutate
            valoare_totala += valoare
        else:
            break

    return valoare_totala

def main():
    n, arme, W = citeste_date()
    
    if n is None or arme is None or W is None or not valideaza_date(n, arme, W):
        print("Datele de intrare nu corespund restricțiilor impuse.")
        return
    
    print("Datele de intrare corespund restricțiilor impuse.")
    valoare_maxima = calculeaza_valoare_maxima(n, arme, W)
    print(valoare_maxima)

if __name__ == "__main__":
    main()