Zadatak: igra

[q]Text zadatka: igra
Mirko i Slavko igraju sledecu igru: na stolu se nalaze n brojeva poredanih u niz. Prvo Mirko uzme jedan broj, sa leve ili sa desne strane niza. Zatim Slavko uzme jedan broj sa leve ili desne strane preostalog niza, i tako naizmenicno dok ne pokupe sve brojeve sa stola. Napisati program koji izracunava, pod pretpostavkom da i Mirko i Slavko igraju optimalno, koliki je maksimalni zbir brojeva koji [color=Red]Slavko [/color]može da skupi.

Sa standardnog ulaza se ucitava u jednom redu broj n (n <= 128), a u drugom redu n brojeva, u opsegu od 0 do 100.

Na standardni izlaz treba ispisate samo jedan broj, maksimalan zbir brojeva koje [color=Red]Mirko [/color]može da osvoji.

Primer:

Ulaz:
4
10 20 1 5

Izlaz:
25[/q]


Nije mi bas skroz jasan zadatak, procitao sam ga nekoliko puta i kako sam shvatio Mirko, odnosno Slavko, ne uzimaju veci od dva broja koji se nalaze na krajevima, nego "gledaju unaprijed" je li bolje uzet veci ili manji da bi kasnije mozda uzeli neki puno veci.

Ako sam dobro shvatio prvo Mirko od 10 20 1 5 uzme 5, onda Slavko od 10 20 1 uzme 10, onda Mirko od 20 1 uzme 20 i Slavko uzme 1?

Mislio sam zadatak rjesit rekurzivno:

void rek (char x)
{
       if (x == 'l')  //sljedeci igrac uzima broj s lijeve strane
       else /* x == 'd' */     //sljedeci igrac uzima broj s desne strane
       
       rek ('l');
       rek('d');
}

...ali mislim da cu ovako dobit da samo jedan igrac igra optimalno, a drugi samo "mu pusta" da uzme sve vece brojeve.

Molim malu pomoc ;D

Zadatak se jednostavno radi tehnikom dinamickog programiranja..

Kada se kaze da obojca igraju optimalno to znaci da ce igrac koji je na redu
uzeti broj tako da je taj_broj + opt_od_ostalih_brojeva najveci..
A opt_od_ostalih_brojeva je u stvari ista igra samo tada pocinje drugi igrac..

Znaci ovde polazimo od pojedinacnih slucajeva ka opstim:
Sracunamo prvo optimalno resenje ako je ostao samo jedan element (i-ti).
Optimalna igra je uzimanje tog i-tog elementa..

U opstem slucaju , kada su ostali brojevi i..j , optimalno resenje ce biti
opt[i][j] = min( opt[i-1][j] + vrednost[i] , opt[i][j-1] + vrednost[j] );
Ako nisi bas upoznat sa dinamickim programiranjem, trebas procitati nesto..
Posle ces razumeti o cemu pricam..Mada, ako se malo potrudis , mozda i sam skontas ,
a to bi bilo i najbolje.

Ulaz:
4
10 20 1 5

Izlaz:
25


ako obojica igraju optimalno, prvi bi uzeo 10, pa drugi 20, pa prvi 5 pa drugi 1 i tako bi dobili zbroj od 21 a ne 25.

znam nesto dinamickog programiranja ali mi i dalje nije jasan skroz zadatak :)

shvatio sam da treba pogledati sve mogucnosti, ali ako to napravim, onda ce se dogoditi slucaj da prvi uzme 10, drugi 5, prvi 20, drugi 1 i onda ce zbroj biti 30???

damn! ;D

Ne trebas probati sve mogucnosti..Kada bi probao sve bio bi prekoracen vremenski limit.

A , kada se kaze da obojica igraju optimalno , to znaci
da ce igrac koji je na redu uzeti broj sa neke strane tako da je maximalna vrednost koju
drugi moze da ostvari od ostatka minimalna..
znaci , ponavljam :

