2729 - SAO

Sursă: [1]

Enunt

Te afli în universul SAO (Sword Art Online pentru necunoscători). Ai la dispoziție o sumă mică de bani și m oferte. Fiecare ofertă constă într-o armură de o anumită rezistență și o sabie de o anumită putere. Tu trebuie să învingi n monștrii ale căror rezistențe și puteri sunt cunoscute. După ce ai învins un monstru, armura ta va pierde din rezistență o valoare egală cu valoarea puterii monstrului, iar sabia va pierde valoarea rezistenței monstrului. Tu vei avea nevoie de setul armură/sabie de o valoare minimă care poate să învingă toți cei n monștri.

Cerinţa

Știind n – numărul de monștri, rezistența și puterea fiecăruia și m – numărul de oferte, cu rezistența armurii, puterea sabiei și prețul, să se determine costul cel mai mic pentru a învinge toți cei n monștri.

Date de intrare

Programul citește de la tastatură numărul n, iar apoi n perechi de numere naturale reprezentând rezistența respectiv puterea fiecărui monstru. Apoi se va citi numărul m și m triplete de numere naturale reprezentând rezistența, puterea și prețul echipamentelor.

Date de ieșire

Dacă datele sunt introduse corect, pe ecran se va afișa: "Datele sunt corecte.". Programul va afișa pe ecran numărul V, reprezentând costul cel mai mic pentru a învinge toți cei n monștrii. În caz contrar, se va afișa pe ecran: "Datele nu sunt comform restricțiilor impuse.".

Restricții și precizări

• 1 ≤ n,m ≤ 10.000
• cele 2*n+3*m numere citite vor fi mai mici sau egale cu 2*63.
• în cazul în care nu poate învinge toți monștrii, se va afișa -1.

Exemple

Exemplu 1

Date de intrare

1

10 10

2

9 9 2

11 11 7

Date de iesire

7

Explicație

Doar cea de-a doua ofertă garantează victoria.

Exemplu 2

Date de intrare

1

10 10

2

9 9 2

5 5 7

Date de iesire

-1

Explicație

Niciuna dintre oferte nu garantează victoria.

Rezolvare

<syntaxhighlight lang="python" line="1"> def citeste_n():

   while True:
       try:
           n = int(input("Introduceti numarul de monștri: "))
           if n >= 1 and n <= 10000:
               print("Datele sunt corecte.")
               return n
           else:
               print("Datele nu sunt conform restrictiilor impuse.")
       except ValueError:
           print("Trebuie introduse doar numere intregi.")

def citeste_monstri(n):

   monstri = []
   for i in range(n):
       while True:
           try:
               rezistenta, putere = map(int, input(
                   "Introduceti rezistența și puterea monștrilor separate prin spatiu: ").split())
               if 1 <= rezistenta <= 2 * 63 and 1 <= putere <= 2 * 63:
                   print("Datele sunt corecte.")
                   monstri.append((rezistenta, putere))
                   break
               else:
                   print("Datele nu sunt conform restrictiilor impuse.")
           except ValueError:
               print("Trebuie introduse doar valori numerice.")
   return monstri

def citeste_m():

   while True:
       try:
           m = int(input("Introduceti numarul de oferte: "))
           if m >= 1 and m <= 10000:
               print("Datele sunt corecte.")
               return m
           else:
               print("Datele nu sunt conform restrictiilor impuse.")
       except ValueError:
           print("Trebuie introduse doar numere intregi.")

def citeste_oferte(m):

   oferte = []
   for i in range(m):
       while True:
           try:
               rezistenta_armura, putere_sabie, pret = map(int, input(
                   "Introduceti rezistența armurii, puterea săbiei și prețul separate prin spatiu: ").split())
               if 1 <= rezistenta_armura <= 2 * 63 and 1 <= putere_sabie <= 2 * 63 and 1 <= pret <= 2 ** 63:
                   print("Datele sunt corecte.")
                   oferte.append((rezistenta_armura, putere_sabie, pret))
                   break
               else:
                   print("Datele nu sunt conform restrictiilor impuse.")
           except ValueError:
               print("Trebuie introduse doar valori numerice.")
   return oferte

def Sao(monstri, oferte):

   # Sortam ofertele in ordine crescatoare dupa pret
   oferte = sorted(oferte, key=lambda x: x[2])

   # Pentru fiecare montru, cautam cea mai ieftina oferta care il poate invinge
   cost_minim = 0
   for i in range(len(monstri)):
       rez_monstru, putere_monstru = monstri[i]
       oferta_potrivita = False
       for j in range(len(oferte)):
           rez_armura, putere_sabie, pret = oferte[j]
           if rez_armura >= putere_monstru and putere_sabie >= rez_monstru:
               cost_minim += pret
               oferta_potrivita = True
               break
       if not oferta_potrivita:
           print(-1)
           return

   print(cost_minim)

if _name_ == '_main_':

   n = citeste_n()
   numere = citeste_monstri(n)
   m = citeste_m()
   numere2 = citeste_oferte(m)
   Sao(numere,numere2)

</syntaxhighlight>

Explicații

Acest cod implementează algoritmul Sao dintr-un joc de strategie, care constă în găsirea celei mai bune oferte pentru a invinge un set de monștri.

Funcția citeste_n() primește de la utilizator numărul de monștri pe care trebuie să îi învingă jucătorul și îl validează. În cazul în care numărul introdus este valid, funcția întoarce acest număr.

Funcția citeste_monstri(n) primește numărul de monștri n și primește de la utilizator caracteristicile fiecărui monstru: rezistența și puterea. Caracteristicile sunt validate, iar în cazul în care datele introduse sunt valide, acestea sunt adăugate într-o listă de monștri, care este returnată la final.

Funcția citeste_m() primește de la utilizator numărul de oferte disponibile și îl validează. În cazul în care numărul introdus este valid, funcția întoarce acest număr.

Funcția citeste_oferte(m) primește numărul de oferte m și primește de la utilizator caracteristicile fiecărei oferte: rezistența armurii, puterea săbiei și prețul. Caracteristicile sunt validate, iar în cazul în care datele introduse sunt valide, acestea sunt adăugate într-o listă de oferte, care este returnată la final.

Funcția Sao(monstri, oferte) primește listele de monștri și oferte, sortează ofertele în ordine crescătoare după preț și pentru fiecare monstru caută cea mai ieftină ofertă care îl poate învinge. Costul minim este calculat prin adunarea prețurilor celor mai bune oferte. Dacă nu există o ofertă potrivită pentru un anumit monstru, se afișează -1. La final, funcția afișează costul minim pentru a învinge toți monștrii.

În funcția principală (if _name_ == '_main_':) sunt apelate funcțiile de citire a datelor (citeste_n(), citeste_monstri(n), citeste_m() și citeste_oferte(m)) și funcția Sao(monstri, oferte) care primește datele citite și afișează rezultatul.