10076 - The Bumpy Robot

Raziel · Post by **Raziel** » Tue Nov 02, 2004 12:48 pm

I used the input from web :

6 6
1.5 0.2 1
0.2 1.5 1
5 10 20 25 30 43
15 -7 30 34 40 50
20 35 -10 40 45 55
30 35 45 -20 50 57
40 42 48 50 -25 60
50 55 60 63 68 -30
1 1 6 6 200

the answer has to be 112 (its on the web) but my program wrote 110.5... I dont know why, perhaps i must use rounded counting of energy and time ? what data type has to be this two numbers ?

Raziel · Post by **Raziel** » Mon Nov 22, 2004 5:08 pm

Here is my code in c++ is it slow or why have i always this answer please help !

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

int pole[225];

int pole1[225];

int rx=0;
int ry=0;
float alfa1;
float alfa2;
int gamma;
float beta1;
float beta2;
int delta;
int x,y,xt,yt;
int energy;
int celkovycas;

int PosunRobota(int tx,int ty,float &E,float &T){
int pom1,pom2,pom3;
pom2=tx*ry+ty;
if ( (tx<0)||(tx>=rx)||(ty<0)||(ty>=ry) )
return 0;
if (pole1[pom2]==1)
return 0;

pom3=x*ry+y;
if (pole[pom3]>pole[pom2]) {
E=alfa1*(pole[pom3]-pole[pom2]);
pom1=(int )E;
if (pom1<E) E=pom1+1;
T=beta1*(pole[pom3]-pole[pom2]);
pom1=(int)T;
if (pom1<T) T=pom1+1;
E=E+gamma;
T=T+delta;

}
else
if (pole[pom3]==pole[pom2]){
E=gamma;
T=delta;
return 1;
}
else {
E=alfa2*(pole[pom2]-pole[pom3]);
T=beta2*(pole[pom2]-pole[pom3]);
pom1=(int)E;
if (pom1<E) E=pom1+1;
pom1=(int)T;
if (pom1<T) T=pom1+1;
E=E+gamma;
T=T+delta;
}

return 1;
}

