Portal Kombat (omówienie)

03.03.2010

Pierwsza obserwacja jaką warto uczynić - Hektor w każdym momencie powinien walczyć z najsilniejszym przeciwnikiem, którego może pokonać. W p.p. na własne życzenie uzyskałby po walce mniejszy wzrost siły, co mu się oczywiście nie opłaca.

Na podstawie tej obserwacji nietrudno opracować rozwiązanie zadania - wystarczy symulować optymalną grę Hektora wg algorytmu:

Dopoki nie pokonales najsilniejszego przeciwnika

  • Jesli są przeciwnicy, ktorych mozesz pokonac, pokonaj najsilniejszego
  • Jesli nie, wypisz NIE i zakoncz

Wypisz liczbę stoczonych walk

 

W jaki sposób można sprawnie zaprogramować takie rozwiązanie?

Rozwiązanie wzorcowe działa w następujący sposób. Przechodzimy tablicę kolejnych przeciwników (w kolejności podanej na wejściu - od najsłabszego do najsilniejszego). Cały czas utrzymujemy specjalną listę przeciwników, których możemy pobić ( są od nas słabsi a przy tym jeszcze ich nie pokonaliśmy ). Za każdym razem, kiedy napotykamy przeciwnika słabszego od nas, odkładamy go na powyższą listę (nie walczymy z nim od razu zgodnie z obserwacją z pierwszego akapitu - być może potrafimy pokonać kogoś silniejszego).

Jeśli napotkany przeciwnik jest silniejszy od nas, to znak, że przed zmierzeniem się z nim lub kimkolwiek silniejszym musimy zwiększyć swoją siłę. Aby to zrobić pokonujemy przeciwnika, którego dodaliśmy do naszej listy jako ostatniego (czyli najsilniejszego na liście) i usuwamy go z listy. 

Poniżej możesz zobaczyć przykładową implementację ze wspomnianą listą realizowaną przy pomocy struktury STL stack:

 

#include <cstdio>
#include <vector>
#include <algorithm>
#include <stack>

using namespace std;

 int main(){
int lz;
scanf("%d", &lz);
while(lz--){
int skill, n;
scanf("%d%d", &skill, &n);
vector<int> op(n); // sila naszych przeciwników
for(int i =0; i < n;i++) scanf("%d", &op[i]);
stack<int> s; // stos przeciwników słabszych niż my
bool NIE = 0;
int res = 0;
for(int i = 0; i < n && !NIE; i++){
while(skill <= op[i]){ // dopóki jesteśmy za słabi
if(s.empty()){ // nie ma słabszych od nas przeciwników
NIE = 1;
break;
}
else{ // jest słabszy przeciwnik
skill += s.top();
res++;
s.pop();
}
}
s.push(op[i]); // zamiast pokonywać, odkładamy do s.
}
if(NIE) printf("NIE\n");
else printf("%d\n", res+1);
}
return 0;
}

 

Organizatorzy:

Wrocławski Portal Informatyczny Instytut Informatyki Uniwersytet Wrocławski Wrocław

Copyright © 2008-2010 Wrocławski Portal Informatyczny

design: rafalpolito.com