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
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.
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.

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;
int v, c;
int x, y, d, l;

int dx = {1, 0, -1, 0};
int dy = {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
Experienced poster
Posts: 215
Joined: Sat Jul 10, 2004 4:31 pm
Location: Shanghai, China

Who can explain me the 114?

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:
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
Experienced poster
Posts: 215
Joined: Sat Jul 10, 2004 4:31 pm
Location: Shanghai, China
I see. I'll try it. Thank you again.
I stay home. Don't call me out.

ImLazy
Experienced poster
Posts: 215
Joined: Sat Jul 10, 2004 4:31 pm
Location: Shanghai, China
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

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,cost;
char polje;

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[i]='X';
for (i=0;i<n;i++) polje[m-1][i]='X';
for (i=0;i<m;i++) polje[i]='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 !!!!

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
Experienced poster
Posts: 215
Joined: Sat Jul 10, 2004 4:31 pm
Location: Shanghai, China
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

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

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

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

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

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;

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
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?

Code: Select all

#include <iostream>

using namespace std;

struct point{
int value;
int cost;
bool is_wall;
bool is_bumper;

}grid;

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].is_wall = true;
grid[i].cost =wallcost;
grid[i][n].is_wall = true;
grid[i][n].cost = wallcost;
}

for(i = 1; i <= n;i++)
{
grid[i].is_wall = true;
grid[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;
}