114 - Simulation Wizardry

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

Moderator: Board moderators

User avatar
ezra
New poster
Posts: 31
Joined: Thu Nov 21, 2002 2:11 pm

Post by ezra »

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

Krzysztof Duleba
Guru
Posts: 584
Joined: Thu Jun 19, 2003 3:48 am
Location: Sanok, Poland
Contact:

114, WA - but why?

Post by 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
Guru
Posts: 584
Joined: Thu Jun 19, 2003 3:48 am
Location: Sanok, Poland
Contact:

Post by 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
Guru
Posts: 584
Joined: Thu Jun 19, 2003 3:48 am
Location: Sanok, Poland
Contact:

Post by 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
Guru
Posts: 584
Joined: Thu Jun 19, 2003 3:48 am
Location: Sanok, Poland
Contact:

Post by 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
New poster
Posts: 19
Joined: Sun Aug 17, 2003 2:10 pm

[114] Confusion

Post by 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]
Last edited by Betty on Tue Aug 19, 2003 6:43 am, edited 1 time in total.

xbeanx
Experienced poster
Posts: 114
Joined: Wed Jul 30, 2003 10:30 pm
Location: Newfoundland, Canada (St. John's)

Post by 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
A great helper
Posts: 277
Joined: Mon Jul 21, 2003 7:49 pm
Contact:

Post by UFP2161 »

Those are the correct outputs for those inputs.

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

xbeanx
Experienced poster
Posts: 114
Joined: Wed Jul 30, 2003 10:30 pm
Location: Newfoundland, Canada (St. John's)

Post by xbeanx »

Try searching the board.

Betty
New poster
Posts: 19
Joined: Sun Aug 17, 2003 2:10 pm

Post by Betty »

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

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
Experienced poster
Posts: 114
Joined: Wed Jul 30, 2003 10:30 pm
Location: Newfoundland, Canada (St. John's)

Post by 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
Experienced poster
Posts: 131
Joined: Thu Apr 17, 2003 8:39 am
Location: Baku, Azerbaijan

114 Simulation Wizardry - need help

Post by 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.
_____________
NO sigNature

xbeanx
Experienced poster
Posts: 114
Joined: Wed Jul 30, 2003 10:30 pm
Location: Newfoundland, Canada (St. John's)

Post by 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
Experienced poster
Posts: 131
Joined: Thu Apr 17, 2003 8:39 am
Location: Baku, Azerbaijan

Post by Farid Ahmadov »

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

Almost Human
Learning poster
Posts: 93
Joined: Sun Jan 12, 2003 3:30 pm

114 - Simulation Wizardry - Getting Confused

Post by 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

Post Reply

Return to “Volume 1 (100-199)”