void Run(int energie, int cas){
float pomcas,pomen;
int xx=x*ry+y;
if ( (x==xt)&&(y==yt) )
if ((celkovycas>cas)||(celkovycas==0)){
celkovycas=cas;
pole1[ry*x+y]=0;
return;
}

if ((cas>celkovycas)&&(celkovycas!=0)) return;

if (x>xt) {
//x--;
if (PosunRobota(x-1,y,pomen,pomcas)) {
if (energie>=pomen){
x--;
energie-=pomen;
cas+=pomcas;
xx-=ry;
pole1[xx]=1;
Run(energie,cas);
energie+=pomen;
cas-=pomcas;
pole1[xx]=0;
xx+=ry;
x++;

}
}

if (y>yt){
//y--
if (PosunRobota(x,y-1,pomen,pomcas)) {
if (energie>=pomen){
y--;
energie-=pomen;
cas+=pomcas;
xx--;
pole1[xx]=1;
Run(energie,cas);
energie+=pomen;
cas-=pomcas;
pole1[xx]=0;
xx++;
y++;
}
}

//y++
if (PosunRobota(x,y+1,pomen,pomcas)) {
if (energie>=pomen){
y++;
energie-=pomen;
cas+=pomcas;
xx++;
pole1[xx]=1;
Run(energie,cas);
energie+=pomen;
cas-=pomcas;
pole1[xx]=0;
xx--;
y--;
}
}

}
else
if ( (y<yt)||(y==yt) )
{
//y++
if (PosunRobota(x,y+1,pomen,pomcas)) {
if (energie>=pomen){
y++;
energie-=pomen;
cas+=pomcas;
xx++;
pole1[xx]=1;
Run(energie,cas);
energie+=pomen;
cas-=pomcas;
pole1[xx]=0;
xx--;
y--;
}
}

//y--
if (PosunRobota(x,y-1,pomen,pomcas)) {
if (energie>=pomen){
y--;
energie-=pomen;
cas+=pomcas;
xx--;
pole1[xx]=1;
Run(energie,cas);
energie+=pomen;
cas-=pomcas;
pole1[xx]=0;
xx++;
y++;
}
}

}
//x++
if (PosunRobota(x+1,y,pomen,pomcas)) {
if (energie>=pomen){
x++;
energie-=pomen;
cas+=pomcas;
xx+=ry;
pole1[xx]=1;
Run(energie,cas);
energie+=pomen;
cas-=pomcas;
pole1[xx]=0;
xx-=ry;
x--;
}
}

}//x>xt

else
if (x<xt) {
//x++;
if (PosunRobota(x+1,y,pomen,pomcas)) {
if (energie>=pomen){
x++;
energie-=pomen;
cas+=pomcas;
xx+=ry;
pole1[xx]=1;
Run(energie,cas);
energie+=pomen;
cas-=pomcas;
pole1[xx]=0;
xx-=ry;
x--;
}
}

if (y>yt){
//y--
if (PosunRobota(x,y-1,pomen,pomcas)) {
if (energie>=pomen){
y--;
energie-=pomen;
cas+=pomcas;
xx--;
pole1[xx]=1;
Run(energie,cas);
energie+=pomen;
cas-=pomcas;
pole1[xx]=0;
xx++;
y++;
}
}

//y++
if (PosunRobota(x,y+1,pomen,pomcas)) {
if (energie>=pomen){
y++;
energie-=pomen;
cas+=pomcas;
xx++;
pole1[xx]=1;
Run(energie,cas);
energie+=pomen;
cas-=pomcas;
pole1[xx]=0;
xx--;
y--;
}
}

}
else
if ( (y<yt)||(y==yt) )
{
//y++
if (PosunRobota(x,y+1,pomen,pomcas)) {
if (energie>=pomen){
y++;
energie-=pomen;
cas+=pomcas;
xx++;
pole1[xx]=1;
Run(energie,cas);
energie+=pomen;
cas-=pomcas;
pole1[xx]=0;
xx--;
y--;
}
}

//y--
if (PosunRobota(x,y-1,pomen,pomcas)) {
if (energie>=pomen){
y--;
energie-=pomen;
cas+=pomcas;
xx--;
pole1[xx]=1;
Run(energie,cas);
energie+=pomen;
cas-=pomcas;
pole1[xx]=0;
xx++;
y++;
}
}

}
//x--
if (PosunRobota(x-1,y,pomen,pomcas)) {
if (energie>=pomen){
x--;
energie-=pomen;
cas+=pomcas;
xx-=ry;
pole1[xx]=1;
Run(energie,cas);
energie+=pomen;
cas-=pomcas;
pole1[xx]=0;
xx+=ry;
x++;

}
}

}//x<xt

else
if (x==xt) {
if (y>yt){
//y--
if (PosunRobota(x,y-1,pomen,pomcas)) {
if (energie>=pomen){
y--;
energie-=pomen;
cas+=pomcas;
xx--;
pole1[xx]=1;
Run(energie,cas);
energie+=pomen;
cas-=pomcas;
pole1[xx]=0;
xx++;
y++;
}
}

//y++
if (PosunRobota(x,y+1,pomen,pomcas)) {
if (energie>=pomen){
y++;
energie-=pomen;
cas+=pomcas;
xx++;
pole1[xx]=1;
Run(energie,cas);
energie+=pomen;
cas-=pomcas;
pole1[xx]=0;
xx--;
y--;
}
}

}
else
if ( (y<yt)||(y==yt) )
{
//y++
if (PosunRobota(x,y+1,pomen,pomcas)) {
if (energie>=pomen){
y++;
energie-=pomen;
cas+=pomcas;
xx++;
pole1[xx]=1;
Run(energie,cas);
energie+=pomen;
cas-=pomcas;
pole1[xx]=0;
xx--;
y--;
}
}

//y--
if (PosunRobota(x,y-1,pomen,pomcas)) {
if (energie>=pomen){
y--;
energie-=pomen;
cas+=pomcas;
xx--;
pole1[xx]=1;
Run(energie,cas);
energie+=pomen;
cas-=pomcas;
pole1[xx]=0;
xx++;
y++;
}
}

}
//x--
if (PosunRobota(x-1,y,pomen,pomcas)) {
if (energie>=pomen){
x--;
energie-=pomen;
cas+=pomcas;
xx-=ry;
pole1[xx]=1;
Run(energie,cas);
energie+=pomen;
cas-=pomcas;
pole1[xx]=0;
xx+=ry;
x++;

}
}

//x++
if (PosunRobota(x+1,y,pomen,pomcas)) {
if (energie>=pomen){
x++;
energie-=pomen;
cas+=pomcas;
xx+=ry;
pole1[xx]=1;
Run(energie,cas);
energie+=pomen;
cas-=pomcas;
pole1[xx]=0;
xx-=ry;
x--;
}
}

}//x<xt

return;
}

