Robot

[•VladBtz]

http://www.olimpiade.ro/materiale/informatica-2013-subiecte-si-bareme-bucuresti-5    Subiectul I

Cod:

#include <iostream>
#include <fstream>
#include <math.h>

using namespace std;

int main()
{int c[200][200], m,n,p,i,j,salvarep=0,v,l,existasolutii=0;
    ifstream f("robot.in");
    f>>p>>m>>n;
    ofstream g("robot.out");
    salvarep=p;
    for(i=1;i<=n;i++)for(j=1;j<=m;j++)f>>c[i][j];
    for(j=1;j<=m;j++)
    {p=salvarep;
    i=1;
        while(p>0)
       {
       l=i;
       v=j;
       if(c[l+1][v]<=c[l+1][v+1]&&c[l+1][v]<c[l+1][v-1])
       {l++;
       p=p- abs(c[l-1][v]-c[l][v]);
       }
       else if(c[l+1][v+1]<=c[l+1][v]&&c[l+1][v+1]<c[l+1][v-1])
       {l++;
       v++;
       p=p-abs(c[l-1][v-1]-c[l][v]);
       }
       else if(c[l+1][v-1]<=c[l+1][v+1]&&c[l+1][v-1]<c[l+1][v])
       {l++;
       v--;
       p=p-abs(c[l-1][v+1]-c[l][v]);
       }
       if(l==n&&p>0){g<<j<<" ";p=-1;existasolutii=1; }



    }
    }
    if(existasolutii==0)g<<"-1";
}

Prima problema este in legatura cu functia abs,care stiam ca se foloseste pentru modulul numarului.Desi am declarat biblioteca math.h (codeblocks) imi apare o eroare "abs wasn't declared in this scope".

[•bogdanboboc97]

abs e in cstdlib
http://www.cplusplus.com/reference/cstdlib/abs/

[•VladBtz]

si cu ce as putea sa o inlocuiesc ca sa aflu modulu?

[•bogdanboboc97]

si cu ce as putea sa o inlocuiesc ca sa aflu modulu?

pui #include <cstdlib> (sau #include <stdlib.h>)
sau faci o functie pt asta

Cod:

int modul(int x)
{
if(x<0)return -x;
else return x;
}

[•VladBtz]

ok multumesc.acum,imi puteti spune ce este in neregula cu codul?


in fisier imi afiseaza -1 pe exemplu,cand ar trebui s aimi afiseze ca sunt solutii si solutiile respective

[•VladBtz]

nimeni?

[•BaTDucK]

