492 Sudest

[•ucc_5]

Nu sunt sigur dar cred ca exista un caz pe care problema nu il trateaza si care ar face sa nu mai poata fi rezolvata cu dinamica, solutia official devenind ... gresita .
E posibil sa ajunga in aceeasi casuta cu o cantitate maxima din doua directii dar din una dintre directii cu mai putine comenzi efectuate astfel incat in final cea cu mai putine comenzi sa obtina o cantitate mai mare.
Ori in rezolvarea acceptata oficial in cazul in care am ajuns cu o anumita suma, aceea va ramane la fel chiar daca am ajuns cu 100 comenzi acolo, iar din alta directie am ajuns cu 20 de comenzi (caz in care e posibil sa avem un rezultat mai bun).
Mentionez din nou ca nu sunt sigur, dar mie asa mi se pare.

[•skull]

Nu poti ajunge la aceleasi coordonate cu un numar diferit de comenzi.

[•tandura]

As dorii si eu niste teste ca de la atasamente nu am cum sa le iau
Multumesc anticipat 

[•CezarMocan]

Problema a fost propusa la OJI 2006. Daca vrei testele oficiale, poti sa intri pe http://olimpiada.info/oji2006, la sectiunea Subiecte, si sa le descarci de acolo.

[•tandura]

MI se pare mie sau testele sunt gresite  ?
uite un .in  :
__________________________________
16
6 1 0 2 8 2 10 7 4 1 2 3 7 10 7 5
4 5 5 3 6 2 6 2 10 1 0 2 7 3 5 1
3 8 2 0 5 9 3 3 7 1 9 0 6 0 9 3
7 7 9 7 6 9 4 10 5 4 2 10 9 8 6 0
6 4 1 9 7 6 10 2 0 0 0 7 3 5 2 4
3 2 10 7 8 10 7 8 5 0 2 6 6 3 9 0
7 1 3 6 5 0 0 6 8 5 10 0 10 1 7 6
6 6 3 10 4 10 2 10 1 8 9 6 10 4 10 7
4 2 8 10 5 1 7 5 5 8 2 9 6 5 8 5
4 4 5 0 9 4 7 6 8 10 4 1 6 9 5 7
2 1 1 9 7 4 7 7 7 8 2 1 4 3 1 6
4 5 1 7 1 6 5 10 8 7 5 8 2 0 7 3
5 6 3 3 4 6 5 10 1 2 6 6 1 10 7 3
9 10 7 7 4 10 10 6 8 7 6 8 6 7 7 0
9 5 2 5 3 1 5 7 9 6 7 6 7 1 7 6
6 10 8 10 6 9 9 4 4 5 2 0 10 1 2 7
14
5 2 2 1 2 2 1 1 1 2 3 1 5 2
________________________________

Si uite un .out  :
________________________________
-23
105
1 1
6 1
6 3
6 5
6 6
8 6
8 8
9 8
10 8
10 9
12 9
15 9
16 9
16 14
16 16
________________________________

Daca aduni valori pozitive cum sa iti dea suma o valoare negativa ? 
Pe asta chiar nu o inteleg !!

Astept o explicatie de la cineva mai luminat ca mine  de ce ii asa !!

Ms anticipat!

[•robertgbr]

9/10 Erori de signal 11.
Imi puteti spune si mie va rog care poate sa fie motivul?
Test Timp executie Memorie folosita Mesaj Punctaj/test
1 0ms 356kb Killed by signal 11(SIGSEGV). 0
2 0ms 360kb Killed by signal 11(SIGSEGV). 0
3 0ms 364kb Killed by signal 11(SIGSEGV). 0
4 0ms 368kb Killed by signal 11(SIGSEGV). 0
5 0ms 372kb Killed by signal 11(SIGSEGV). 0
6 4ms 380kb Killed by signal 11(SIGSEGV). 0
7 4ms 392kb Killed by signal 11(SIGSEGV). 0
8 4ms 396kb Killed by signal 11(SIGSEGV). 0
9 4ms 384kb Killed by signal 11(SIGSEGV). 0
10 0ms 396kb OKAY! 10

[•tandura]

SIGSEGV mie imi aparea cand imi iesea din ceva vactori sau nu imi citea ceva si atunci mergea asa aiurea pana se hotara sa imi dea eroarea; am observat ca poate fi din cauza unei citiri din fisier.

Incearca sa maresti vectori si / sau tablourile (matricile) si daca nu merge nici asa verifica citirile din fisier daca doresti dami PM si iti voi da niste teste ofisiale de la OJI pe aceasta problema ca sa poti verifica citirea  .

[•mvcl3]

