114 - Simulation Wizardry

Moderator: Board moderators

FlyDeath
Learning poster
Posts: 73
Joined: Wed Jan 02, 2002 2:00 am
Location: Taiwan
It says " The value and cost may be any integer (i.e., they may be negative; a negative cost adds lifetime to a ball that hits the bumper)."
Will it be an endless loop?
Because I get TLE,and i really don't know why
.I gave it 10000 life and it finished immediately.Maybe there is something wrong with my code:

Code: Select all

#include <stdio.h>

class bumper
{
public:
int value;
int cost;
};

void main()
{
int i=0,j=0;
bumper allbumper[51][51];
bool hb[51][51];
int top=0,right=0;
int hwcost=0;
int bumpers=0;
int exit=0;
int x=0,y=0,life=0,way=0;
int value=0;
int total=0;
int flag=0;
int tx,ty;
scanf("%d %d",&right,&top);
right--;
top--;
scanf("%d",&hwcost);
scanf("%d",&bumpers);
for(i=0;i<51;i++)
for(j=0;j<51;j++)
hb[i][j]=0;
for(i=0;i<bumpers;i++)
{
scanf("%d %d",&tx,&ty);
scanf("%d %d",&allbumper[tx][ty].value,&allbumper[tx][ty].cost);
hb[tx][ty]=1;
}
while(scanf("%d %d %d %d",&x,&y,&way,&life)!=EOF)
{
value=0;
do
{
exit=0;
flag=0;
switch(way)
{
case 0:
life--;
if(life==0)
{
exit=1;
printf("%dn",value);
break;
}
if(x+1>right)
{
way=(way+3)%4;
if(life>hwcost)
{
life=life-hwcost;
break;
}
else
{
exit=1;
printf("%dn",value);
break;
}
}
else
{
for(i=0;i<bumpers;i++)
{
if(hb[x+1][y]==1)
{
flag=1;
way=(way+3)%4;
if(life<allbumper[x+1][y].cost)
{
exit=1;
printf("%dn",value);
break;
}
else if(life==allbumper[x+1][y].cost)
{
value=value+allbumper[x+1][y].value;
printf("%dn",value);
exit=1;
break;
}
else if(life>allbumper[x+1][y].cost)
{
life=life-allbumper[x+1][y].cost;
value=allbumper[x+1][y].value+value;
break;
}
}
}
if(flag==0)
x++;
break;
}
case 1:
life--;
if(life==0)
{
exit=1;
printf("%dn",value);
break;
}
if(y+1>top)
{
way=(way+3)%4;
if(life>hwcost)
{
life=life-hwcost;
break;
}
else
{
exit=1;
printf("%dn",value);
break;
}
}
else
{
for(i=0;i<bumpers;i++)
{
if(hb[x][y+1]==1)
{
flag=1;
way=(way+3)%4;
if(life<allbumper[x][y+1].cost)
{
exit=1;
printf("%dn",value);
break;
}
else if(life==allbumper[x][y+1].cost)
{
value=value+allbumper[x][y+1].value;
printf("%dn",value);
exit=1;
break;
}
else if(life>allbumper[x][y+1].cost)
{
life=life-allbumper[x][y+1].cost;
value=allbumper[x][y+1].value+value;
break;
}
}
}
if(flag==0)
y++;
break;
}
case 2:
life--;
if(life==0)
{
exit=1;
printf("%dn",value);
break;
}
if(x-1<0)
{
way=(way+3)%4;
if(life>hwcost)
{
life=life-hwcost;
break;
}
else
{
exit=1;
printf("%dn",value);
break;
}
}
else
{
for(i=0;i<bumpers;i++)
{
if(hb[x-1][y]==1)
{
flag=1;
way=(way+3)%4;
if(life<allbumper[x-1][y].cost)
{
exit=1;
printf("%dn",value);
break;
}
else if(life==allbumper[x-1][y].cost)
{
value=value+allbumper[x-1][y].value;
printf("%dn",value);
exit=1;
break;
}
else if(life>allbumper[x-1][y].cost)
{
life=life-allbumper[x-1][y].cost;
value=allbumper[x-1][y].value+value;
break;
}
}
}
if(flag==0)
x--;
break;
}
case 3:
life--;
if(life==0)
{
exit=1;
printf("%dn",value);
break;
}
if(y-1<0)
{
way=(way+3)%4;
if(life>hwcost)
{
life=life-hwcost;
break;
}
else
{
exit=1;
printf("%dn",value);
break;
}
}
else
{
for(i=0;i<bumpers;i++)
{
if(hb[x][y-1]==1)
{
flag=1;
way=(way+3)%4;
if(life<allbumper[x][y-1].cost)
{
exit=1;
printf("%dn",value);
break;
}
else if(life==allbumper[x][y-1].cost)
{
value=value+allbumper[x][y-1].value;
printf("%dn",value);
exit=1;
break;
}
else if(life>allbumper[x][y-1].cost)
{
life=life-allbumper[x][y-1].cost;
value=allbumper[x][y-1].value+value;
break;
}
}
}
if(flag==0)
y--;
break;
}
}
}while(exit==0);
total=total+value;
}
printf("%dn",total);
}

