1000 Taxe2

[•stef2n]

Aici puteti discuta despre problema Taxe2.

[•alexdmotoc]

Problema asta este de backtracking?

[•S7012MY]

Nu, e lee

[•predator5047]

Nu e Lee ci programare dinamica.

[•SpiderMan]

Alexandru, tin sa te anunt la Lee este PROGRAMARE DINAMICA  .

[•vladtarniceru]

se poate face mai rapid cu un bellman-ford sau un dijkstra decat cu un lee, dar merge si asa

[•VisuianMihai]

imi puteti spune si mie va rog cum pot aplica algoritmii de la grafuri la matrici?
Inteleg ca fiecare casuta reprezinta un nod, iar laturile din matrice sunt muchii, dar nu stiu cum sa transpun.
(Sunt nou in asa ceva)

[•PlayLikeNeverB4]

Fiecare nod e reprezentat de o pereche de coordonate (x,y) iar vecinii fiecarui nod sunt (x+1,y),(x,y+1),(x-1,y),(x,y-1). Poti creea o structura care va reprezenta un nod.

[•adistef_radu]

cum se pot downloada fisierele de test? Am incercat de mai multe ori, dar ma duce inapoi la problema si imi apare eroarea : "Nu aveti permisiuni pentru a descarca fisierul grader_test1.in". ma poate ajuta cineva? multumesc anticipat!

[•MciprianM]

Aceasta problema nu permite vizualizarea testelor folosite in evaluarea pe infoarena. Adica nu se poate.
Poti sa vezi, insa, testele folosite la evaluarea de la Olimpiada Judeteana din 2003. Acestea le gasesti in arhiva pentru OJI 2003, din sectiunea Downloads a site-ului.

[•adistef_radu]