Imi explica si mie cineva ce nu-i in regula cu sursa mea...iau doar ultimul test..
Multumesc!!!

[•taigi100]

Ma chinui de ceva timp si nu inteleg de ce aceasta sursa imi da Memory limit exceeded pe testele 2,3,4.
Am calculat memoria toatala folosita si imi da undeva pe la aprox 110kb ( am luat in considerare si fisierele ).
Singura functie de care nu am tinut cont prea mult ar fi cea recursiva de afisare a coordonatelor dar din cate m-am uitat eu nu ar trebui sa ajunga la un numar atat de mare de copii incat sa depaseasca 640kb. De asemenea pe primul test imi zice ca folosesc 260kb memorie care iarasi nu prea inteleg de unde vine.

Cod:

#include<stdio.h>
int n,m[102][102],k,v[205];
int cpy[102][102];
FILE *g=fopen("sudest.out","w");
struct coord
{
    unsigned char x,y;
} stack[205],omg[102][102];
void PrintStupidCoords(int a,int b)
{
    if(!(a==1 && b==1))
    PrintStupidCoords(omg[a][b].x,omg[a][b].y);
        fprintf(g,"%d %d\n",a,b);
}
void RobysDinamics()
{
    int crt=0,ssize=1,vcrt=1,aux;
    stack[crt].x=stack[crt].y=1;
    m[1][1]=cpy[1][1];
    while((k-vcrt)>-1)
    {
        aux=ssize;
        for(int i=crt;i<aux;i++)
        {
            if( stack[i].x+v[vcrt]<=n && (m[stack[i].x][stack[i].y]+cpy[stack[i].x+v[vcrt]][stack[i].y])>=m[stack[i].x+v[vcrt]][stack[i].y])
            {
                m[stack[i].x+v[vcrt]][stack[i].y]=m[stack[i].x][stack[i].y]+cpy[stack[i].x+v[vcrt]][stack[i].y];
                stack[ssize].x=stack[i].x+v[vcrt];
                stack[ssize].y=stack[i].y;
                omg[stack[i].x+v[vcrt]][stack[i].y].x=stack[i].x;
                omg[stack[i].x+v[vcrt]][stack[i].y].y=stack[i].y;
                ssize++;
            }
            if( stack[i].y+v[vcrt]<=n && (m[stack[i].x][stack[i].y]+cpy[stack[i].x][stack[i].y+v[vcrt]])>=m[stack[i].x][stack[i].y+v[vcrt]])
            {
                m[stack[i].x][stack[i].y+v[vcrt]]=cpy[stack[i].x][stack[i].y+v[vcrt]]+m[stack[i].x][stack[i].y];
                stack[ssize].x=stack[i].x;
                stack[ssize].y=stack[i].y+v[vcrt];
                omg[stack[i].x][stack[i].y+v[vcrt]].x=stack[i].x;
                omg[stack[i].x][stack[i].y+v[vcrt]].y=stack[i].y;
                ssize++;
            }
        }
        crt+=aux-crt;;
      vcrt++;
    }
 
}
int main()
{
    FILE *f=fopen("sudest.in","r");
 
    fscanf(f,"%d",&n);
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            fscanf(f,"%d",&cpy[i][j]);
    fscanf(f,"%d",&k);
    for(int i=1;i<=n;i++)
        fscanf(f,"%d",&v[i]);
    RobysDinamics();
    fprintf(g,"%d\n",m[n][n]);
    PrintStupidCoords(n,n);
}

[•alex_unix]

La prima vedere tind sa cred ca te folosesti de stack la parcurgerea in latime.  Acolo bagi punctele pe care ai ajuns si dupa aceea te extinzi de la ele mai departe. Vad ca folosesti si un v pe acolo... in principiu sursa e brainfuck . Iti zic cum am facut eu si poate asa stii daca ai gresit undeva :
Deci am facut ceva asemanator cu parcurgerea in latime, doar ca mergi numai in sud / est . Am pastrat punctele (coord) intr-o coada de dimensiune 101 * 101 * 2 . Cand reconstituiam drumul era mult mai simplu, ma duceam direct nord-vest pornind de la destinatie. Dinamica o stii tu mai departe . Nu am vazut nimic declarat atat in sursa ta, deci poate aici e greseala. Asta s-ar putea sa fie cauza la SIGSEGV. La MLE s-ar putea sa fie din cauza ca nu se opreste recursiva (a si b sa nu mai ajunga 1) .
Vreo 240 kb vin din cauza bibliotecii <cstdio> , nu au legatura cu sursa ta.

P.S. Cred ca ar trebui sa fie si testele de la OJI pe net. Vezi pe care iti pica.