114 - Simulation Wizardry

[ezra]

thank you very much for your kindness for helping me..

[Krzysztof Duleba]

Hi!

I'm tired with looking into my code and trying to guess what can be wrong. Do I miss anything? Is there any tricky place where I could have made a mistake?

[cpp]#include <iostream>

using namespace std;

typedef struct field
{
int value;
int cost;
bool bumper;
};

class gamestate
{
public:
field table[51][51];
int wall_cost, m,n, ball_x,ball_y, direction,lifetime, points;
void initialize_ball(int a);
void initialize_table();
int simulate();
};

void gamestate::initialize_table()
{
cin>>m; cin>>n;
for(int i=0;i<m;i++)for(int j=0;j<n;j++)
table[j].bumper=table[j].value=table[j].cost=0;
cin>>wall_cost;
int a,b,p; cin>>p;
for(int i=0;i<p;i++)
{
cin>>a;cin>>b;
cin>>table[a].value;
cin>>table[a].cost;
table[a].bumper=true;
}
}

void gamestate::initialize_ball(int a)
{
ball_x=a;cin>>ball_y;cin>>direction;cin>>lifetime;points=0;
}

int gamestate::simulate()
{
lifetime--;
if(lifetime<=0)return points;
int new_x=ball_x, new_y=ball_y;
if(direction==1)new_y++;if(direction==0)new_x++;
if(direction==3)new_y--;if(direction==2)new_x--;

if((new_y>=n)||(new_y<=0)||(new_x<=0)||(new_x>=m))
{
direction=(direction+3)%4;
lifetime-=wall_cost;
if(lifetime<=0)return points;
}
else if(table[new_x][new_y].bumper)
{
direction=(direction+3)%4;
lifetime-=table[new_x][new_y].cost;
points+=table[new_x][new_y].value;
}
else
{
ball_x=new_x;
ball_y=new_y;
}
return simulate();
}


int main()
{
gamestate g;g.initialize_table();
int a,b,c,d,points,total_points=0;
while(cin>>a)
{
g.initialize_ball(a);
points=g.simulate();
cout<<points<<endl;
total_points+=points;
}
cout<<total_points<<endl;
}[/cpp]

[Krzysztof Duleba]

Oh, forget about that code. Just tell me if I draw the example board correctly:

4 WWWWW
3 W O BW
2 W B W
1 W W
0 WWWWW
0 1 2 3 4

W - wall
B - bumper
O - starting position for the balls (the same for all balls in the example).

I think it is the only way to look at the problem to have the answers 0 0 1 2 2 for lifetimes 0 1 2 3 4 5, but it's written clearly that "This describes a cartesian grid where 1 <= x <= m and 1 <= y <= n". In the example it is not the case as points with x or y equal to 4 do not belong to the board.

[Krzysztof Duleba]

Ups, something strange happened to my drawing. Once again:

4 WWWWW
3 W++OBW
2 W+++BW
1 W++++W
0 WWWWW
+ 0 1 2 3 4

+ is an empty space here.

[Krzysztof Duleba]

No one to answer, what a shame. The correct interpretation of the example is the following:

4 WWWW
3 WO B W
2 W+ B W
1 WWWW

with meaning of B,O,W,+ given before.

Regards

[Betty]

I've been trying to do 114 for a while now, it looked so simple when I first read it, however I just can't get it (get WA, had a few timeouts on earlier trials thou) I've read any code I can see on this board that is about 114, but all that code isn't working from what i've read either, and I couldn't any big differences.

If anyone is kind enough to help I'd appreciate it (even if you have sample data, I would make some but I'm guessing that it would work for my program, but not actually be a valid sample)

[cpp]
//@BEGIN_OF_SOURCE_CODE
#include <stdio.h>
#include <string.h>

struct obj{
int cost,value;
};

struct bll{
int x,y,value;
int direction,life;
};

int main(){
char line[1000];
char board[52][52]={0};
int X,Y,WallCost;
int nBumpers;
int total = 0;

scanf("%d %d", &X , &Y);
scanf("%d",&WallCost);
scanf("%d",&nBumpers);

obj bumpers[52][52];

int x1,y1;
int value,cost;
for(int i=0;i<nBumpers;i++){
scanf("%d %d %d %d",&x1,&y1,&value,&cost);
bumpers[y1-1][x1-1].value = value;
bumpers[y1-1][x1-1].cost = cost;
board[y1-1][x1-1]='B';
}

scanf("%d",&y1); //seems to have a \n still in buffer?
bll ball;
while(fgets(line,1000,stdin)){
ball.value=0;
line[strlen(line)-1]=0;
sscanf(line,"%d %d %d %d",&ball.x,&ball.y,&ball.direction,&ball.life);
ball.x--;
ball.y--;
while((--(ball.life))>0){

switch(ball.direction){
case 0:
x1=ball.x+1;
y1=ball.y;
break;
case 1:
y1=ball.y+1;
x1=ball.x;
break;
case 2:
x1=ball.x-1;
y1=ball.y;
break;
case 3:
y1=ball.y-1;
x1=ball.x;
break;
}

if(x1>0&&x1<X-1&&y1>0&&y1<Y-1){
if(board[y1][x1]!='B'){

ball.x=x1;
ball.y=y1;
}else{ //Bumper

if(ball.life>0){
ball.direction=(ball.direction+3)%4;
ball.value+=bumpers[y1][x1].value; ball.life-=bumpers[y1][x1].cost;
}

}
}else{

ball.life-=WallCost;
ball.direction=(ball.direction+3)%4;

}
}
printf("%d\n",ball.value);
total+=ball.value;
}
printf("%d\n",total);

// printf("\n");


return 0;

}