for i := 1 to n opt[i][i] = vrednost[i];

za svako (i,j) gde je i<j :
opt[i][j] = max( vrednost[i] + opt[i+1][j] , opt[i][j-1] + vrednost[j] );
i meni je u pocetku bio nejasan zadatak, ali , uz poznavanje dinamickog programiranja,
razume se sta se trazi..

puno hvala, pokusat cu nesto iskombinirat, pa se opet javim...kad ne uspijem ;D

jas eve probav so nesto kako memoizacija, no sum pocetnik i e mozno da ima greski, pa ako moze ke ve molam komentari za tocnosta i efikasnosta

var i,j,k,l,n,pom1,pom2:integer;
a:array[1..100]of integer;
b:array[1..100,1..100]of integer;
fin,fout:text;
function max(x,y:integer):integer;
begin
     if x>y then max:=x else max:=y;
end;
function min(x,y:integer):integer;
begin
     if x>y then min:=y else min:=x;
end;
procedure resi(i,j:integer);
begin
     if b[i,j]=-1 then
     begin
          if i=j then b[i,j]:=a[i];
          if j-i=1  then b[i,j]:=max(a[i],a[j]) ;
          if j-i>1 then
          begin
               if b[i+2,j]=-1 then resi(i+2,j);
               if b[i+1,j-1]=-1 then resi(i+1,j-1);
               if b[i,j-2]=-1 then resi(i,j-2);
               if b[i+1,j-1]=-1 then resi(i+1,j-1);
               pom1:=a[i]+min(b[i+2,j],b[i+1,j-1]);
               pom2:=a[j]+min(b[i+1,j-1],b[i,j-2]);;
               b[i,j]:=max(pom1,pom2);
          end;
     end;
end;
begin
read(n);
for i:=1 to n do read(a[i]);
for i:=1 to n-1 do
begin
     for j:=i+1 to n do
     b[i,j]:=-1;
end;
resi(1,n);
write(b[1,n]);
end.

Evo moje rjesenje u C++-u:
#include <cstdio>
#include <iostream>
#define MAX 130
using namespace std;
const int inf = 1000000000;
int n, a[MAX], memo[MAX][MAX], sum;
int rek(int from, int to) {
if(from > to) return 0;
if(memo[from][to] != inf) return memo[from][to];
return memo[from][to] = max(a[from] - rek(from+1, to), a[to] - rek(from, to-1));
}
void solve() {
for(int i = 0; i < n; ++i)
for(int j = 0; j < n; ++j) memo[i][j] = inf;
printf("%d", (sum+rek(0, n-1))/2);
//rekurzija vraca koliko vise moze skupiti Slavko pa je potrebno rjesiti sustav jednadzbi da dobijem ukupno
}
void input() {
scanf("%d", &amp;n);
for(int i = 0; i < n; ++i) {scanf("%d", &amp;a[i]); sum+=a[i];}
}
int main() {
input();
solve();
return 0;
}

Stvarno ne razumem ovaj zadatak , poludicu sve sam probao i znam kako ...
Ako moze kod Relja ili neko ko je radio dinamicki a ne rekurzijom?

Mogu ti poslati kood, ali bolje da ti objasnim.
Znachi trenutno imas n brojeva. Imas 2 moguca poteza: da uzmes sa kraja i sa pocetka.
Sad ti kazes ovako: "Ako uzmem sa pocetka/kraja kolika je maximalna suma koju ce protivnik nakupiti optimalnom igrom nadalje sa ostatkom brojeva?". Prema tome ti gledas da izaberes onaj tako da je suma koju ce protivnik posle pokupiti bude sto manja. Znachi, protivnik posle tvoje igre ima istu situaciju s tim sto ima n-1 brojeva i on ima isti problem koji si ti imao u prethodnom potezu. Sada on razmishlja sta da odabere tako da pokupi sto vise (tj da ti od ostatka brojeva, posto on uzme, uzmes sto manju sumu).
Dakle, imas ~n^2 / 2 stanja u kojima se mozes naci - pocetak je u i a kraj u j.