while(p>0){
    l=i;
    v=j

Ce este ingrosat isi are locul inainte de while.
Oricum, metoda ta de rezolvare este gresita, problema rezolvandu-se prin programare dinamica. Se va construi alta matrice(sa o numim sol) si in ordine descrescatoare a liniilor, pornind de pe penultima linie sol[ i ][j]=min(sol[i+1][k]+abs(C[ i ][j]-C[i+1][k])), k fiind pe rand j-1, j ,j+1. La urma verificam fiecare element de pe prima linie a matricii nou construite daca este mai mic ca P, asta insemnand ca robotul poate ajunge de acolo pe ultima linie.
Iti las si un cod pentru a intelege mai bine(la cat de bine stiu sa explic...)

Cod:

#include<stdio.h>
#include<algorithm>
using namespace std;
const int Valoare=(1<<30);
int C[205][205],sol[205][205];bool ok;
int modul(int x)
{
    if(x>0) return x;
    return -x;
}
int main()
{
    int N,M,P;
    freopen("robot.in","r",stdin);
    freopen("robot.out","w",stdout);
    scanf("%d%d%d",&P,&N,&M);
    for(int i=1;i<=N;++i)
        for(int j=1;j<=M;++j)
            scanf("%d",&C[i][j]);
    for(int i=0;i<=N+1;++i)
        sol[i][0]=sol[i][M+1]=Valoare;
    for(int i=0;i<=M+1;++i)
        sol[0][i]=sol[N+1][i]=Valoare;
    for(int i=N-1;i;--i)
        for(int j=1;j<=M;++j){
            sol[i][j]=min(sol[i+1][j-1]+modul(C[i][j]-C[i+1][j-1]),min(sol[i+1][j]+modul(C[i][j]-C[i+1][j]),sol[i+1][j+1]+modul(C[i][j]-C[i+1][j+1])));
        }
    for(int i=1;i<=M;++i)
        if(sol[1][i]<P){
            printf("%d ",i);
            ok=1;
        }
    if(!ok)
        printf("-1");
    fclose(stdin);fclose(stdout);
    return 0;
}

[•VladBtz]

Imi pare rau dar nu am invatat ,,programare dinamica" ,functii,siruri de caractere si ce alte lucruri mai apar in codul tau.O alta rezolvare mai simpla ca amterie nu exista.Sa nu uitam totusi ca este vorba de un exercitiu de la faza locala din Bucuresti ,si nu cred ca elevii respectivi au ajuns la asa ceva,chiar daca sunt la intensiv.(poate doar siruri de caractere,dar programare dinamica...)

[•VladBtz]

esti sigur ca numai prin prog dinamica se rezolva.am incercat sa refac putin codul si cred ca e aproape bine ,dar nu stiu cum sa il fac sa o ia din nou pe aceeasi coloana de fiecare data cand se blocheaza in vecini

Cod:

#include <iostream>
#include <fstream>
#include <cstdlib>

using namespace std;
int main()
{
int n,m,j,a[200][200],afisaj=0,gasit,lin,col,ene,x=0;
ifstream f("nrdiv.in");
ofstream g("nrdiv.out");
f>>ene>>n>>m;
for(lin=1;lin<=n;lin++)for(j=1;j<=m;j++)f>>a[lin][j];
x=ene;
for(j=1;j<=m;j++)
{ene=x;
    lin=1;
    col=j;
    gasit=0;
    while(ene>0&&gasit==0)
    {
        if(ene>=abs(a[lin][col]-a[lin+1][col]))
        {
        lin++;
        ene-=abs(a[lin][col]-a[lin+1][col]);
        if(lin==n)gasit=1;
        }
        else if(col-1>=1&&ene>=abs(a[lin][col]-a[lin+1][col-1]))
        {
        lin++;
        ene-=abs(a[lin][col]-a[lin+1][col-1]);
        if(lin==n)gasit=1;
        }
        else if(col+1<=m&&ene>=abs(a[lin][col]-a[lin+1][col+1]))
        {
           lin++;
        ene-=abs(a[lin][col]-a[lin+1][col-1]);
        if(lin==n)gasit=1;
        }
        if (gasit==1)
        {
            g<<j;
            afisaj++;
        }
        else
        {
            if(j==m&&afisaj==0)g<<-1;
        }


    }
}

}

e prob de olimp de clasa a X-a locala,si in cls X nu se invata prog dinamica.si daca spune sa se afiseze o Valoare (de exemplu -1) trebuie sa il pun intre " " sau doar -1 fara ele?Am mai vazut prob de genul la locale(adica coborare si cercetare daca merge drept in fata sau dreapta sau stanga ,tot a 10-a si nu cred ca e cu dinamica.

[•PlayLikeNeverB4]

Codul tau e gresit, nu garanteaza raspunsul optim. Nu se poate fara programare dinamica.

[•klamathix]

Nu te lăsa constrâns de materie/clasă/etc, lucrurile astea sunt aleatoare. Încearcă să-ți analizezi soluția și să demonstrezi că funcționează. Dacă încerci și nu iese, ai măcar o idee de ce nu merge. Apoi poți consulta soluția cu programare dinamică să vezi ce aduce nou și cum rezolvă obstacolele din soluția ta.

[•VladBtz]

asta si incerc

[•VladBtz]

http://campion.edu.ro/arhiva/www/arhiva_2009/seds/7/index.htm


asta poate sa ajute?

Cod:

#include<stdio.h>
#include<algorithm>
using namespace std;
const int Valoare=(1<<30);
int C[205][205],sol[205][205];bool ok;
int modul(int x)
{
    if(x>0) return x;
    return -x;
}
int main()
{
    int N,M,P;
    freopen("robot.in","r",stdin);
    freopen("robot.out","w",stdout);
    scanf("%d%d%d",&P,&N,&M);
    for(int i=1;i<=N;++i)
        for(int j=1;j<=M;++j)
            scanf("%d",&C[i][j]);
    for(int i=0;i<=N+1;++i)
        sol[i][0]=sol[i][M+1]=Valoare;
    for(int i=0;i<=M+1;++i)
        sol[0][i]=sol[N+1][i]=Valoare;
    for(int i=N-1;i;--i)
        for(int j=1;j<=M;++j){
            sol[i][j]=min(sol[i+1][j-1]+modul(C[i][j]-C[i+1][j-1]),min(sol[i+1][j]+modul(C[i][j]-C[i+1][j]),sol[i+1][j+1]+modul(C[i][j]-C[i+1][j+1])));
        }
    for(int i=1;i<=M;++i)
        if(sol[1][i]<P){
            printf("%d ",i);
            ok=1;
        }
    if(!ok)
        printf("-1");
    fclose(stdin);fclose(stdout);
    return 0;
}

am am invatat niste programare dinamica si am niste intrebari despre codul tau :  pot sa pun fstream in loc de stdio si f>> respectiv g<< in loc de printf si scanf?

in partea cu (C[j]-C[i+1][j-1]),min(sol[i+1][j] ce cauta virgula aia acolo?

min ( )  e o functie din biblioteca algorithm?

[•BaTDucK]

1. Nu te opreste nimeni sa folosesti fstream.
2. Trebuie determinat minimul dintre 3 variabile(a,b,c), asa ca determin minimul dintre (b,c) si apoi minimul dintre (a,min(b,c)).
3. Da, min este o functie din biblioteca algorithm.

Te-ar ajuta daca ai considera celula din care pleci radacina unui arbore...

[•VladBtz]

care e treaba cu virgula aia de acolo ?

const int Valoare=(1<<30);  

cont ce face?cu ce pot inlocui << ?

sol

• =sol[M+1]=Valoare;      adica sol i 0 ia valoare lui sol de i m=1 si sol de i m=1 ia valoarea lui Valoare?

[•BaTDucK]

Pai virgula de acolo separa variabilele(ca altfel nici nu stiu cum sa zic), in cazul de fata min(a,min(b,c)).
Variabila 'Valoare' ramane constanta pe tot parcursul programului(nu se poate modifica), tine loc de '#define Valoare ...'.
(1<<30) este echivalent cu 2³⁰.1 in binar este in mod uimitor tot 1, iar <<30(Shift left) muta bitii din reprezentarea binara cu 30 de pozitii in stanga.
Cand vrei sa dai lui a si b aceiasi valoare, poti sa scri in loc de a=val;b=val; doar a=b=val;(b=val si dupa a=b).

[•VladBtz]

cat de important e faza cu bitii in ex?il pot inlocui cu # Define valoare 2^30 ?de ce i-ai dat o valoare asa mare?




if(x>0) return x;
    return -x

al doilea return e de la else ?pot pune cstlib si abs in loc de subprogram?

ai folosit mutarea bitilor ca sa incarci matricea sol?

[•PlayLikeNeverB4]

Bitii nu fac decat sa scrie mai simplu o valoare mare, dar poti scrie si manual un miliard. Trebuie sa fie o valoare mare astfel incat cand faci min(INFINIT, alta_valoare) sa se ia tot timpul alta_valoare.
Al doilea return din functie e un fel de else implicit. Daca intra la if se iese din functie iar daca nu se merge la celalalt return. E echivalent cu abs().
Matricea sol o calculezi cu programare dinamica, nu are legatura cu bitii.

[•VladBtz]

for(int i=0;i<=N+1;++i) sol [ i ][ 0 ] = s o l [ i ] [ M+1]=Valoare;

deci sol [ i ] [m+1] = 2^30; si sol [ i ] [ 0 ] = sol [ i ] [M+1] adica ia valoarea lui 2^30 ?  

[•PlayLikeNeverB4]

Da, ordinea e de la dreapta la stanga.

[•VladBtz]

si de ce a doua amtrice incepe de la 0 pana la coloana +1 ,adica cu 2 mai mult?


const int Valoare=(1<<30);  asta nu face altceva decat sa ridica la putere.cum pot sa ia respectivele valoarea lui Valoare,daca sunt declarate de tip int,adica intru e 32.000 maxim si nr 2 la 30 e imens.

[•PlayLikeNeverB4]

Banuiesc ca voia ca la marginea matricei sa fie INFINIT. Tipuri de date: http://www.tutorialspoint.com/cplusplus/cpp_data_types.htm

[•VladBtz]

 for(int i=0;i<=N+1;++i)
        sol

• =sol[M+1]=Valoare;

   for(int i=0;i<=M+1;++i)
        sol[0]=sol[N+1]=Valoare;

deci aici doar incarca matricea cu infinit (nu doar marginea ia valoarea 2^30 ci si componentele din interior)


 for(int i=N-1;i;--i)   cu i de la N-1 pana la i ,i scade...dar i are valoarea 1 sau?