C8H10N4O2
Experienced poster
Posts: 137
Joined: Wed Feb 27, 2002 2:00 am
Read the problem carefully. A hit scores points if the ball does not die before moving to the square. Thus, if you have a ball with Life 2 and a Bumper of Cost 10, the ball still scores. Deduct 1 for the move and if still alive (Life>0) then you get a hit no matter what the bumper cost is. The bumper cost is only for rebounds.

FlyDeath
Learning poster
Posts: 73
Joined: Wed Jan 02, 2002 2:00 am
Location: Taiwan
I fixed my code and get its more clear ,but I still get WA.I'm sure my program can handle the problem you post this time.Is there any special test case,or there is something I don't know?

Code: Select all

#include <stdio.h>
#define RIGHT 0
#define UP 1
#define LEFT 2
#define DOWN 3

int vboard[52][52];
int cboard[52][52];
bool map[52][52];

void main()
{
int bumpers;
int i,j;
int tmpx,tmpy;
long life;
int dir;
int wallcost;
int nextx,nexty;
int nowx,nowy;
long score;
long total=0;
#ifndef ONLINE_JUDGE
freopen("in.txt","r",stdin);
freopen("out.txt","w",stdout);
#endif
scanf("%d %d",&tmpx,&tmpy);
scanf("%d",&wallcost);
scanf("%d",&bumpers);
for(i=0;i<52;i++)
{
for(j=0;j<52;j++)
{
vboard[i][j]=0;
cboard[i][j]=0;
map[i][j]=0;
}
}
for(i=0;i<=tmpx+1;i++)
{
cboard[i][0]=wallcost;
map[i][0]=1;
cboard[i][tmpy+1]=wallcost;
map[i][tmpy+1]=1;
}
for(i=0;i<=tmpy+1;i++)
{
cboard[0][i]=0;
map[0][i]=1;
cboard[tmpx+1][i]=0;
map[tmpx+1][i]=1;
}
for(i=0;i<bumpers;i++)
{
scanf("%d %d",&tmpx,&tmpy);
map[tmpx+1][tmpy+1]=1;
scanf("%d",&vboard[tmpx+1][tmpy+1]);
scanf("%d",&cboard[tmpx+1][tmpy+1]);
}
while(scanf("%d %d %d %ld",&nowx,&nowy,&dir,&life)!=EOF)
{
score=0;
nowx++;
nowy++;
while(1)
{
nextx=nowx;
nexty=nowy;
if(dir==RIGHT)
nextx=nowx+1;
else if(dir==UP)
nexty=nowy+1;
else if(dir==LEFT)
nextx=nowx-1;
else if(dir==DOWN)
nexty=nowy-1;
life--;
if(life==0)
{
total=total+score;
printf("%ldn",score);
break;
}
if(map[nextx][nexty]==1)
{
if(dir==RIGHT)
dir=DOWN;
else if(dir==UP)
dir=RIGHT;
else if(dir==LEFT)
dir=UP;
else if(dir==DOWN)
dir=LEFT;
life=life-cboard[nextx][nexty];
score=score+vboard[nextx][nexty];
if(life<=0)
{
total=total+score;
printf("%ldn",score);
break;
}
}
else
{
nowx=nextx;
nowy=nexty;
}
}
}
printf("%ldn",total);
}

C8H10N4O2
Experienced poster
Posts: 137
Joined: Wed Feb 27, 2002 2:00 am
Um, quick examination of your code reveals:

