114 - Simulation Wizardry

[wsarzynski]

ball uses unit of lifetime for each HIT of bumper,
even if it does not move, it can lose all life just by hitting walls.
answer to your input is
0
0

[Aengus]

I have troubles with this problem for a long time.

I've already checked all the things, mentioned at the board. I got Time Limit and when I've made some kind of dynamic programming instead of usual simulation, I've got the runtime error, which ment that the ball returnes to some point with increased lifetime left. Could anyone check my code?

[c]#include <stdio.h>

int m, n, wc;
int field[52][52];
int v[2500], c[2500];
int x, y, d, l;

int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};

int move(void) { /* Returning the value for this move */
int newx, newy;

newx = x + dx[d];
newy = y + dy[d];

if (newx > 1 && newx < m && newy > 1 && newy < n && field[newx][newy] == 0) {
x = newx;
y = newy;
return 0;
}

d--; if (d < 0) d = 3;

if (field[newx][newy]) {
l -= c[field[newx][newy]];
return v[field[newx][newy]];
}

l -= wc;
return 0;
}

int p, bx, by;
int total, points;
int i, j, k;

int main(void) {
scanf("%d %d %d %d", &m, &n, &wc, &p);

for (i = 1; i <= p; i++) {
scanf("%d %d %d %d", &bx, &by, &v, &c);

field[bx][by] = i;
}

while (scanf("%d %d %d %d", &x, &y, &d, &l) == 4) {
points = 0;

while (--l > 0) points += move();

total += points;

printf("%d\n", points);
}

printf("%d\n", total);

return 0;
}[/c][/c]

[ImLazy]

I even can't understand the sample input&output! OK, here is the way how I think about the sample input&output:

The sample input:
4 4
0
2
2 2 1 0
3 3 1 0

And we just look at the 5th ball:
2 3 1 5

I think what will happen as follows:

Code: Select all

0. The ball is at (2,3), direction:up, life:5
1. The ball goes to (2,4), its life becomes 4. Since (2,4) is wall, the ball turns right, now direction is right.
2. The ball goes to (3,4), its life becomes 3. Since (3,4) is wall, the ball turns right, now direction is down.
3. The ball goes to (3,3), its life becomes 2. Since (3,3) is bumper, the ball gets 1 score and turn right. Now direction is left.
4. The ball goes to (2,3), its life becomes 1. 
5. The ball goes to (1,3), its life becomes 0. It disappears.

As my thought, it should score 1. But the sample output tells us it scores 2.
I know my way to consider this process is certainly wrong. But I really don't know how can the ball mentioned above get 2 scores. Who can tell me?

[gits]

Hi again! I've already solved this one, but my first atempt was Wrong Answer.

Let me draw the table of the sample input:

XXXX
X_BX
XB_X
XXXX

The X are walls B are bumpers.
The problem says that 1 <= x <= m and 1 <= y <= n. But the limit positions are walls. That means (3,4) isn't a valid position, neither is (1,1). So, in a 4x4 grid, only 2x2 positions are "inside".

So for the sample input, you start in position (2,3) and then:
step 1 (up): you hit the wall at (2,4) and thus stay in (2,3) but turn right.
step 2 (right): you _try_ to hit the bumper in (3,3). You only hit the bumper IF your life is still positive when you hit it. More on this below.
step 3 (down): you _try_ to hit the bumper in (2,2).
step 4 (left): hit the wall at (1,3), stay in (2,3) and turn right
step 5 (up): hit wall (2,4) and turn.

In the sample input you never leave position (2,3).

My Wrong Answer was because you only hit a bumper when your life is still positive. For instace, suppose your life is 2, you are in (2,3) going right and there is a bumper in (3,3). To make the move you lose 1 life, so life becomes 1. But then you hit the bumper and thus turn right (and sum its value to the pontuation). Notice that the bumper cost may reduce your life below 0, and it may also raise your life again; but the catch here is that you _only_ hit the bumper if the life total _after_ moving is still positive.
Now suppose the life total was 1. Because you spend 1 life to make the move, you don't hit the bumper, so you don't get it's value and it doesn't change your life total (either if would go up or down).

Hope this helps

[ImLazy]

I see. I'll try it. Thank you again.

[ImLazy]

Ha ha..., Now I get AC. Thank you one more time, gits.

[dootzky]

why SIGSEGV??

