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

Staryin
New poster
Posts: 12
Joined: Fri Dec 16, 2005 4:22 pm
Location: shanghai/china
Contact:

WHY WA!114!!!!!!!!!!!!!!!!!!!!!!!!!!!

Post by Staryin » Wed Nov 01, 2006 2:01 pm

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;
		
		}
		
		timeleft -= gettime(sx,sy);
		if(timeleft  < 1)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);
			
		}
		
	}	
	
}

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

joehuang92
New poster
Posts: 9
Joined: Sat Nov 18, 2006 4:56 pm
Location: Taiwan
Contact:

114 WA... Are there more test cases?

Post by joehuang92 » Tue Dec 19, 2006 10:43 am

I've tried all test cases on the board and my program gives all correct results...but it just recieve WA. Can someone help to give more test cases? (And ofcource, correct output)

I'll be thanksful !!

Cytoplasm
New poster
Posts: 13
Joined: Tue Jun 14, 2005 6:33 pm
Location: Paris, France

Post by Cytoplasm » Wed Dec 20, 2006 8:13 pm


joehuang92
New poster
Posts: 9
Joined: Sat Nov 18, 2006 4:56 pm
Location: Taiwan
Contact:

Post by joehuang92 » Thu Dec 21, 2006 8:13 am

Thx a lot.

But I found that the test case on the page is invalid, for the bumper datas exceed the number given(There are 314 bumpers but input give out the number 300). For the reason I had deleted some of the bumpers, then other test cases didn't fit any of the outputs...

Same situation also happened when I expand the number of bumpers to the input number 314, test cases just blow up or give out wrong output.

But I'm sure that I've run through all test cases on the board and my program gives correct output...

If possible, can you help modify the input? Or maybe someone who can help check my code if there are something wrong...?

Code: Select all

#include<stdio.h>
#include<stdlib.h>

typedef struct
{
  int type;
  int cost; 
  int point;
}grid;

typedef struct
{
  int x,y;
  int life;
  int point;
  int mode;
}pinball;

int height;
int width;

grid map[51][51];

int cost_wall;

int n_bumper;

int sum_point;

void makewall();
void move(int mode,pinball *ballPtr);

int main()
{
  int i,j;
  int temp_x,temp_y,temp_p,temp_c;
  
  pinball *ball;
  
  scanf(" %d %d",&width,&height);
  scanf(" %d",&cost_wall);
  scanf(" %d",&n_bumper);
  
  for( i=0 ; i<n_bumper ; i++ )
  {
    scanf(" %d %d %d %d",&temp_x,&temp_y,&temp_p,&temp_c);
    map[temp_x][temp_y].type = 2;
    map[temp_x][temp_y].cost = temp_c;
    map[temp_x][temp_y].point = temp_p;
  }
  makewall();
  
  ball = ( pinball* )malloc( sizeof(pinball) );
  
  while( scanf(" %d %d %d %d",&(ball->x),&(ball->y)
                             ,&(ball->mode),&(ball->life) )==4 )
  {
    ball->point = 0;
    
    while( ball->life > 0 )
      move( ball->mode , ball );
      
    sum_point += ball->point; 
    
    printf("%d\n",ball->point);
  }
  printf("%d\n",sum_point);
  
  return 0;
}

void makewall()
{
  int i;
  
  for( i=1 ; i<=width ; i++ )
  {
    map[i][1].cost = map[i][height].cost = cost_wall;
    map[i][1].point = map[i][height].point = 0;
    map[i][1].type = map[i][height].type = 1;
  }
  for( i=1 ; i<=height ; i++ )
  {
    map[1][i].cost = map[width][i].cost = cost_wall;
    map[1][i].point = map[width][i].point = 0;
    map[1][i].type = map[width][i].type = 1;
  }
}