Am incercat si arhiva de la oji2003 (http://olimpiada.info/oji2005/index.php?cid=arhiva) dar nu contine nici macar .cpp dar sa mai aiba si testele ...

[•MciprianM]

Aceasta problema nu permite vizualizarea testelor folosite in evaluarea pe infoarena. Adica nu se poate.
Poti sa vezi, insa, testele folosite la evaluarea de la Olimpiada Judeteana din 2003. Acestea le gasesti in arhiva pentru OJI 2003, din sectiunea Downloads a site-ului.

Prin sectiunea Downloads a site-ului m-am referit la site-ul infoarena. Pe pagina principala a site-ului este un meniu care contine optiunea Downloads si care te duce la adresa: http://infoarena.ro/downloads. Acolo gasesti arhiva pentru OJI 2003, la adresa: http://infoarena.ro/downloads?action=download&file=oji2003.zip&safe_only=false
M-am uitat prin arhiva asta pe care ti-am linkat-o si contine, cel putin pentru taxe, solutii oficiale, teste si toate cele. Banuiesc ca e la fel si pentru celelalte probleme.

[•andreii1]

Imi intra in 0.1 s, dar pe 0.05 s iau 80 p. Ma puteti ajuta cu niste optimizari? Acesta este Lee-ul meu:

Cod:

while(p<=u)
    {
        if(!(cost[n][n]>=0&&cost[c[p].x][c[p].y]>=cost[n][n]))
        for(i=1;i<=4;i++)
        {
            x=dx[i]+c[p].x;
            y=dy[i]+c[p].y;
            if(a[x][y]+max(0,cost[c[p].x][c[p].y])<=s&&(cost[x][y]==-1||cost[x][y]>cost[c[p].x][c[p].y]+a[x][y])&&x>=1&&y>=1&&x<=n&&y<=n)
            {cost[x][y]=cost[c[p].x][c[p].y]+a[x][y];c[++u].x=x;c[u].y=y;}
        }
        p++;
    }

[•PlayLikeNeverB4]

Vei avea maximum 10000 de elemente in coada fiindca fiecare va fi o singura data inserat.

[•andreii1]

Oups  , am uitat sa mentionez ca trebuie optimizata din punct de vedere al timpului.. am avut probleme si cu memoria initial tot pe acele teste, dar am rezolvat . Mersi oricum!

[•PlayLikeNeverB4]

Pai daca declari un vector de 10000 de elemente, ia mai putin timp sa-l aloci fata de cum faci tu. Nu sunt chiar separate memoria si timpul. Nu stiu cat imbunatateste timpul, dar oricum e mai bine.

[•soriyn]

Cum ti s-a mai zis timpul de executie e strans legat de memorie. Coada o poti declara char. Incearca asa.

[•andreii1]

Am declarat tot ce s-a putut short int si unsigned char, cat despre lungimea cozii am pus 77900 in urma unei 'cautari binare'. La un numar mai mic, depasea coada pe testul maximal, deoarece exista varfuri ce trebuie adaugate de mai multe ori pentru a determina minimul.. Sigur nu mai pot optimiza, intr-un anumit fel, conditiile de la lee-ul meu?

[•PlayLikeNeverB4]

Am luat 100 cu sursa sa si singurul lucru pe care l-am modificat a fost sa nu mai introduc de mai multe ori aceeasi celula in coada.

[•andreii1]

nu inteleg totusi.. daca avem deja introdus un element pe care, daca il introducem iar, obtinem o solutie mai buna? in sursa mea, introduc doar puncte in conditii optime

[•Sapientia]

Vreo idee de ce iau incorect pe testele 7,9,10? sursa:http://www.infoarena.ro/job_detail/1026018?action=view-source.(LEE)

[•otniel]

#include<iostream>
using namespace std;
#include<stdio.h>
const int x1[4]={1,-1,0,0};
const int y1[4]={0,0,-1,1};
FILE *f,*g;
short int a[161][161],c[161][161],i,j,n,inceput=1,sfarsit=1,s,k;
struct punct
{
    short int ls,ld,d;
};
punct coada [199999999],x,y;
int main()
{
    f=fopen("taxe2.in","r");
    g=fopen("taxe2.out","w");
    fscanf(f,"%hd%hd",&s,&n);
    for(i=1;i<=n;i++)
        for(j=1;j<=n;j++)
           {fscanf(f,"%hd",&a[j]);

    }
    for(i=1;i<=n;i++)
    {
        c[0]=c[n+1]=-1;
        c

• =c[n+1]=-1;

            }
    coada[inceput].ls=coada[inceput].ld=1;
    coada[inceput].d=a[j];
    c[1][1]=a[1][1];
     while(inceput<=sfarsit)
     {
         x=coada[inceput];
         inceput++;
         for(k=0;k<4;k++)
         {
             if(c[x.ls+x1[k]][x.ld+y1[k]]==0)
             {
                 c[x.ls+x1[k]][x.ld+y1[k]]=c[x.ls][x.ld]+a[x.ls+x1[k]][x.ld+y1[k]];
                 y.ls=x.ls+x1[k];
                 y.ld=x.ld+y1[k];
                 sfarsit++;
                 coada[sfarsit]=y;
            }
            else
                if(c[x.ls][x.ld]+a[x.ls+x1[k]][x.ld+y1[k]]<c[x.ls+x1[k]][x.ld+y1[k]])
            {
                c[x.ls+x1[k]][x.ld+y1[k]]=c[x.ls][x.ld]+a[x.ls+x1[k]][x.ld+y1[k]];
                 y.ls=x.ls+x1[k];
                 y.ld=x.ld+y1[k];
                 sfarsit++;
                 coada[sfarsit]=y;
            }
         }
     }
        if(s-c[n][n]>=0)
            fprintf(g,"%hd",s-c[n][n]);
        else
            fprintf(g,"-1");
}
de ce i-au pe testu 7,9,10 killsiegv 11?

[•darkseeker]

Cred ca "i-ei" "killsiegv 11" pe "testu 7,9,10" din cauza felului in care scrii pe forum. In general primesti semnalul ala de eroare in cazul in care intri pe o zona de memorie care nu este alocata, aka depasesti limitele unui vector. In cazul tau, coada de 200 de milioane de elemente s-ar putea sa iti faca probleme de asemenea. Pe viitor inainte sa pui o intrebare asigura-te ca e macar jumatate din ea corecta gramatical.

[•otniel]

si daca reduc dimensiuneile cozii i-au killsiegv si coada are 199 milioane

[•vasica38]

  probleme cu memoria , 640 kbs ii prea putin