016 Joc

[•bogdan2412]

Eu luam 30 pct pentru ca gresisem initializarea matricei

[•gabitzish1]

Ziceti-mi si mie cat da pe  :

...

4 6
 2  1  3   4  0   5
 3 -1 -2  0   4 -1
-1 -2 -3 -4 -5 -6
 1  2  3  4   5  6
poate ma prind ce-am gresit.

Multumesc anticipat!

 3 1 6

Nu pricep cum obtine diferenta 3..
Gicu ia 5 (1,6), Nelu 4 (1,4) => dif=1;
Gicu ia 3 (1,3), Nelu 2 (1,1)=> dif=2;
si se termina jocul...

ceea ce e totuna cu: Gicu ia 2(1,1)... si se termina.. e aceasi diferenta.. avand in vedere ca amandoi joaca optim, nu ma prind ce nu am inteles in exemplul respectiv...

[•fireatmyself]

diferenta 3 se obtine astfel: Gicu ia 5 (1,6), Nelu ia 4 (1,4), Gicu ia 2 (1,1). 5+2-4 = 3
prima linie a matricii este si exemplul dat de mircea, al carui raspuns este tot 3 1 6.

LE: strategia dupa care ai incercat sa rezolvi exemplul de mai sus e greedy. problema se rezolva prin programare dinamica (cel putin asa am rezolvat-o eu)

[•ucc_5]

Nu inteleg deloc de ce nu merge testul 8. Algoritmul meu memoreaza in sol[ i ][ j ] - maximul  pana la (i,j) (desigur memorez undeva solutia ca sa fie pe lina si coloana potrivita). sol[ i ][ j ]=max(sol[ i-1 ][ j ],sol[ i ][ j-1 ],a[ i ][ j ]-sol[ i ][ j-1 ],a[ i ][ j ]-sol[ i-1 ][ j ]).
Teoretic ar trebui sa mearga perfect.
Ba chiar arata si greseala din exemplul lui domino (vad ca nu a mentionat nimeni, pentru primul test solutia e 3 2 4 nu 3 2 6).

[•Mitza444]

Chiar nu am nici o idee de rezolvare ,ma puteti ajuta cu niste indicatii??

[•SpiderMan]

Chiar esti orb ? Pe bune acum, rezolvarea este exact cu un post mai sus, si minune e si corecta  .

[•ion824]

Cat va da pentru testul respectiv?
1 2
-5 -5

[•SpiderMan]

Cod:

0 1 2

[•ion824]

Intuieste cineva ce are testul 8 ? Solutia mea e asemanatoare cu cea descrisa de usurelu catalin .

[•thesilverhand13]

 @ Ursuletul Catalin: pentru acel test a lui Domino,raspunsul este chiar 3 2 6  ....

[•swim406]

Cod:

for (i = 1; i <= N; ++i)
	for (j = 1; j <= M; ++j)
		maxmat[i][j] = best[1][1];

...

Cod:

if (best[i][j] > maxmat[i][j]) 
		for (k = i; k <= N; ++k)
			for (l = j; l <= M; ++l)
				maxmat[k][l] = best[i][j];

Iau 80 de puncte cu WA pe 6 si 9, si am ajuns la concluzia ca este din cauza maximului. Asta este bucata unde lucrez cu maximul... Nu imi dau seama de greseala nicidecum. Sa fie altceva?

[•new_programmer]

Va rog foarte frumos sa mentionati in restrictiile problemei ca diferenta de scor inseamna scor Gicu - scor Nicu. Cuvantul "diferenta" are o alta semnificatie decat cea pe care o are in enunt. Am pierdut foarte mult timp si nu as vrea sa piarda si altii.

[•pauldb]

Diferenta: vezi prima definitie, semnificatia 2.

[•wefgef]

Citeste primele doua comentarii din acest topic. Enuntul este destul de clar.

[•DorelBarbu]

Va rog, ar putea posta cineva o mica explicatie a relatiei de reucrenta? d[ i][j] = diferenta maximace poate fi obtinuta in dreptunghiul incadrat de pozitia (1,1) si (i,j). Eu asa m-am gandit, dar nu ma prind cum sa continui. Am vazutca intr-adevar, si altii au facut asa. Mi-ar prinde bine un hint. multumesc in avans!

[•Vlad_lsc2008]

Ok...nu pot sa trec peste 60 de punte orice as face. Ma poate ajuta cineva?

[•Vlad_lsc2008]

Nevermind....era o greseala stupida....

[•mihai.alpha]

Problema asta ma dispera. Am facut cu programare dinamica si tot imi da 70 de puncte, cu testele 6, 8, 9 WA. Uitati codul:

Cod:

#include <bits/stdc++.h>

#define Max 1004

FILE *fin, *fout;
int N, M;
int a[Max][Max];
int maxi[Max][Max], sol[Max][Max];

inline int smax(int a, int b)  {
    if(a > b)
        return a;

    return b;
}


int main()  {
    fin = fopen("joc.in", "r");
    fout = fopen("joc.out", "w");

    int s;

    fscanf(fin, "%d%d", &N, &M);

    for(int i = 1;i <= N;i++)
        for(int j = 1;j <= M;j++)
            fscanf(fin, "%d", &a[j]);
    int ri, rj;

    s = a[1][1];
    ri = 1, rj = 1, maxi[1][1] = a[1][1];
    sol[1][1] = a[1][1];
    maxi[1][2] = a[1][1];
    maxi[2][1] = a[1][1];


    for(int i = 1;i <= N;i++)
        for(int j = 1;j <= M;j++)  {
            if(i == 1 && j == 1)
                continue;
            sol[j] = a[j] - maxi[j];
            maxi[j] = smax(maxi[j], sol[j]);
            maxi[j + 1] = maxi[j];
            maxi[i + 1][j] = maxi[j];
            maxi[i + 1][j + 1] = maxi[j];
            if(sol[j] > s)
                s = sol[j], ri = i, rj = j;
        }

    fprintf(fout, "%d %d %d", s, ri, rj);

    fclose(fin);
    fclose(fout);

    return 0;
}

Later edit:

Am luat 100p. Am refacut dinamica si a mers

[•FlorinHaja]

De ce nu e diferența maximă 10? Rețin o matrice smax[2][ i][j] , în care rețin soluția maximă pe care o obțin având ultimul jucător Gicu (pt. rândul 0) sau Nicu (pt. rândul 1). Gicu poate lua jetoanele de valoare 5, 4 și 2, iar Nicu cele de valoare 0 și 1.

[•andrei.arnautu]

Presupunand ca fiecare din cei doi joaca optim

Pe cazul din exemplu se intampla ceea ce este scris la explicatii, mai jos de enunt.

Ideea este ca primul jucator vrea sa maximizeze diferenta, iar cel de-al doilea urmareste sa o minimizeze, asta inseamna ca "amandoi joaca optim".

[•PatrickCplusplus]

Daca am matricea 6 1 2 3 4 7 Gicu alege 7 sau 6 ?

[•PatrickCplusplus]

Never mind, am inteles!