void move(int mode,pinball *ballPtr)
{
  int i,j;
  int cost;

  switch(mode)
  {
    case 0:
      for( i=ballPtr->x + 1 ; i<=width ; i++ )
      {
        if( map[i][ballPtr->y].type != 0 )
        {
          ballPtr->life -= i - ballPtr->x;
          if( ballPtr->life > 0 )
          {
            ballPtr->life -= map[i][ballPtr->y].cost;
            if( ballPtr->life > 0 )
            {
              ballPtr->point += map[i][ballPtr->y].point;
              ballPtr->x = i - 1;
              ballPtr->mode = 3;
            }
          }
          break;
        }
      }
      break;
    case 1:
      for( i=ballPtr->y + 1 ; i<=height ; i++ )
      {
        if( map[ballPtr->x][i].type != 0 )
        {
          ballPtr->life -= i - ballPtr->y;
          if( ballPtr->life > 0 )
          {
            ballPtr->life -= map[ballPtr->x][i].cost;
            if( ballPtr->life > 0 )
            {
              ballPtr->point += map[ballPtr->x][i].point;
              ballPtr->y = i - 1;
              ballPtr->mode = 0;
            }
          }
          break;
        }
      }
      break;
    case 2:
      for( i=ballPtr->x - 1 ; i>=1 ; i-- )
      {
        if( map[i][ballPtr->y].type != 0 )
        {
          ballPtr->life -= ballPtr->x - i;
          if( ballPtr->life > 0 )
          {
            ballPtr->life -= map[i][ballPtr->y].cost;
            if( ballPtr->life > 0 )
            {
              ballPtr->point += map[i][ballPtr->y].point;
              ballPtr->x = i + 1;
              ballPtr->mode = 1;
            }
          }
          break;
        }
      }
      break;
    case 3:
      for( i=ballPtr->y - 1 ; i>=1 ; i-- )
      {
        if( map[ballPtr->x][i].type != 0 )
        {
          ballPtr->life -= ballPtr->y - i;
          if( ballPtr->life > 0 )
          {
            ballPtr->life -= map[ballPtr->x][i].cost;
            if( ballPtr->life > 0 )
            {
              ballPtr->point += map[ballPtr->x][i].point;
              ballPtr->y = i + 1;
              ballPtr->mode = 2;
            }
          }
          break;
        }
      }
      break;
  }
}

joehuang92
New poster
Posts: 9
Joined: Sat Nov 18, 2006 4:56 pm
Location: Taiwan
Contact:

Post by joehuang92 » Sun Dec 24, 2006 4:51 am

By the way, I want to make sure some of the constraint to some tricky situation...

1. Ball on the wall
2. Ball out the wall
3. Ball on the bumper
4. Bumper on the bumper
5. Bumper on the wall

above, what situations are allowed?

To my knowing, all of them are not allowed, is that right?

stcheung
Experienced poster
Posts: 114
Joined: Mon Nov 18, 2002 6:48 am
Contact:

Post by stcheung » Thu Jan 04, 2007 8:43 am

None of those 5 scenarios is allowed in the input. And at any given time, you can guarantee that the ball will only be on a free space. For instance, in the sample input in problem statement, the ball never leaves (2,3) because it's bounded by the walls and the 2 bumpers at (2,2) and (3,3)

stcheung
Experienced poster
Posts: 114
Joined: Mon Nov 18, 2002 6:48 am
Contact:

Post by stcheung » Thu Jan 04, 2007 8:50 am

I believe the #1 cause for WA, which no other thread actually mentions, is that when you hit a bumper, BOTH the value and cost matter only when you still have a positive lifetime after subtracting 1 for making that movement.

In your case, you have this:
timeleft -= gettime(sx,sy);
if(timeleft < 1)return one_point;
one_point += getpoint(sx,sy);

So you are calculating the new lifetime before checking that you have a positive lifetime left.

The code should probably be this:
if(timeleft < 1)return one_point;
timeleft -= gettime(sx,sy);
one_point += getpoint(sx,sy);