int main(){
int i,j,k,l;
do{
cin>>rx;
cin>>ry;
if (rx==0)
return 0;
cin>>alfa1;
cin>>alfa2;
cin>>gamma;
cin>>beta1;
cin>>beta2;
cin>>delta;
for (i=0;i<rx;i++)
for (j=0;j<ry;j++)
cin>>pole[i*rx+j];
cin>>x;
cin>>y;
cin>>xt;
cin>>yt;
x--;
y--;
xt--;
yt--;
cin>>energy;
celkovycas=0;
k=x;l=y;
i=x-xt;
j=y-yt;
if (i<0) i=-i;
if (j<0) j=-j;
i+=j;
j=(gamma>delta)?delta:gamma;
i=j*i;
if (i>energy) {
cout<<"failed"<<endl;
continue;
}

pole1[ry*x+y]=1;
Run(energy,0);
pole1[ry*k+l]=0;
if (celkovycas!=0)
cout<<celkovycas<<endl;
else cout<<"failed"<<endl;
}while ( (rx!=0)||(ry!=0) );
return 0;
}

Raziel · Post by **Raziel** » Thu Dec 16, 2004 10:13 am

I have another question about this problem ... can have any of those positive integers alfa beta etc value 0?

Raziel · Post by **Raziel** » Tue Jan 04, 2005 4:16 pm

could anyone tell me why WA or send some input that my program will not correctly execute?

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

int zad[225]={
5, 10, 20, 25, 30, 43 ,
15, -7, 30, 34, 40, 50 ,
20, 35, -10, 40, 45, 55,
30, 35, 45, -20, 50, 57,
40, 42, 48, 50, -25, 60,
50, 55, 60, 63, 68, -30,
};

int *pole[201];

int rx;
int ry;
float alfa1=1.5;
float alfa2=0.2;
int gamma=1;
float beta1=0.2;
float beta2=1.5;
int delta=1;
int x=1,y=1,xt=6,yt=6;
int target=xt+yt*rx-1-rx;//cil
int from=x+y*rx-1-rx;//zacatek
int energy=200;

int IsNextTo(int p1,int p2){ //sousedicipolicko
if (p2<0) return 0;
if (p2>=rx*ry) return 0;
if ( (p1/rx)==(p2/rx)) return 1;
if ( (p1%rx)==(p2%rx)) return 1;
return 0;
}

void PosunRobota(int pos1,int pos2,int &En,int &Ti){//vypocet energie a casu
int pom1;
float E,T;

if (zad[pos1]==zad[pos2]){
En=gamma;
Ti=delta;
return;
}
if (zad[pos1]>zad[pos2]) {
E=alfa1*(zad[pos1]-zad[pos2]);
pom1=(int)E;
if (pom1<E) E=pom1+1;
T=beta1*(zad[pos1]-zad[pos2]);
pom1=(int)T;
if (pom1<T) T=pom1+1;
En=E+gamma;
Ti=T+delta;
}
else {
E=alfa2*(zad[pos2]-zad[pos1]);
T=beta2*(zad[pos2]-zad[pos1]);
pom1=(int )E;
if (pom1<E) E=pom1+1;
pom1=(int)T;
if (pom1<T) T=pom1+1;
En=E+gamma;
Ti=T+delta;
}
}

