114 - Simulation Wizardry
Moderator: Board moderators
-
- New poster
- Posts: 19
- Joined: Fri Oct 04, 2002 7:50 pm
- Location: Warsaw, Poland
-
- 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[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]
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]
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:
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?
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.
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.
Hi again! I've already solved this one, but my first atempt was Wrong Answer.
Let me draw the table of the sample input:
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
Let me draw the table of the sample input:
The X are walls B are bumpers.XXXX
X_BX
XB_X
XXXX
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

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

http://online-judge.uva.es/board/viewto ... highlight=
Good luck.

I stay home. Don't call me out.
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.
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 */
lifetime maybe very big.
please call me hongyan.
my QQ number is 76296127
my Email address is sanwushuosi@163.com
welcome for connect me!!
my QQ number is 76296127
my Email address is sanwushuosi@163.com
welcome for connect me!!
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...
114 - Simulation Wizardry
I hope somebody can help me... I don't know why i got WA.
Please, help
My code:
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;
}
I can't say that i understood this totally...but the catch here is that you _only_ hit the bumper if the life total _after_ moving is still positive.
but this is right sequence, how it working:
hope it will help...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;
}
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[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;
}