here is my code, it's little bit pointless to explain what i did, 'cause i simply SIMULATE the whole pinball thang

thx for any help,
dootzky

Code: Select all

#include <iostream.h>

	int i,j,m,n,x,y,a,b,c,d;
	int wall_cost,way,life,points,total_points;
	int value[200][200],cost[200][200];
	char polje[200][200];



void init () {
	// init
	for (i=0;i<m;i++) for (j=0;j<n;j++) polje[i][j]='.';
	for (i=0;i<m;i++) for (j=0;j<n;j++) value[i][j]=0;
	for (i=0;i<m;i++) for (j=0;j<n;j++) cost[i][j]=0;
	total_points=0;

	// sada postavljamo zidove
	for (i=0;i<n;i++) polje[0][i]='X';
	for (i=0;i<n;i++) polje[m-1][i]='X';
	for (i=0;i<m;i++) polje[i][0]='X';
	for (i=0;i<m;i++) polje[i][n-1]='X';
}

void turn_right () { if (--way==-1) way=3; } // 0 - right; 1 - up; 2 - left; 3 - down;




int go_play () {
	
	points=0;

	while (life>1) {
		if (way==0) { // RIGHT
			if (polje[y][x+1]=='X') { 
				turn_right(); 
				life -= wall_cost;
				goto ciklus; 
			}
			if (polje[y][x+1]=='*') { 
				turn_right(); 
				points += value[y][x+1]; 
				life -= cost[y][x+1]; 
				goto ciklus; 
			}
			if (x<n) x++; // znaci ako nema nista ispred - MOVE bjatch! :)
		}

		if (way==1) { // UP
			if (polje[y-1][x]=='X') { 
				turn_right(); 
				life -= wall_cost;
				goto ciklus; 
			}
			if (polje[y-1][x]=='*') { 
				turn_right(); 
				points += value[y-1][x]; 
				life -= cost[y-1][x]; 
				goto ciklus; 
			}
			if (y>0) y--; // znaci ako nema nista ispred - MOVE bjatch! :)
		}

		if (way==2) { // LEFT
			if (polje[y][x-1]=='X') { 
				turn_right(); 
				life -= wall_cost;
				goto ciklus; 
			}
			if (polje[y][x-1]=='*') { 
				turn_right(); 
				points += value[y][x-1]; 
				life -= cost[y][x-1]; 
				goto ciklus; 
			}
			if (x>0) x--; // znaci ako nema nista ispred - MOVE bjatch! :)
		}

		if (way==3) { // DOWN
			if (polje[y+1][x]=='X') { 
				turn_right(); 
				life -= wall_cost;
				goto ciklus; 
			}
			if (polje[y+1][x]=='*') { 
				turn_right(); 
				points += value[y+1][x]; 
				life -= cost[y+1][x]; 
				goto ciklus; 
			}
			if (y<m) y++; // znaci ako nema nista ispred - MOVE bjatch! :)
		}

ciklus:
	life--;
	d=0; // haha, omg! empty statement! :)
		
	} // kraj while

	return points;
}



/*** MAIN ***/
void main () {

	// input
	cin >> m >> n;
	cin >> wall_cost;
	init();
	cin >> j; // number of bumpers
	for (i=0;i<j;i++) { 
		cin >> x >> y >> a >> b; 
		x--; y=m-y;
		polje[y][x]='*';
		value[y][x]=a;
		cost [y][x]=b;
	}
	
	// uzimanje i obrada loptica...
	while (cin >> x >> y >>	way >> life) {
		x--; y=m-y;

		c = go_play();
		total_points += c;

		cout << c << endl;

	} // kraj while

	cout << total_points << endl;
	
	
// test output
//	for (i=0;i<m;i++) {
//		for (j=0;j<n;j++) cout << polje[i][j];
//		cout << endl;
//	}

}

[Chok]

Hi all,
I'm getting confuced for the problem input/output. I've also checked for the previous thread. Please give some explanation abt the input and output. Thankx in advance.

[ImLazy]

I used to be confused about this problem, too. I hope this can help you.
http://online-judge.uva.es/board/viewto ... highlight=
Good luck.

[Sakib]

I dont understand Why This problem can cause "Time Limit Exceeded".
There may be an infinite loop or what?
Please Somebody help me.
At least someone give me some Test inputs Outputs pls.
Thanks.

[hongyan]

lifetime maybe very big.

[ar2rd]