//@END_OF_SOURCE_CODE
[/cpp]

[xbeanx]

Here's some sample input / output.

Code: Select all

50 50
1
11
3 2 0 1
2 10 0 1
3 9 100 1
4 46 1 1
2 47 1 1
25 25 50 10
49 30 0 0
24 2  10  5
30 10 20 20
5 48 1 -2
3 49 1 -1
3 47 2 10
2 9 3 100
5 10 1 1000
25 10 1 1000

And output:

Code: Select all

5
400
534
530
1469

I don't know if this is correct, but my program (which got a WA) gives this output. I found it on a webpage which says it is the correct output.

[UFP2161]

Those are the correct outputs for those inputs.

BTW, you should really remove your Judge ID from the code.. =)

[xbeanx]

Try searching the board.

[Betty]

Hey thanks for the input (and the tip to remove my id )

It turned out that I was misreading the first ball (due to that scanf before the loop without that I was getting an extra ball as there was still a \n in the input buffer before the first ball.)

I was pretty sure my answer was correct as it gave the right answer for everthing I threw at it, although the first ball I always tested on was value 0 anyway, so i never noticed the problem. So I changed the scanf to a fgets (as it gets the \n and doesn't stuff up the first ball)

So I got a nice AC really quick =D

new code
[cpp]
//@BEGIN_OF_SOURCE_CODE

#include <stdio.h>
#include <string.h>

struct obj{
int cost,value;
};

struct bll{
int x,y,value;
int direction,life;
};

int main(){
char line[1000];
char board[52][52]={0};
int X,Y,WallCost;
int nBumpers;
int total = 0;

scanf("%d %d", &X , &Y);
scanf("%d",&WallCost);
scanf("%d",&nBumpers);

obj bumpers[52][52];

int x1,y1;
int value,cost;
for(int i=0;i<nBumpers;i++){
scanf("%d %d %d %d",&x1,&y1,&value,&cost);
bumpers[y1-1][x1-1].value = value;
bumpers[y1-1][x1-1].cost = cost;
board[y1-1][x1-1]='B';
}


bll ball;
fgets(line,1000,stdin);
while(fgets(line,1000,stdin)){
ball.value=0;

sscanf(line,"%d %d %d %d",&ball.x,&ball.y,&ball.direction,&ball.life);

ball.x--;
ball.y--;

while((--(ball.life))>0){

switch(ball.direction){
case 0:
x1=ball.x+1;
y1=ball.y;
break;
case 1:
y1=ball.y+1;
x1=ball.x;
break;
case 2:
x1=ball.x-1;
y1=ball.y;
break;
case 3:
y1=ball.y-1;
x1=ball.x;
break;
}

if(x1>0&&x1<X-1&&y1>0&&y1<Y-1){
if(board[y1][x1]!='B'){

ball.x=x1;
ball.y=y1;
}else{ //Bumper

if(ball.life>0){

ball.direction=(ball.direction+3)%4;
ball.value+=bumpers[y1][x1].value; ball.life-=bumpers[y1][x1].cost;
}

}
}else{

ball.life-=WallCost;
ball.direction=(ball.direction+3)%4;

}
}
printf("%d\n",ball.value);
total+=ball.value;
}
printf("%d\n",total);

// printf("\n");


return 0;

}


//@END_OF_SOURCE_CODE

[/cpp]

[xbeanx]

Nice code.

I was working on this for 2 days, only to find the first program I wrote in about 20 minutes was fine, but instead of starting my counter at 1 I was starting it at 0.

I was very pissed, since it worked with all input I sent at it. Seems like my whole purpose in life is to debug.

[Farid Ahmadov]

Hi. I simulate this game with sample inputs and can't get correct answers.
I cannot understand the problem statement.

Can anyone help to simulate this postion?

Code: Select all

5|wwwww
4|w   w
3|w b w
2|wb +w
1|wwwww
  -----
  12345

w - wall
b - bumper
+ - ball
lifetime of the ball is 10 and direction is 3 (down)
Please show position, lifetime and direction of this ball on every step until it dies.

tnx.

[xbeanx]

I converted your funky diagram into an input file:

Code: Select all

5 5
0
2
2 2 0 0
3 3 0 0
4 2 3 10

Which gives the following output:

Code: Select all

0
0

You did not say what the cost of each bumper was, so I assumed 0.

[Farid Ahmadov]

I have already got AC, just 1 hour after I wrote this topic. Thank you anyway.

[Almost Human]

The ball uses one unit of lifetime for each grid step it moves. It also uses some units of lifetime for each bumper or wall that it hits.

It is said that the ball lose one unit of lifetime only if it move one grid step right ????

so can anybody tell me what will be the input for this ???

3 3
0
4
2 1 0 1
1 2 0 1
3 2 0 1
2 3 0 1
2 2 0 10

thanks