Nadam se da sam ti dao neko usmerenje kako da razmishljas.
Ako opet budes imao problema, javi.
Pozdrav

Ja trenutno radim na trubacima, dali bi mogla proraditi moja ideja memoizacijom tamu?

Ali kako ja znam koja je njegova minimalna a moja maximalna suma, i obratno, moja minimalna a njegova maximalna.
Kako da znam dali da uzmem levi ili desni element? Ili mozda da probam da uzmem i levi i desni pa onda i protivnik da uzme i levi i desni pa ...... aaa to je previse.

Pa, imas neke slucajeve u kojima sigurno znas optimalno resenje.
To je kada na stolu stoji samo 1 broj. Onda ces ti (ili protivnik) uzeti to.
Znatim, prosiris na slucaj sa 2 broja, a za 1 vec imas izracunato. I tako nastavis,
pa mozes za slucaj od n brojeva da iskoristis onaj od n-1 koji si vec izracunao.

Pa zar ne moze svaki broj da bude zadnji na stolu?

Nope , ne razumem , opet pitam , moze kod?

Pa moze svaki broj da bude poslednji na stolu, ali ti isprobavas
sve slucajeve (s tim sto smestas ono sto si vec izracunao da ne bi opet to radio). I na kraju ti ostje ono sto imas na pocetku i to je resenje.

Shaljem ti kod na private, ali nisam siguran da ce ti mnogo koristiti.. Odavno sam ga kucao i tada sam se upoznavao sa dinamickim programiranjem tako da ne znam bas koliko ces ga skontati.
U svakom sluchaju srecno ! :)

A sta se tice do trubacima?

Uf.. pa trubaci su nezgodnije dinamicko.
Mislim, nisu teski kada razmishljas na DP nacin, ali je prilichno zajebano razumeti u suprotnom.
Secam se da mi uopste nije bio jasan zadatak dok nisam skontao nacin DP razmishljanja.
Pogledaj neke teme. Trebalo bi da sam pisao neke hintove. Videcu da iskucam neko objasnjenje kada nadjm vremena.
Poz

Ako mozes da mi objasnis kako radi dinamicko na test primeru.

4
10 20 1 5

Kako bi radio tvoj program?

Ovo su optimalna resenja za igraca koji igra trenutno, a na potezu se nalazi odredjen interval brojeva (koji je naznacen):

[10] - uzece 10. to je optimalno (za [20], [1], [5] je isto)

[10, 20] - uzece 20 i prepustice protivniku 10
[20, 1] - uzece 20 i prepustice protivniku 1
[1, 5] - uzece 5 i prepustice protivniku 1

[10, 20, 1] :
Kaze ovako: ako uzmem 10, onda ce protivnik uzeti optimalno od [20, 1], a ako uzmem 1 onda ce protivnik uzeti optimalno od [10, 20]. Gledam u kom slucaju ce protivnik uzeti manje (meni onda pripada sbir svih trenutno na tabeli minus ono sto ce on uzeti. Dakle to sto treba oduzeti treba biti sto manje).
za [20, 1, 5] je ista prica.

I na kraju posmatras slucaj [10, 20, 1, 5]. Opet kao u prethodnom slucaju: ako uzmem 10 on ce optimalno od [20, 1, 5], a ako uzmem 5 protivnik ce optimalno od [10, 20, 1]. Pa sad gledam u kom slucaju ce manje uzeti. I to ce ti biti ono stanje od koga se krece i dobio si resenje.

Pozdrav,
Treba mi mala uputa oko zadatka igra.
Evo mog rijesenja.

[c]
#include<iostream>
#include<algorithm>
using namespace std;
int *niz;

