114 - Simulation Wizardry

[arc16]

if i'm not wrong, you should increase the score if the ball still has a lifetime before you decrease the ball's lifetime. It stated in the desc.

Code: Select all

As long as the ball has a positive lifetime when it hits a bumper, it obtains the full score for that bumper.

so these lines below is not correct

[c]
ball.lifetime -= A[ball.x][ball.y].cost;
if(ball.lifetime >0) //maybe this must be turned on
partialscore += A[ball.x][ball.y].value;
[/c]

[PMNOX]

yes, true, but i still don't know what is wrong

[PMNOX]

ok, judge has finally accepted my problem, there was just simple input bug, tell me if you still want me to publish code.

[nghiank]

tes?

[skylander]

i just carn figure out what is wrong with my code, the judge just gives me wa

[c]/* @BEGIN_OF_SOURCE_CODE /**/

#include <sys/types.h>
#include <sys/stat.h>
#include <fcntl.h>
#include <stdio.h>

#define MAX_M 55
#define MAX_N 55

void makeGrid(const int, const int, const int);
int playBall(const int, const int, const int, const int);

int grid[MAX_M][MAX_N], value[MAX_M][MAX_N], isobstacle[MAX_M][MAX_N];

int m, n;

int main(void) {
#ifndef ONLINE_JUDGE
close (0); open ("in", O_RDONLY);
#endif
int i;
int x, y, v, c;
int wall, bumper;

scanf("%d %d\n", &m, &n);
scanf("%d\n", &wall);

makeGrid(m, n, wall);

scanf("%d\n", &bumper);

for(i=0;i<bumper;i++) {
scanf("%d %d %d %d\n", &x, &y, &v, &c);

grid[n - y][x + 1] = c;
value[n - y][x + 1] = v;
isobstacle[n - y][x + 1] = 1;
}

/*printGrid(m, n, -1, -1);*/

wall = 0;
bumper = 0;

while(!feof(stdin)) {
scanf("%d %d %d %d\n", &x, &y, &c, &v);

wall = playBall(x, y, c, v);
bumper += wall;

printf("%d\n", wall);
}
printf("%d\n", bumper);

return 0;
}

int playBall(const int x, const int y, const int dir, const int life) {
int lifetime, points;
int ballx, bally, oldx, oldy;
int balldir;

lifetime = life;
balldir = dir;
points = 0;

ballx = x;
bally = y;

while(lifetime > 0) {
oldx = ballx;
oldy = bally;

switch(balldir) {
case 0:
ballx++;
break;
case 1:
bally++;
break;
case 2:
ballx--;
break;
case 3:
bally--;
break;
}

if(!isobstacle[n - bally][ballx + 1])
lifetime--;
else {
printf("");
lifetime -= grid[n - bally][ballx + 1] + 1;
if(lifetime > 0)
points += value[n - bally][ballx + 1];

ballx = oldx;
bally = oldy;

balldir += 3;
balldir %= 4;
}
/*printGrid(m, n, ballx + 1, n - bally);*/
/*printf("\n");*/
}

return points;
}

void makeGrid(const int m, const int n, const int w) {
int i, j;

for(i=0;i<=n;i++)
for(j=0;j<=m;j++) {
if(!j || !i || j == m || i == n) {
grid[j] = w;
isobstacle[j] = 1;
} else {
grid[j] = 0;
isobstacle[j] = 0;
}
value[j] = 0;
}
}

/* @END_OF_SOURCE_CODE /**/[/c]

[epsilon0]

i need help on this problem as well. my code works well on the judge's input.
but it gives me a TIME LIMIT. i don't see why. this problem has a low complexity.

here's my program:

[c]#include <stdio.h>
#include <stdlib.h>

#define MMAX 51
#define NMAX 51
#define NOBUMP -1

int grid[MMAX][NMAX];

int m,n,wallcost,nbumpers;

typedef struct cost { int pointsup, lifedown; } cost;

struct _ball { int x,y,dir,pts,life; } ball;

cost *bumpers;