stcheung
Experienced poster
Posts: 114
Joined: Mon Nov 18, 2002 6:48 am
Contact:

Post by stcheung » Thu Jan 04, 2007 9:03 am

You should process BOTH the value and cost of the bumper when your life is positive.

So something like this instead:
if(life>0) {
score += val[x+dx[dir]][y+dy[dir]];
life -= cost[x+dx[dir]][y+dy[dir]];
}

I also found it easier to leave x & y as is instead of decrementing everything.

stcheung
Experienced poster
Posts: 114
Joined: Mon Nov 18, 2002 6:48 am
Contact:

Post by stcheung » Thu Jan 04, 2007 9:25 am

Aengus, your code actually works fine if I chose C++ but throws Compile error for C...

stcheung
Experienced poster
Posts: 114
Joined: Mon Nov 18, 2002 6:48 am
Contact:

Post by stcheung » Thu Jan 04, 2007 9:32 am

I thought the 2 bumpers in the example are at (2,2) and (3,3) and the ball is at (2,3) so the diagram is this:

4 WWWW
3 WO B W
2 WB + W
1 WWWW
1 2 3 4

snar
New poster
Posts: 44
Joined: Thu Sep 01, 2005 12:14 pm
Location: Yerevan, Armenia

114 - Simulation Wizardry - Confused

Post by snar » Fri Jul 27, 2007 9:43 pm

Hello,
I searched in all previous topics related to this problem. But I have some questions.

The definition of "hitting" is the same for both walls and bumpers. To hit an obstacle you must move to the point ocuppied by it. That means lifetime decreses by 1 unit + cost of that obstacle. If it's lifetime>0, then you'll get the points, if the obstacle is a wall, otherwise no any points.

Let's use the sample input.

Code: Select all

4WWWW 
3W.BW 
2WB.W
1WWWW
 1234
The ball is in (2, 3), direction is up, lifetime is 3.

i. Trying to move to (2, 4). Lifetime becomes 2. A wall. Minus the wall cost, which is 0. No points added. Direction becomes right. The ball is still in (2, 3).
ii. Trying to move to (3, 3). Lifetime becomes 1. A bumber. Minus the bumper cost, which is 0. 1 point added. Direction becomes down. The ball is still in (2, 3).
iii. Trying to move to (2, 2). Lifetime becomes 0. The ball disappears from the grid.

Where's my mistake?

Thanks.
Narek Saribekyan

Jan
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Location: Dhaka, Bangladesh
Contact:

Post by Jan » Sat Jul 28, 2007 2:01 am

Then you should use existing thread.
Ami ekhono shopno dekhi...
HomePage

porker2008
New poster
Posts: 21
Joined: Wed Oct 08, 2008 7:04 am

MY GOD!!! - Problem about Q114

Post by porker2008 » Fri Oct 10, 2008 9:28 pm

I got AC when I submit my code on 3rd,Oct. However, I get WA now!!!!

Also, one of my friends got AC of Q114 and now he also gets WA!!!

Can somebody tell me why?

Leeon
New poster
Posts: 4
Joined: Thu Sep 04, 2008 4:09 pm

Re: MY GOD!!! - Problem about Q114

Post by Leeon » Thu Oct 16, 2008 8:13 am

Maybe there was some rejudgement (sometimes some of problems are judged again, because bugs were found in judging system or in problem test set).
try these inputs: http://fdemesmay.dyndns.org/cs/acm/v1/114.in
and check it out with these ouputs: http://fdemesmay.dyndns.org/cs/acm/v1/114.out

porker2008
New poster
Posts: 21
Joined: Wed Oct 08, 2008 7:04 am

Re: MY GOD!!! - Problem about Q114

Post by porker2008 » Fri Oct 17, 2008 7:27 am

I got AC now.

Anyway, thank you very much.

Post Reply

Return to “Volume 1 (100-199)”