I have no idea why it gets WA. I tested my program for all inputs available on board and it works. Any ideas?

Code: Select all

//Simulation Wizardry - acm.uva.es/p/v1/114.html
#include <iostream>
#include <cstring>
#include <cstdio>
#define MAXD 55
#define REP(i,n) for(int tn=n,i=0; i < tn; i++)
using namespace std;

int cost[MAXD][MAXD],val[MAXD][MAXD],bmp[MAXD][MAXD],M,N,wallCost,x,y,life,p,dir,score,total=0;
int dx[] = {1,0,-1,0},dy[] = {0,1,0,-1};

int main() {
    
    #ifndef ONLINE_JUDGE
    freopen("in.txt", "r", stdin);
    freopen("out.txt", "w", stdout);
    #endif
    
    cin >> M >> N; M--; N--;
    cin >> wallCost;
    cin >> p;  
    
    memset(cost, 0, sizeof(cost));
    memset(val, 0, sizeof(val));
    memset(bmp, 0, sizeof(bmp));

    REP(i,p) {
        cin >> x >> y; x--; y--;
        cin >> val[x][y] >> cost[x][y]; 
        bmp[x][y] = 1;       
    }

    while( cin >> x >> y >> dir >> life ) {
         x--; y--; score = 0;
         
         while(life > 0) {
             life--;
             if( bmp[x+dx[dir]][y+dy[dir]] ) { 
                  if(life>0)score += val[x+dx[dir]][y+dy[dir]];
                  life -= cost[x+dx[dir]][y+dy[dir]];
                  dir = (dir+3)%4;   
             }
             else if( x+dx[dir] == M || x+dx[dir] == 0 || y+dy[dir] == N || y+dy[dir] == 0) { 
                  life -= wallCost;
                  dir = (dir+3)%4;
             }
             else {            
                  x+=dx[dir];
                  y+=dy[dir];
             }
                             
         }
         
         cout << score << endl;
         total += score;
    }
    cout << total << endl;
}

[Fali]

I hope somebody can help me... I don't know why i got WA.
Please, help

My code:

Code: Select all

/*
  Simulation Wizardry, UVa # 114
  Nephtali Garrido
*/
#include <iostream>
#include <cstdio>
using namespace std;
struct bumper
{      bool h;
       long v,cos;
}mat[53][53];


long pa,p,vida,tot,pu;
int m,n,c,c2,x,y,d;

int main()
{   scanf("%d %d",&m,&n);
    for(c=0;c<n;c++)
     for(c2=0;c2<m;c2++)
      mat[c][c2].h=false;
    scanf("%ld",&pa);
    scanf("%ld",&p);
    for(c=0;c<p;c++)
    { scanf("%d %d",&x,&y);
      x--;
      y--;
      mat[y][x].h=true;
      scanf("%ld %ld",&mat[y][x].v,&mat[y][x].cos);
    }
    tot=0;
    while(scanf("%d",&x)!=EOF)
    { scanf("%d",&y);
      x--;
      y--;
      scanf("%d",&d);
      scanf("%ld",&vida);
      pu=0;
      while(vida>0)
      { if(d==0)
        { if(x+1>=m-1)
           if(vida-pa-1<=0)
            break;
           else
           { vida-=pa;
             vida--;
             d=3;
           }
          else if(mat[y][x+1].h==true)
           if(vida-mat[y][x+1].cos-1<=0)
            break;
           else
           { pu+=mat[y][x+1].v;
             d=3;
             vida-=mat[y][x+1].cos;
             vida--;
           }
          else
          { vida--;
            x++;
          }
        }
        else if(d==1)
        { if(y+1>=n-1)
           if(vida-pa-1<=0)
            break;
           else
           { vida-=pa;
             vida--;
             d--;
           }
          else if(mat[y+1][x].h==true)
           if(vida-mat[y+1][x].cos-1<=0)
            break;
           else
           { pu+=mat[y+1][x].v;
             d--;
             vida-=mat[y+1][x].cos;
             vida--;
           }
          else
          { vida--;
            y++;
          }
        }
        else if(d==2)
        { if(x-1<=0)
           if(vida-pa-1<=0)
            break;
           else
           { vida-=pa;
             vida--;
             d--;
           }
          else if(mat[y][x-1].h==true)
           if(vida-mat[y][x-1].cos-1<=0)
            break;
           else
           { pu+=mat[y][x-1].v;
             d--;
             vida-=mat[y][x-1].cos;
             vida--;
           }
          else
          { vida--;
            x--;
          }
        }
        else if(d==3)
        { if(y-1<=0)
           if(vida-pa-1<=0)
            break;
           else
           { vida-=pa;
             vida--;
             d--;
           }
          else if(mat[y-1][x].h==true)
           if(vida-mat[y-1][x].cos-1<=0)
            break;
           else
           { pu+=mat[y-1][x].v;
             d--;
             vida-=mat[y-1][x].cos;
             vida--;
           }
          else
          { vida--;
            y--;
          }
        }
      }
      printf("%ld\n",pu);
      tot+=pu;
    }
    printf("%ld\n",tot);
    return 0;
}