int main()
{
int n;
int i,j;
int optimal=0;
cin>>n;
niz = new int[n];
for(i=0;i<n;i )cin>>niz[i];
i=0;
j=n-1;
int F=0,S=0;
int F1=0,S1=0;
int value;
bool naredu = true;

// GLAVNI DIO //
while(i-1<j)
{
naredu = !naredu;
F = niz[i];
S = max(niz[i 1],niz[j]);
F1 = niz[j];
S1 = max(niz[i],niz[j-1]);
if( S > S1 ){
value = F1;
j--;
}else if( S < S1){
value = F;
i ;
}else{
if( F > F1){
value = F;
i ;
}else{
value = F1;
j--;
}
}
if(naredu==false)
optimal = value;
///////////////////////////
delete []niz;
cout<<optimal<<endl;
return 0;
}
[c]

Jedini problem je sto neradi xD.
Cilj sam shvatio. Ali neznam da li valja ovaj moj pristup:
Igrac uzima onaj element koji garantuje da ce sljedeci igrac uzeti sto manju vrijednost.

Za svaku pomoc sam zahvalan.

Nisam citao tvoj kod jer mi snalazenje u tudjem kodu nije jaca strana ali probaj da razmisljas ovako:

opt(1,1,n):=min(a[1]+(ukupno-rasporedjeno-a[1]-opt(2,2,n)),a[n]+(ukupno-rasporedjeno-a[n]-opt(2,1,n-1)));

objasnjenje:
opt-rekurzivna funkcija koja trazi optimalno resenje, njeni parametri su(igrac,prvi,poslednji:integer), igrac govori ko je na redu, prvi(odnosno poslednji) govori koji broj pocetnog niza je prvi(odnosno poslednji) u trenutnom nizu. ukupno je zbir svih brojeva a rasporedjeno zbir onih koje si do sad rasporedio. min mislim da znas sta znaci. Sad u prevodu: optimalna igra ovog igraca je ona gde je zbir uzetog elementa i maximuma od preostalih elemenata koji moze da uzme posle igre sledeceg igraca najveci.

Ja mislim da sam ja radio nesto slicno, ne secam se sad.

What is the results for these tests :
1) N=5; 10,1,20,4,7
2) N=7; 8,21,16,9,6,10,11

And this is my code...what's wrong with it..

Var	N,I,J	: Byte;
		B			:	Array[1..128] Of ShortInt;
    Sum 	: Integer;
    T			: ShortInt;

Begin
  ReadLn(N);
  For I:=1 To N Do ReadLn(B[I]);

  T:=1;
  Sum:=0;
  I:=1;
  J:=N;

  While (I<=J) Do Begin
      If B[I+1] + B[J] < B[I] + B[J-1] Then
      	Begin
        	If T=1 Then Sum:=Sum+B[I];
          I:=I+1;
        End
      Else
      	Begin
        	If T=1 Then	Sum:=Sum+B[J];
          J:=J-1;
        End;
      If T=1 Then T:=2 Else T:=1;
  End;

  WriteLn(Sum);
End.

pa pokušaj napravit kao šta je nemanja1990 reko.njegova ideja je odlična

ne razbiram bas ovoj jezik...ali nemozete mi reci u moj kod..sta nije vo red ?

ovako moja ideja:
trebaš se sa 2 fora srest u sredini.
dakle evo malo bolje objašnjenje:
na početku imaš 2 broja x[1] i x[n] (to znači da ih skidaš sa 2 fora) i odmah gledaš x[2] i x[n-1] i onda tražiš optimalno rješenje i pribrojiš ga u sum.
ja se nadam da sam pomogao.ako nešto nije jasno samo pitaj.i ova ideja nije zagarantirana da će proč ograničenje (vremensko naravno)

druze...namesto 2 fora jas imam while so I & J
ali ipak, nesto ne e vo red, samo neznam sta :S
:S