char init()
{
int x,y,i,j;
scanf("%d%d%d%d",&m,&n,&wallcost,&nbumpers);
for (i=1;i<m-1;i++)
for (j=1;j<n-1;j++)
grid[j] = NOBUMP;
for (i=0;i<m;i++)
{
grid[0] = 0;
grid[n-1] = 0;
}
for (j=0;j<n;j++)
{
grid[0][j] = 0;
grid[m-1][j] = 0;
}
if ((bumpers = (cost *)malloc((nbumpers+1)*sizeof(cost))) == NULL)
return 0;
bumpers[0].pointsup = 0;
bumpers[0].lifedown = wallcost;
for (i=1;i<=nbumpers;i++)
{
scanf("%d%d%d%d",&x,&y,&bumpers.pointsup,&bumpers.lifedown);
grid[x][y] = i;
}
return 1;
}

char getBall()
{
if ((scanf("%d%d%d%d",&ball.x,&ball.y,&ball.dir,&ball.life)) != 4)
return 0;
ball.pts = 0;
return 1;
}

int simulate()
{
int x,y,nbmp;
while(--(ball.life))
{
x = ball.x; y = ball.y;
switch(ball.dir)
{
case 0: x++; break;
case 1: y++; break;
case 2: x--; break;
default: y--;
}
if ((nbmp = grid[x][y]) != NOBUMP)
{
ball.pts += bumpers[nbmp].pointsup;
ball.life -= bumpers[nbmp].lifedown;
switch(ball.dir)
{
case 0: ball.dir = 3; break;
case 1: ball.dir = 0; break;
case 2: ball.dir = 1; break;
default: ball.dir = 2;
}
}
else
{
ball.x = x;
ball.y = y;
}
}
printf("%d\n",ball.pts);
return ball.pts;
}

int main()
{
int n_points = 0;
if (!init())
return EXIT_FAILURE;
while(getBall())
n_points += simulate();
printf("%d\n",n_points);
return EXIT_SUCCESS;
}
[/c]

please tell me if you see why this code gets TIME LIMIT EXCEEDED

[epsilon0]

i had a table offset problem. i corrected it, but it's still time limit

[epsilon0]

i still have TLE.

here is my source code now:

note that coordinates in my program go from 0 ot m-1 and 0 to n-1.
also i assumed walls were within the grid. ie playground 4x4 means only 2x2 "non-wall" positions.

[c]#include <stdio.h>
#include <stdlib.h>

#define MMAX 51
#define NMAX 51
#define NOBUMP -1

int grid[MMAX][NMAX];

int m,n,wallcost,nbumpers;

typedef struct cost { int pointsup, lifedown; } cost;

struct _ball { int x,y,dir,pts,life; } ball;

cost *bumpers;

char init()
{
int x,y,i,j;
scanf("%d%d%d%d",&m,&n,&wallcost,&nbumpers);
for (i=1;i<m-1;i++)
for (j=1;j<n-1;j++)
grid[j] = NOBUMP;
for (i=0;i<m;i++)
{
grid[0] = 0;
grid[n-1] = 0;
}
for (j=0;j<n;j++)
{
grid[0][j] = 0;
grid[m-1][j] = 0;
}
if ((bumpers = (cost *)malloc((nbumpers+1)*sizeof(cost))) == NULL)
return 0;
bumpers[0].pointsup = 0;
bumpers[0].lifedown = wallcost;
for (i=1;i<=nbumpers;i++)
{
scanf("%d%d%d%d",&x,&y,&bumpers.pointsup,&bumpers.lifedown);
grid[x-1][y-1] = i;
}
return 1;
}

char getBall()
{
if ((scanf("%d%d%d%d",&ball.x,&ball.y,&ball.dir,&ball.life)) != 4)
return 0;
ball.x--;
ball.y--;
ball.pts = 0;
return 1;
}