void Run(){
int i,Ene,t1,t2,j;
int En,cas;
int bylo;
for (Ene=0;Ene<=energy;Ene++) {
pole[Ene]=(int*)malloc(sizeof(int)*rx*ry);

if (Ene==0)
for (i=0;i<rx*ry;i++){
if (i!=target)
pole[0]=-10;
else
pole[0]=0;
}
else //ene!=0
for (i=0;i<rx*ry;i++){
if (i==target)
pole[Ene]=0;
else {
t1=-10;
if (IsNextTo(i,i+1)){
PosunRobota(i,i+1,En,cas);
if ((Ene-En)<0) t1=-10;
else
if (pole[Ene-En][i+1]<0) t1=-10;
else t1=pole[Ene-En][i+1]+cas;
}//is next to
if (IsNextTo(i,i-1)){
PosunRobota(i,i-1,En,cas);
if ((Ene-En)<0) t2=-10;
else
if (pole[Ene-En][i-1]<0) t2=-10;
else t2=pole[Ene-En][i-1]+cas;
if ((t1<0)||((t2<t1)&&(t2>0)))
t1=t2;
}
if (IsNextTo(i,i-rx)){
PosunRobota(i,i-rx,En,cas);
if ((Ene-En)<0) t2=-10;
else
if (pole[Ene-En][i-rx]<0) t2=-10;
else t2=pole[Ene-En][i-rx]+cas;
if ((t1<0)||((t2<t1)&&(t2>0)))
t1=t2;
}
if (IsNextTo(i,i+rx)){
PosunRobota(i,i+rx,En,cas);
if ((Ene-En)<0) t2=-10;
else
if (pole[Ene-En][i+rx]<0) t2=-10;
else t2=pole[Ene-En][i+rx]+cas;
if ((t1<0)||((t2<t1)&&(t2>0)))
t1=t2;
}
pole[Ene]=t1;
}//i!=target
}
}//for
}

int main(){
int i;

do {
cin>>rx;
cin>>ry;
if (rx==0)
return 0;
cin>>alfa1;
cin>>alfa2;
cin>>gamma;
cin>>beta1;
cin>>beta2;
cin>>delta;
for (i=0;i<rx*ry;i++)
cin>>zad;
cin>>x;
cin>>y;
cin>>xt;
cin>>yt;
target=xt+yt*rx-1-rx;
from=x+y*rx-1-rx;

cin>>energy;

if ((x==xt)&&(y==yt)) {
cout<<"0"<<endl;
continue;
}
Run();
if (pole[energy][from]<0)
cout<<"failed"<<endl;
else
cout<<pole[energy][from]<<endl;
} while (1);

}

sohel · Post by **sohel** » Sun Mar 13, 2005 12:34 pm

It's strange that there is no previous thread related to this problem..

http://acm.uva.es/p/v100/10076.html

How is the optimization done when there are two parameters involved.
.. is it possible to solve it using bfs or is there other strategy?

I think optimizing time for each node might not lead to a solution since energy parameter is involved as well.
.. there might be no solution if we optimize the time and that means considering the greater time can lead to a solution.

Can someone give a hint or two so that I can at least get started.

little joey · Post by **little joey** » Sun Mar 13, 2005 1:56 pm

Did you notice all energies are integers?

If the problem was to determine the minimum time to get from source to target spending at most Emax energy, then it was an easy problem. You could use a well known greedy algorithm (by a countryman of mine

).

Say you find a minimum using this algorithm, and the path costs Epath <= Emax energy, you could try to find a new path spending at most Epath-1 energy. If you find such a path, and the minimum time is equal to the minimum time of your previous path, you have found a better solution.

sohel · Post by **sohel** » Mon Mar 14, 2005 7:51 am

Little Joey wrote: Did you notice all energies are integers?

Actually no.... I guess I will be needing glasses very soon and a powerful one as well.
.. I can't believe I overlooked the ceil part in the formula.

Well now it's a straight forward problem..
.. you talked about the algo of your countryman( -- he was born in Rotterdam in 1930, right? )
I applied exhaustive bfs() and got AC in 0.776 seconds.

Little Joey also wrote: Say you find a minimum using this algorithm, and the path costs Epath <= Emax energy, you could try to find a new path spending at most Epath-1 energy. If you find such a path, and the minimum time is equal to the minimum time of your previous path, you have found a better solution.

Yeah, I know this thing...
.. but thank you very much, nevertheless.

- But if the energies were not integers, how would you have solved it then.

little joey · Post by **little joey** » Mon Mar 14, 2005 10:38 am

sohel wrote:- But if the energies were not integers, how would you have solved it then.

Binary search, maybe?

tgoulart · Post by **tgoulart** » Mon Jun 25, 2007 6:08 am

little joey wrote:If the problem was to determine the minimum time to get from source to target spending at most Emax energy, then it was an easy problem.

Isn't that what the problem asks for? I read it many times and I can't understand it in another way...

OJ Board

10076 - The Bumpy Robot

10076 - The Bumpy Robot

10076 Time Limit Exceed HELP

10076 WA

10076... how is it done.

ooops..

Re: ooops..