Rezolvare completă PbInfo #2729 SAO

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

Programul va afișa pe ecran numărul V, reprezentând costul cel mai mic pentru a învinge toți cei n monștrii.

Restricții și precizări

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

Exemplu 1:

Intrare

1
10 10
2
9 9 2
11 11 7

Ieșire

7

Explicație

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

Exemplu 2:

Intrare

1
10 10
2
9 9 2
5 5 7

Ieșire

-1

Explicație

Niciuna dintre oferte nu garantează victoria.

Cum e corect?

cout < "As la info"; cout << "As la info"; cout >> "As la info";

Felicitări! Poți mai mult?

Avem sute de probleme pentru tine, fiecare cu explicații ușor de înțeles.

Greșit, dar nu-i bai!

Antrenează-te cu sutele de probleme pe care ți le-am pregătit. Îți explicăm fiecare problemă în parte.

Rezolvare

Iată rezolvarea de 100 de puncte pentru problema SAO:

#include <iostream>

using namespace std;

long long n,rn,rm,x,y,v,mini=-1;

int main(){
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>x>>y;
        rm+=x;
        rn+=y;
    }
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>x>>y>>v;
        if(x>=rn&&y>=rm){
            if(mini==-1){mini=v;}
            else {mini=min(mini,v);}
        }
    }
    cout<<mini;
    return 0;
}

Atenție

Enunțurile afișate pe această pagină aparțin exclusiv site-ului PbInfo. Astfel, pentru ștergerea conținutului, puteți să ne contactați la adresa Adresa de email.

Rezolvarea problemei #2729 SAO

Pe această pagină găsești rezolvarea de 100 de puncte pentru problema #2729 SAO de pe PbInfo.ro. Atenție: nu încurajăm copiatul codului! Totuși, credem cu tărie că analizarea unei soluții corecte este o metodă foarte ușoară de a învăța informatică, astfel că oferim sursele pentru peste 1500 de probleme de pe platforma PbInfo.ro.

Pentru rezolvări PbInfo de la peste 1500 de probleme, vă invităm să intrați pe site-ul nostru!