[Ultras]

but the catch here is that you _only_ hit the bumper if the life total _after_ moving is still positive.

I can't say that i understood this totally...
but this is right sequence, how it working:

if (a[NextPoint.x][NextPoint.y].is==true){ // next point is bumper
Ball.lifes--;
if (Ball.lifes>0){
Ball.lifes-=a[NextPoint.x][NextPoint.y].cost;
Ball.points+=a[NextPoint.x][NextPoint.y].value;

Ball.direction -=1;
if (Ball.direction <0) Ball.direction+=4;
}

hope it will help...

[Staryin]

Code: Select all

#include <iostream>

using namespace std;

struct point{
	int value;
	int cost;
	bool is_wall;
	bool is_bumper; 	
	
}grid[55][55];

int nextdir(int dir)
{
	if(dir == 0)return 3;
	if(dir == 1)return 0;
	if(dir == 2)return 1;
	if(dir == 3)return 2;
}

int getpoint(int x,int y)
{
	if(grid[x][y].is_bumper)return grid[x][y].value;
	return 0;
}

int gettime(int x,int y)
{
	if(grid[x][y].is_bumper||grid[x][y].is_wall)return grid[x][y].cost+1;
	
	return 1;
}
int solve(int sx,int sy,int dir,int timeleft)
{
	int one_point = 0;
	while(1)
	{
		
		switch(dir)
		{
			case 0:sx++;break;	
			case 1:sy++;break;
			case 2:sx--;break;
			case 3:sy--;break;
		
		}
		//cout<<sx<<" "<<sy<<endl;
		//cout<<timeleft<<endl;
		timeleft -= gettime(sx,sy);
		//cout<<timeleft<<endl;
		if(timeleft <= 0)return one_point;
		one_point += getpoint(sx,sy);	
		if(grid[sx][sy].is_wall||grid[sx][sy].is_bumper)
		{
			if(dir == 0)sx--;
			if(dir == 1)sy--;
			if(dir == 2)sx++;
			if(dir == 3)sy++;
			dir = nextdir(dir);
			
		}
		//cout<<sx<<" "<<sy<<endl;
	}	
	
}

int main()
{
	int m,n,i,j;
	int wallcost,n_bumper;
	int x,y,p_value,p_cost;
	int dir,timeleft;
	int sum_point = 0;
	cin>>m>>n;
	
	for(i = 1;i <= m;i++)
		for(j = 1;j <=n;j++)
			{
				grid[i][j].value = 0;
				grid[i][j].cost = 0;
				grid[i][j].is_wall = false;
				grid[i][j].is_bumper = false;
			}
	
	cin>>wallcost;
	
	for(i = 1; i <= m;i++)
	{
		grid[i][1].is_wall = true;	
		grid[i][1].cost =wallcost;
		grid[i][n].is_wall = true;	
		grid[i][n].cost = wallcost;
	}
		
	for(i = 1; i <= n;i++)
	{
		grid[1][i].is_wall = true;
		grid[1][i].cost = wallcost;
		grid[m][i].is_wall = true;
		grid[m][i].cost = wallcost;
	}
	
	
	
	cin>>n_bumper;
	
	for(i = 0;i < n_bumper;i++)
	{
		cin>>x>>y>>p_value>>p_cost;
		grid[x][y].is_bumper = true;
		grid[x][y].value = p_value;
		grid[x][y].cost = p_cost;
	}
	
	while(cin>>x>>y>>dir>>timeleft)
	{
		int one_point = 0;
		one_point = solve(x,y,dir,timeleft);
		cout<<one_point<<endl;
		sum_point += one_point;
	}
	
	cout<<sum_point<<endl;
	return 0;	
}