10076 - The Bumpy Robot

All about problems in Volume 100. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

Post Reply
Raziel
New poster
Posts: 7
Joined: Fri Oct 15, 2004 3:43 pm
Contact:

10076 - The Bumpy Robot

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 ?
Wheel weaves as the wheel wishes ...

Raziel
New poster
Posts: 7
Joined: Fri Oct 15, 2004 3:43 pm
Contact:

10076 Time Limit Exceed HELP

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;
}
Wheel weaves as the wheel wishes ...

Raziel
New poster
Posts: 7
Joined: Fri Oct 15, 2004 3:43 pm
Contact:

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?
Wheel weaves as the wheel wishes ...

Raziel
New poster
Posts: 7
Joined: Fri Oct 15, 2004 3:43 pm
Contact:

10076 WA

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);

}
Wheel weaves as the wheel wishes ...

User avatar
sohel
Guru
Posts: 856
Joined: Thu Jan 30, 2003 5:50 am
Location: New York

10076... how is it done.

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. :)

User avatar
little joey
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm

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.

User avatar
sohel
Guru
Posts: 856
Joined: Thu Jan 30, 2003 5:50 am
Location: New York

ooops..

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.

User avatar
little joey
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm

Re: ooops..

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
New poster
Posts: 42
Joined: Sat Oct 21, 2006 8:37 am
Location: Alegrete, Brazil

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...
Thiago Sonego Goulart - UFMG/Brazil

Post Reply

Return to “Volume 100 (10000-10099)”