int simulate()
{
int x,y,nbmp;
while(--(ball.life))
{
x = ball.x; y = ball.y;
switch(ball.dir)
{
case 0: x++; break;
case 1: y++; break;
case 2: x--; break;
default: y--;
}
if ((nbmp = grid[x][y]) != NOBUMP)
{
ball.pts += bumpers[nbmp].pointsup;
ball.life -= bumpers[nbmp].lifedown;
ball.dir = (ball.dir + 3) % 4;
/* switch(ball.dir)
{
case 0: ball.dir = 3; break;
case 1: ball.dir = 0; break;
case 2: ball.dir = 1; break;
default: ball.dir = 2;
}
*/
}
else
{
ball.x = x;
ball.y = y;
}
}
printf("%d\n",ball.pts);
return ball.pts;
}

int main()
{
int n_points = 0;
if (!init())
return EXIT_FAILURE;
while(getBall())
n_points += simulate();
printf("%d\n",n_points);
return EXIT_SUCCESS;
}
[/c]

please help, this is the second program in a row that i solve and get rejected, though it works (after 128 CRC Software).

[Ivan Golubev]

also i assumed walls were within the grid. ie playground 4x4 means only 2x2 "non-wall" positions.

No, walls are outside the grid, so 4x4 means it's really 4x4 playground.

[epsilon0]

are you sure? if i do this my program gives wrong answers.

[Ivan Golubev]

Oops, sorry, I was wrong! Yeah, the walls are inside the grid.

[Hisoka]

Hello......

Can you help me to give some test case for this problem, because I always got WA for this problem but I don't know why.
Maybe my description wrong or ???? but based on all previous post for this problem I thinks my description true. maybe I missing something ?

THANKS.......

[Hisoka]

oke finally I got AC. I miss a clue from this board.

THANKS.........

[ezra]

please help me. i dont know why i keep getting wa for this prob.
here is my code
[c]#include<stdio.h>
struct grid
{
int obstacle;
int value;
int cost;
};

struct ball
{
int px;
int py;
int d;
int life;
};

void resolve(int a,int *ax,int *ay)
{
switch(a)
{
case 0 : *ax=1; *ay=0; break;
case 1 : *ax=0; *ay=1; break;
case 2 : *ax=-1; *ay=0; break;
case 3 : *ax=0; *ay=-1;
}
}

void main()
{
int x,y,total;
struct ball bola;
int wcost;
int ax,ay;
int bx,by,bv,bc;
int n,i,j;
int nilai;
struct grid icen[51][51];
scanf("%d%d",&x,&y);
scanf("%d",&wcost);
for(i=1;i<=x;i++)
for(j=1;j<=y;j++)
{
if(i==1||j==1||i==x||j==y)
{
icen[j].obstacle=1;
icen[j].value=0;
icen[j].cost=wcost;
}
else
{
icen[j].obstacle=0;
icen[j].value=0;
icen[j].cost=0;
}
}
scanf("%d",&n);
for(i=0;i<n;i++)
{
scanf("%d%d%d%d",&bx,&by,&bv,&bc);
icen[bx][by].obstacle=1;
icen[bx][by].value=bv;
icen[bx][by].cost=bc;
}
total=0;
while(scanf("%d%d%d%d",&(bola.px),&(bola.py),&(bola.d),&(bola.life))==4)
{
nilai=0;
resolve(bola.d,&ax,&ay);
while(bola.life>0)
{
(bola.life)--;
if(bola.life>0)
{
if(icen[bola.px+ax][bola.py+ay].obstacle==1)
{
bola.life-=icen[bola.px+ax][bola.py+ay].cost;
if(bola.life>0)
nilai+=icen[bola.px+ax][bola.py+ay].value;
(bola.d)--;
if(bola.d==-1)
bola.d=3;
resolve(bola.d,&ax,&ay);
}
else
{
bola.px+=ax;
bola.py+=ay;
}
}
}
printf("%d\n",nilai);
total+=nilai;
}
printf("%d\n",total);
}[/c]
thanks for reply.

[Hisoka]

hello ezra.......

I think you misunderstand about this problem.
check this post.

http://acm.uva.es/board/viewtopic.php?t=255

I got WA at first too.

bye........