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

wsarzynski
New poster
Posts: 19
Joined: Fri Oct 04, 2002 7:50 pm
Location: Warsaw, Poland

Post by wsarzynski » Sat Nov 08, 2003 5:46 am

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
New poster
Posts: 12
Joined: Thu Oct 30, 2003 1:38 pm
Location: St. Petersburg, Russia
Contact:

Continuous troubles with this problem.

Post by Aengus » Sun Nov 09, 2003 1:47 pm

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]

User avatar
ImLazy
Experienced poster
Posts: 215
Joined: Sat Jul 10, 2004 4:31 pm
Location: Shanghai, China

Who can explain me the 114?

Post by ImLazy » Mon Jan 17, 2005 9:19 am

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?
I stay home. Don't call me out.

gits
New poster
Posts: 19
Joined: Sun Oct 26, 2003 10:08 pm
Location: Aveiro, Portugal
Contact:

Post by gits » Thu Jan 20, 2005 4:12 pm

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 :)

User avatar
ImLazy
Experienced poster
Posts: 215
Joined: Sat Jul 10, 2004 4:31 pm
Location: Shanghai, China

Post by ImLazy » Thu Jan 20, 2005 5:13 pm

I see. I'll try it. Thank you again.
I stay home. Don't call me out.

User avatar
ImLazy
Experienced poster
Posts: 215
Joined: Sat Jul 10, 2004 4:31 pm
Location: Shanghai, China

Post by ImLazy » Fri Jan 21, 2005 7:51 am

Ha ha..., Now I get AC. Thank you one more time, gits.
I stay home. Don't call me out.

dootzky
New poster
Posts: 36
Joined: Tue Apr 12, 2005 12:20 am
Location: belgrade, serbia (ex yugoslavia)
Contact:

114

Post by dootzky » Wed May 18, 2005 10:48 pm

why SIGSEGV??

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

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
New poster
Posts: 48
Joined: Mon Jun 27, 2005 4:18 pm
Location: Hong Kong

Problem 114 : Confuced !!!!

Post by Chok » Fri Jul 29, 2005 1:50 pm

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.

User avatar
ImLazy
Experienced poster
Posts: 215
Joined: Sat Jul 10, 2004 4:31 pm
Location: Shanghai, China

Post by ImLazy » Sat Aug 06, 2005 6:43 am

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.
:)
I stay home. Don't call me out.

Sakib
New poster
Posts: 24
Joined: Fri Jan 28, 2005 5:27 pm
Location: Bangladesh

Problem 114 TLE???????!!!!!!!!!!!!!

Post by Sakib » Mon Aug 15, 2005 5:50 pm

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.
/* Sorry For Nothing */

hongyan
New poster
Posts: 4
Joined: Wed Oct 19, 2005 3:06 am
Location: zsu

Post by hongyan » Thu Oct 20, 2005 6:58 am

lifetime maybe very big.
please call me hongyan.
my QQ number is 76296127
my Email address is sanwushuosi@163.com
welcome for connect me!!

ar2rd
New poster
Posts: 16
Joined: Sat Oct 22, 2005 2:05 am

114 WA

Post by ar2rd » Sun Dec 18, 2005 5:05 pm

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;
}
You're never too old to become younger...

Fali
New poster
Posts: 8
Joined: Fri Jul 15, 2005 4:00 am

114 - Simulation Wizardry

Post by Fali » Tue Jun 27, 2006 7:36 am

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
New poster
Posts: 3
Joined: Fri Aug 18, 2006 9:37 pm

Post by Ultras » Sun Aug 27, 2006 1:51 am

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
New poster
Posts: 12
Joined: Fri Dec 16, 2005 4:22 pm
Location: shanghai/china
Contact:

WHY WA !???114! WHO CAN HELP ME?

Post by Staryin » Sun Oct 29, 2006 2:49 am

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;	
}

Post Reply

Return to “Volume 1 (100-199)”