1203 Robot3

[•andrei.12]

Aici puteti discuta despre problema Robot3.

Multumim Robert Simoiu pentru adaugarea ei.

[•ctlin04]

imi spune si mie cineva cum se poate economisi memorie, pentru ca iau MLE pe trei teste si chiar nu stiu ce sa mai fac

[•S7012MY]

N-am rezolvat problema dar în general la problemele de tipul ăsta e de recomandat să inlocuiești variabilele de tip int cu cele de tip short . Din cauza asta am pierdut 100 p la oji 

[•ctlin04]

mda , se pare ca e gresita fraza-"Cantitatea de energie dintr-o poziţie este un număr natural mai mic sau egal cu 1 000 000", defapt am constatat ca cantitatea de energie dintr-o pozitie este un numar mai mic sau egal cu 100, asa ca pentru cei care au MLE nu va mai chinuiti ore in sir sa vedeti unde puteti face ceva, dar pur si simplu declarati imaginea hartii in felul urmator "a: array [1..1000,1..1000] of 0..100;". SUCCES

[•cosminx2003]

Dupa chinuri groaznice am reusit si eu  .

@catalin cantitatea de energie nu incape pe 8 biti, nici macar pe 16, deci restrictia cu n<=1 000 000 e corecta, am testat eu cu numere de cateva sute de mii si primeam WA pentru int8 si short.

[•ctlin04]

Probabil, dar eu in program nu am folosit nimic mai mult de integer, oricum bine ca ai reusit

[•elfus]

Daca un element din matrice are valoarea >= cu 5000 atunci robotul poate ajunge din acel punct pana la sfarsitul traseului (sunt maxim 5000 de comenzi). Asa ca merge retinuta matricea si short int, iar cand am gasit o valoare >=5000 execut toate comenzile.

Eu zic ca ar merge scazuta limita de memorie la 1024 kbiti, tocmai ca solutia asta sa nu intre. Cel putin solutia mea de la concurs avea O(M) memorie.

L.E. Btw, autorul problemei e domnul Stelian Ciurea. Doar solutia problemei a fost oferita de domnul profesor Marius Nicoli. Eventual puteti sa-l treceti ca si coautor.

[•SpiderMan]

Am schimbat autorul si limita de memorie si am reevaluat.
@cosminx2003, sursa ta ia acum 60 pct., uite-o aici modificata http://infoarena.ro/job_detail/606404 si ia 100 puncte lejer, folosind bitset din STL, foloseste foarte putina memorie, este ca un vector de bool, sau cu vector din STL dinamic, http://infoarena.ro/job_detail/606407, merge mult mai repede .

[•cosminx2003]

Gata, am facut-o acum cu bitset si a scazut memoria folosita de vreo 3 ori .

[•ctlin04]

Daca mi-ar spune cineva cum pot sa micsorez de vreo trei ori memoria in pascal, i-as fi foarte recunoscator

[•SpiderMan]

Nu e buna solutia ta, daca iei settextbuff ai doar 1 MLE, dar ai 2 TLE, deci nicicum nu-i bine. Eu am pe solutia mea (si vad ca si cea oficiala) vreo 300-400 kb maxim, deci gaseste alta solutie, eu am doar vectori .

[•ctlin04]

Mda, mi-a dat ceva batai de cap problema asta, dar pina la urma am scos 240Kb

[•SebiSebi]

De ce imi da eroare daca folosesc functia "sort"? Multumesc anticipat!

[•PlayLikeNeverB4]

#include <algorithm>

[•otniel]

robotul poate acumula energie si din patratelele de langa el sau numai din acelea pe care le parcurge?

[•otniel]

de ce iau numai incorect ca pe testele pe care am incercat merge.Un hint ceva?
#include<iostream>
using namespace std;
#include<fstream>
int n,m,x,y,a[1005][1005],i,j,vr;
long long suma;
char s[5005];
int main()
{
    fstream f("robot3.in");
    ofstream g("robot3.out");
    f>>n;
    f>>m;
    f>>x;
    f>>y;
    for(i=0;i<m;i++)
        f>>s;
    for(i=1;i<=n;i++)
        for(j=1;j<=n;j++)
        f>>a[j];
        suma=a

• [y];

        if(s[0]=='S')
            x++;
        else
            if(s[0]=='E')
            y++;
        else
            if(s[0]=='V')
            y--;
        else
            if(s[0]=='N')
            x--;
 
    for(i=1;i<m;i++)
    {
    suma=(suma+a

• [y])-1;

    if(suma<0)
        {vr=1;
 
        g<<x<<" "<<y;
            break;
        }
        if(s=='S')
            {x++;
            if(suma==0&&suma+a

• [y]==0)

                {
                g<<x-1<<" "<<y;
                vr=1;
                break;}
            }
        else
            if(s=='E')
            {y++;
            if(suma==0&&suma+a

• [y]==0)

                {
                g<<x<<" "<<y-1;
                vr=1;
            break;}
            }
        else
            if(s=='V')
            {y--;
             if(suma==0&&suma+a

• [y]==0)

                {
                g<<x<<" "<<y+1;
                vr=1;
            break;}
            }
        else
            if(s=='N')
            {x--;
             if(suma==0&&suma+a

• [y]==0)

                {
                g<<x+1<<" "<<y;
                vr=1;
            break;}
            }
    }
    if(vr==0)
    {g<<x<<" "<<y;
    }
}