Code: Select all

for(i=0;i<=tmpx+1;i++)
{
cboard[i][0]=wallcost;
map[i][0]=1;
cboard[i][tmpy+1]=wallcost;
map[i][tmpy+1]=1;
}
for(i=0;i<=tmpy+1;i++)
{
cboard[0][i]=0;
map[0][i]=1;
cboard[tmpx+1][i]=0;
map[tmpx+1][i]=1;
}
Notice how you set 2 walls to wallcost and leave 2 walls at 0. I think that's a bug:o)

Caesum
Experienced poster
Posts: 225
Joined: Fri May 03, 2002 12:14 am
Location: UK
Contact:
so what happens when your life is 1 and you then move and hit a bumper with a negative cost ? Life becomes 0 so you dont score ? but the cost is negative so your life becomes positive again ?

skylander
New poster
Posts: 13
Joined: Mon Jun 10, 2002 3:24 pm
Contact:

114 - Simulation Wizardry

the judge gave me WA but it worked well with the sample inputs...and some of my own inputs

[cpp]
/* @BEGIN_OF_SOURCE_CODE */

#include <iostream.h>

const int MAP_SIZE = 56;

typedef struct MAPTYPE {
bool canWalk;
int cost, value;
} MapType;

/* Function Prototypes */
void createMap(int, int, int);
void createBumper(int, int, int, int);
int playBall(int, int, int, int);
void printBall(int, int);

/* Variable Declarations */
MapType map[MAP_SIZE][MAP_SIZE];
int mapRow, mapCol;

/* main() */

int main(void) {
int wallCost, bumperCount;
int bumperX, bumperY, bumperValue, bumperCost;
int ballX, ballY, ballDirect, ballLife;
int score, totalScore;
int i;

fileio(OPEN);

cin >> mapRow >> mapCol >> wallCost;
createMap(mapRow, mapCol, wallCost);

cin >> bumperCount;

for(i=0;i<bumperCount;i++) {
cin >> bumperX >> bumperY >> bumperValue >> bumperCost;
createBumper(bumperX, bumperY, bumperValue, bumperCost);
}

totalScore = 0;
//printBall(-1, -1);
//return 0;

while(!cin.eof()) {
cin >> ballX >> ballY >> ballDirect >> ballLife;

if(cin.eof())
break;

score = playBall(ballX - 1, ballY - 1, ballDirect, ballLife);
totalScore += score;
cout << score << endl;
}

cout << totalScore << endl;

fileio(CLOSE);

return 0;
}

/* Functions Definitions */
void createMap(int sizex, int sizey, int cost) {
int i, j;

for(i=1;i<=sizex;i++)
for(j=1;j<=sizey;j++) {
map[j].canWalk = true;
map[j].cost = cost;
map[j].value = 0;
}

for(i=0;i<sizex;i++) {
map[0].canWalk = false;
map[sizey].canWalk = false;
map[0].cost = cost + 1;
map[sizey].cost = cost + 1;
}

for(i=0;i<sizey;i++) {
map[0].canWalk = false;
map[sizex].canWalk = false;
map[0].cost = cost + 1;
map[i][sizex].cost = cost + 1;
}
}

void createBumper(int x, int y, int value, int cost) {
map[mapRow - y][x - 1].value = value;
map[mapRow - y][x - 1].cost = cost + 1;
map[mapRow - y][x - 1].canWalk = false;
}

int playBall(int x, int y, int dir, int life) {
int score;
int oX, oY;
int bX, bY, bD, bL;
bool ballHit;

bX = x;
bY = y;
bD = dir;
bL = life;
score = 0;

while(bL > 0) {
oX = bX;
oY = bY;

switch(bD) {
case 0:
bX++;
break;
case 1:
bY++;
break;
case 2:
bX--;
break;
case 3:
bY--;
break;
}

if(map[mapRow - bY - 1][bX].canWalk) {
bL--;
} else {
if(bL > 1) {
bL -= map[mapRow - bY - 1][bX].cost;
score += map[mapRow - bY - 1][bX].value;
bX = oX;
bY = oY;
bD += 3;
bD %= 4;
}
}

/* printBall(bX, bY);
cout << "X: " << bX << " Y: " << bY << " L: " << bL << " D: " << bD;
cout << endl;*/
}

return score;
}

void printBall(int x, int y) {
int i, j;

//cout << (mapRow - y - 2);
for(i=0;i<mapRow;i++) {
for(int j=0;j<mapCol;j++) {
if(i == (mapRow - y - 1) && j == x) {
cout << "B";
} else {
if(map[i][j].canWalk)
cout << "*";
else
cout << "X";
}
}
cout << endl;
}

}

/* @END_OF_SOURCE_CODE */

[/cpp]

thx

wyvmak
Experienced poster
Posts: 110
Joined: Thu Dec 13, 2001 2:00 am
i cannot totally understand your code, but two things suspicious:

1. if(bL > 1) {
why not if(bL>=1)

2. why .cost = cost + 1

but maybe more important thing is,
minus bL first,
if bL<=0, then no score can be gained

Joe Smith
New poster
Posts: 26
Joined: Wed Apr 17, 2002 5:56 am

114 Simulation Wizardry (infinite loop)

I'm getting an infinite loop on this one. The problem statement is totally unclear. It's easy to see how an infinite loop could be caused... but since I can't understand the problem description, I have no idea what's wrong.
Is it possible to have a bumper on the edge, where I'm assuming there's a wall? Is it possible for more than one bumper to be in a square?

If anyone can see the problem in my code and point it out it would be appreciated.

[cpp]
const int dir_x[] = { 1, 0, -1, 0 };
const int dir_y[] = { 0, 1, 0, -1 };

struct Bumper {
int x, y, val, cost;
};

int m, n, wallcost, p, x, y, dir, lifetime;
Bumper b[3000];

int main()
{
scanf("%d %d %d %d", &m, &n, &wallcost, &p);
for (int i=0; i<p; i++) {
scanf("%d %d %d %d", &b.x, &b.y, &b.val, &b.cost);
}

int total=0;
while (scanf("%d %d %d %d", &x, &y, &dir, &lifetime)==4) {
int score=0;
for (;;) {
if (x+dir_x[dir]==1 || x+dir_x[dir]==m) {
dir = (dir+3)%4;
} else if (y+dir_y[dir]==1 || y+dir_y[dir]==n) {
dir = (dir+3)%4;
} else {
bool hit=false;
for (int i=0; i<p; i++) {
if (x+dir_x[dir]==b.x && y+dir_y[dir]==b.y) {
score += b.val;
dir = (dir+3)%4;
}
}
if (!hit) {
x += dir_x[dir];
y += dir_y[dir];
}
}
}
printf("%d\n", score);
total += score;
}
printf("%d\n", total);
}
[/cpp]

Ivan Golubev
Experienced poster
Posts: 167
Joined: Fri Oct 19, 2001 2:00 am
Location: Saint Petersburg, Russia

Code: Select all

for (int i=0; i<p; i++) {
if (x+dir_x[dir]==b[i].x && y+dir_y[dir]==b[i].y) {
...
You're getting overall complexity of O((numbers of bumpers)*(numbers of moves)) and it can be very large value. There is a way to check the collision of bumber and ball instantly.

And AFAIR there no problems with input.

Joe Smith
New poster
Posts: 26
Joined: Wed Apr 17, 2002 5:56 am
Ivan Golubev wrote:Your problem is here:

Code: Select all

for (int i=0; i<p; i++) {
if (x+dir_x[dir]==b[i].x && y+dir_y[dir]==b[i].y) {
...
You're getting overall complexity of O((numbers of bumpers)*(numbers of moves)) and it can be very large value. There is a way to check the collision of bumber and ball instantly.

And AFAIR there no problems with input.
Ah yes... very careless. I fixed it and it works now! Thank you!

Archangel
New poster
Posts: 29
Joined: Wed Jun 26, 2002 9:00 am

Does this problem have any special test case to let me get WA?

PMNOX
New poster
Posts: 49
Joined: Wed Feb 13, 2002 2:00 am
Location: Poland
Contact:
can you post your source code, i'll check it, i already have source code, but i also get WA
[cpp]#include <iostream.h>
struct pinball
{
bool bouncer;
int value;
int cost;
};

struct {
int x,y;
int direction;
}ball;

void writeball()
{
}

void main()
{

int col,row,wallcost,nBouncers;
pinball A[53][53];
cin>>col>>row>>wallcost>>nBouncers;
for(int i=1;i<=col;i++)
for(int j=1;j<=row;j++)
{
A[j].bouncer = false;
A[j].value = 0;
A[j].cost = 0;
}
//int minx=1,miny=1;
for(int i=1;i<=col;i++)
{
A[1].bouncer = true;
A[1].value = 0;
A[1].cost = wallcost;
A[row].bouncer = true;
A[row].value = 0;
A[row].cost = wallcost;
}
for(int j=1;j<=row;j++)
{
A[1][j].bouncer = true;
A[1][j].value = 0;
A[1][j].cost = wallcost;
A[col][j].bouncer = true;
A[col][j].value = 0;
A[col][j].cost = wallcost;
}
int bouncercol,bouncerrow,bouncervalue,bouncercost;
for(int i=0;i<nBouncers;i++)
{
cin>>bouncercol>>bouncerrow>>bouncervalue>>bouncercost;
A[bouncercol][bouncerrow].bouncer = true;
A[bouncercol][bouncerrow].value=bouncervalue;
A[bouncercol][bouncerrow].cost=bouncercost;
}
int partialscore;
int totalscore=0;
while(!cin.eof())
{

partialscore=0;
//ball.x++;
//ball.y++;
int orgx,orgy;
{
orgx=ball.x;
orgy=ball.y;
switch (ball.direction)
{
case 0: /* direction right (add col) */
ball.x++;
break;
case 1: /* direction up (add row) */
ball.y++;
break;
case 2: /* direction left (minus col) */
ball.x--;
break;
case 3: /* direction down (minus row) */
ball.y--;
break;
}
writeball();
if(A[ball.x][ball.y].bouncer == true)
{
if (ball.direction == 0) /* update new direction */
ball.direction = 3;
else
ball.direction--;
//if(ball.lifetime >0) //maybe this must be turned on
partialscore += A[ball.x][ball.y].value;
ball.x = orgx;
ball.y = orgy;
}

writeball();
}

cout<<partialscore<<endl;
totalscore+=partialscore;
}
cout<<totalscore<<endl;

#ifndef ONLINE_JUDGE
int www;
cin>>www;
#endif
}[/cpp]
Last edited by PMNOX on Fri Aug 23, 2002 5:08 pm, edited 2 times in total.

Archangel
New poster
Posts: 29
Joined: Wed Jun 26, 2002 9:00 am
Here is my code:)

Code: Select all

#include<iostream.h>
#include<stdlib.h>

struct bumperprofile
{
int value;
int cost;
};

short row,col,bumpernum,bumperrow,bumpercol,i,j,index;
int   wallcost,totalscore,partialscore;

void main(void)
{
while(cin>>col>>row)
{
short *map = (short*) malloc(sizeof(short) *(row+1)*(col+1));
for (i=2;i<row;i++) /* fill walkable block of the map with -1 */
{
for (j=2;j<col;j++)
*(map+i*(col+1)+j) = -1;
}
cin>>wallcost>>bumpernum;
bumperprofile *bumperdata = new bumperprofile [bumpernum];
index = 0;
for (i=0;i<bumpernum;i++) /* fill and bumperdata array and update the bumper in the map */
{
cin>>bumpercol>>bumperrow>>(bumperdata+index)->value>>(bumperdata+index)->cost;
*(map+bumperrow*(col+1)+bumpercol) = index;	/* update the bumper with its array index */
index++;
}
totalscore = 0; /* reset the total score */
while (cin.eof() != 1) /* read in all pinballs, process one at a time */
{
partialscore = 0;
{
oricol = ballcol;
orirow = ballrow;
switch (direction)
{
case 0: /* direction right (add col) */
ballcol++;
break;
case 1: /* direction up (add row) */
ballrow++;
break;
case 2: /* direction left (minus col) */
ballcol--;
break;
case 3: /* direction down (minus row) */
ballrow--;
break;
}
if ((ballcol == 1)||(ballcol == col)||(ballrow == 1)||(ballrow == row)) /* when ball bump the wall */
{
if (direction == 0) /* update new direction */
direction = 3;
else
direction--;
ballcol = oricol; /* resume ball position */
ballrow = orirow;
}
else if (*(map+ballrow*(col+1)+ballcol) != -1) /* when ball hit the bumper */
{
partialscore = partialscore + (bumperdata+*(map+ballrow*(col+1)+ballcol))->value; /* update score value */
if (direction == 0) /* update new direction */
direction = 3;
else
direction--;
ballcol = oricol; /* resume ball position */
ballrow = orirow;
} /* end else */
} /* end while */
cout<<partialscore<<endl;
totalscore = totalscore + partialscore;
} /* end while */
cout<<totalscore<<endl;
free(map);
delete[]bumperdata;
}

}

ywliu
New poster
Posts: 9
Joined: Thu Aug 22, 2002 7:32 am
Location: Taiwan
PMNOX~~

your source code have a problem.
look original question carefully..

Sample input 's first line
4 4

it respresent 4*4 grid ...but col1 col4 row1 row4 is wall. not col5 row5.
so you can fix and try again....good luck....

[cpp]
for(int i=0;i<=x+1;i++)
{
A[0].bouncer = true;
A[0].value = 0;
A[0].cost = cost;
A[y+1].bouncer = true;
A[y+1].value = 0;
A[y+1].cost = cost;
}
for(int j=0;j<=y+1;j++)
{
A[0][j].bouncer = true;
A[0][j].value = 0;
A[0][j].cost = cost;
A[x+1][j].bouncer = true;
A[x+1][j].value = 0;
A[x+1][j].cost = cost;
}
[/cpp]

PMNOX
New poster
Posts: 49
Joined: Wed Feb 13, 2002 2:00 am
Location: Poland
Contact:
thx, i have already fixed it:
[cpp]#include <iostream.h>
#define ONLINE_JUDGE
struct pinball
{
bool bouncer;
int value;
int cost;
};

struct {
int x,y;
int direction;
}ball;

void writeball(int &x)
{
}

void main()
{

int col,row,wallcost,nBouncers;
pinball A[53][53];
cin>>col>>row>>wallcost>>nBouncers;
for(int i=1;i<=col;i++)
for(int j=1;j<=row;j++)
{
A[j].bouncer = false;
A[j].value = 0;
A[j].cost = 0;
}
//int minx=1,miny=1;
for(int i=1;i<=col;i++)
{
A[1].bouncer = true;
A[1].value = 0;
A[1].cost = wallcost;
A[row].bouncer = true;
A[row].value = 0;
A[row].cost = wallcost;
}
for(int j=1;j<=row;j++)
{
A[1][j].bouncer = true;
A[1][j].value = 0;
A[1][j].cost = wallcost;
A[col][j].bouncer = true;
A[col][j].value = 0;
A[col][j].cost = wallcost;
}
int bouncercol,bouncerrow,bouncervalue,bouncercost;
for(int i=0;i<nBouncers;i++)
{
cin>>bouncercol>>bouncerrow>>bouncervalue>>bouncercost;
A[bouncercol][bouncerrow].bouncer = true;
A[bouncercol][bouncerrow].value=bouncervalue;
A[bouncercol][bouncerrow].cost=bouncercost;
}
int partialscore;
int totalscore=0;
while(!cin.eof())
{

partialscore=0;
//ball.x++;
//ball.y++;
int orgx,orgy;
{
orgx=ball.x;
orgy=ball.y;
switch (ball.direction)
{
case 0: /* direction right (add col) */
ball.x++;
break;
case 1: /* direction up (add row) */
ball.y++;
break;
case 2: /* direction left (minus col) */
ball.x--;
break;
case 3: /* direction down (minus row) */
ball.y--;
break;
}
#ifndef ONLINE_JUDGE
writeball(partialscore);
#endif
if(A[ball.x][ball.y].bouncer == true)
{
if (ball.direction == 0) /* update new direction */
ball.direction = 3;
else
ball.direction--;
//if(ball.lifetime >1) //maybe this must be turned on
partialscore += A[ball.x][ball.y].value;
ball.x = orgx;
ball.y = orgy;
}
#ifndef ONLINE_JUDGE
writeball(partialscore);
#endif
}

cout<<partialscore<<endl;
totalscore+=partialscore;
}
cout<<totalscore<<endl;
#ifndef ONLINE_JUDGE
int www;
cin>>www;
#endif
}[/cpp]
Last edited by PMNOX on Fri Aug 23, 2002 11:07 pm, edited 1 time in total.