587 - There's treasure everywhere!

All about problems in Volume 5. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

yatsen
Learning poster
Posts: 68
Joined: Fri Nov 23, 2001 2:00 am
Location: taiwan

Post by yatsen » Fri Dec 07, 2001 4:01 am

I think 587 is an easy problem. But I got WA. Could anyone help me? The following is my source code.

#include <stdio.h>
#include <math.h>
#include <ctype.h>
#include <string.h>
int main()
{
char map[300],*dir,*m;
double sq2,x,y;
int s,caseno=1;

sq2=sqrt(0.5);

while (scanf("%s",map) && strcmp(map,"END"))
{
x=y=0.0;
m=map;
while (*m)
{ s=0;
while (isdigit(*m)) s=10*s+(*m++ - '0');
for (dir=m;isalpha(*m);m++);
if (*m==',') *m++=0; else *m=0;
if (strcmp(dir,"N")==0) y+=s;
if (strcmp(dir,"S")==0) y-=s;
if (strcmp(dir,"E")==0) x+=s;
if (strcmp(dir,"W")==0) x-=s;
if (strcmp(dir,"NE")==0) {x+=sq2*s; y+=sq2*s;}
if (strcmp(dir,"NW")==0) {x-=sq2*s; y+=sq2*s;}
if (strcmp(dir,"SE")==0) {x+=sq2*s; y-=sq2*s;}
if (strcmp(dir,"SW")==0) {x-=sq2*s; y-=sq2*s;}
}
printf("Map #%dn",caseno++);
printf("The treasure is located at (%.3f,%.3f).n",x,y);
printf("The distance to the treasure is %.3f.nn",sqrt(x*x+y*y));
}
return 0;
}

junjieliang
Experienced poster
Posts: 169
Joined: Wed Oct 31, 2001 2:00 am
Location: Singapore

Post by junjieliang » Fri Dec 07, 2001 10:45 am

Try initialising x and y to 10e-12 instead of 0.

yatsen
Learning poster
Posts: 68
Joined: Fri Nov 23, 2001 2:00 am
Location: taiwan

Post by yatsen » Tue Dec 11, 2001 2:01 am

I got accepted after initialising x and y to 10e-12 instead of 0.
But I don't know why. Could you tell me?

junjieliang
Experienced poster
Posts: 169
Joined: Wed Oct 31, 2001 2:00 am
Location: Singapore

Post by junjieliang » Tue Dec 11, 2001 6:02 am

I was told by someone else too, in the old board... but I think it's because of some precision error, maybe the input has distances like 0.9994999..., where the small difference counts.

galgamet
New poster
Posts: 5
Joined: Thu May 09, 2002 9:29 pm

587

Post by galgamet » Tue May 21, 2002 1:05 pm

The judge told me that this program ran for 0.000 seconds and gave a WA :evil:

Code: Select all

#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include <math.h>
#include <ctype.h>

int main(void)
{
    char map[201];
    char dir[3];
    int c = 0;
    int d;
    int i;
    float x, y, s;

    s = sqrt(0.5);
    dir[2] = 0;
    i = 0;

    while (scanf("%s", map) && strcmp(map, "END")) {
        i++;
        x = 0.0;
        y = 0.0;
        c = 0;
        d = 0;

        while (map[c] != '.') {
            if (isdigit(map[c]))
                d = (d*10) + (map[c]-'0');

            if (isalpha(map[c])) {
                dir[0] = map[c];
                if (isalpha(map[c+1])) {
                    dir[1] = map[++c];
                } else dir[1] = 0;

                if (!strcmp(dir, "N")) y += (float)d;
                if (!strcmp(dir, "S")) y -= (float)d;
                if (!strcmp(dir, "E")) x += (float)d;
                if (!strcmp(dir, "W")) x -= (float)d;
                if (!strcmp(dir, "NE")) { x += s * (float)d; y+= s * (float)d; }
                if (!strcmp(dir, "NW")) { x -= s * (float)d; y+= s * (float)d; }
                if (!strcmp(dir, "SE")) { x += s * (float)d; y-= s * (float)d; }
                if (!strcmp(dir, "SW")) { x -= s * (float)d; y-= s * (float)d; }
            }

            if (map[c] == ',') {
                d = 0;
                c++;
                continue;
            }

            c++;
        }

        printf("Map #%i\n", i);
        printf("The treasure is located at (%0.3f,%0.3f).\n", x, y);
        printf("The distance to the treasure is %0.3f.\n\n", sqrt(x*x + y*y));
    }

    return 0;
}

10153EN
Experienced poster
Posts: 148
Joined: Sun Jan 06, 2002 2:00 am
Location: Hong Kong
Contact:

HI~

Post by 10153EN » Tue May 21, 2002 6:54 pm

I could tell you there's precision error~~

Try to make the precision error smaller and your code will be got accepted.

Magus
New poster
Posts: 5
Joined: Thu May 09, 2002 9:34 am

Post by Magus » Thu Jun 06, 2002 3:55 pm

Can You tell me what is wrong? I compared output of my program with the output of my friend program for some test data generated by us.
Data are identical but his code is accepted and mine got WA :(

#include <stdio.h>
#include <math.h>
#include <string.h>

int main()
{
char w[205];
int map,i;
int x,y,px,py,step;
double fx,fy,fp;

fp=(sqrt(2)/2);
map=0;
while(gets(w))
{
if( strcmp( w, "END" ) == 0 ) break;
map++;
i=0;
x=y=0;
px=py=0;
while(w[i]!='.')
{
step=0;
while((w[i]>='0') && (w[i]<='9'))
{
step*=10;
step+=(w[i]-'0');
i++;
}
switch(w[i++])
{
case 'W':
x-=step;
break;
case 'N':
if(w[i]=='W')
{
px-=step;
py+=step;
i++;
}else
if(w[i]=='E')
{
px+=step;
py+=step;
i++;
}else y+=step;
break;
case 'E':
x+=step;
break;
case 'S':
if(w[i]=='W')
{
px-=step;
py-=step;
i++;
}else
if(w[i]=='E')
{
px+=step;
py-=step;
i++;
}else y-=step;
break;
}
}
fx=x+px*fp;
fy=y+py*fp;
printf("Map #%d\n",map);
printf("The treasure is located at (%0.3f,%0.3f).\n",fx,fy);
printf("The distance to the treasure is %0.3f.\n\n",sqrt(fx*fx+fy*fy));
}
return 0;
}

please help!!!

ali_chan
New poster
Posts: 3
Joined: Wed Aug 07, 2002 9:30 am
Location: Indonesia
Contact:

Post by ali_chan » Thu Aug 22, 2002 10:49 am

change %0.3f to %.3f, I accepted because of this.

ali.

ali_chan
New poster
Posts: 3
Joined: Wed Aug 07, 2002 9:30 am
Location: Indonesia
Contact:

587 treasure every where

Post by ali_chan » Thu Aug 22, 2002 11:02 am

change %0.3f to %.3f, I accepted because of this.

ali.

supermin
New poster
Posts: 37
Joined: Sat Oct 12, 2002 9:54 am
Location: (Taiwan)
Contact:

Post by supermin » Thu Jan 09, 2003 12:16 pm

P587

I use double for x,y ,and I got WA.
Instead,I use long double.I got AC.

ayaw
New poster
Posts: 18
Joined: Fri May 23, 2003 3:52 pm
Contact:

Post by ayaw » Mon May 26, 2003 10:38 am

i also got WA

here is my code :

Code: Select all

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

main() {
	int i,j,n,count=1;
	float dx,xx,yy,d;
	char *x,step[999],dir[999],buff[999],buf[999];
	dx=sqrt(2)/2;
	while(1) {
		gets(buf);
		if(strcmp(buf,"END")==0) return 0;
		x = buf;
		xx = 0, yy=0;
		while(1) {
			sscanf(x,"%[^.,\n]s",buff);
			x+=(strlen(buff));
			sscanf(buff,"%[0123456789]s",step);
			sscanf(buff+strlen(step),"%s",dir);
			if(strlen(dir)==2) d = dx;
			else d = 1;
			for(i=0;i<atoi(step);i++) {
				for(j=0;j<dir[j];j++) {
					switch(dir[j]) {
					  case 'S' : yy+=-d; break;
					  case 'N' : yy+=d; break;
					  case 'W' : xx+=-d; break;
					  case 'E' : xx+=d; break;
					}
				}
			}
			if(x[0]=='.') break;
			else x++;
		 }
		 printf("Map #%d\n",count++);
		 printf("The treasure is located at (%.3f,%.3f).\n",xx,yy);
		 printf("The distance to the treasure is %.3f.\n",sqrt(xx*xx+yy*yy));
	}
}
can u help me!!!
peace...

Rene
New poster
Posts: 13
Joined: Mon May 05, 2003 4:40 am
Location: Shanghai,China

Post by Rene » Tue Aug 05, 2003 6:32 pm

i think if you try to init x and y as 10e-6,you will get AC.
GOOD LUCK. :lol:
Le roi c'est loi,le loi c'est roi

a_jain
New poster
Posts: 3
Joined: Sun Oct 20, 2002 7:36 pm

587 WA

Post by a_jain » Fri Jun 11, 2004 2:35 pm

Can somebody tell me why the following code is wrong:

#include<iostream>
#include<vector>
#include<string>
#include<cmath>

using namespace std;

#define PI 3.14159265
#define ANGLE (PI*45/180)

int main()
{

int steps, count = 1;
char d1, d2;
char temp;
cin >> temp;

while(temp != 'E')
{
vector< pair< double, pair < char, char > > > list;
pair< double, pair< char, char > > t;

cin.putback(temp);

cin >> steps;
cin >> d1 >> d2;
bool addLast = false;
while(d2 != '.')
{
if(d2 != ',' && d2 != '.')
{
t.first = steps;
t.second.first = d1;
t.second.second = d2;
cin >> d2;
}
else
{
t.first = steps;
t.second.first = d1;
t.second.second = 'Z';
}

list.push_back(t);
if(d2 != '.')
{
cin >> steps >> d1 >> d2;
if(d2 == '.')
addLast = true;
}
}

if(addLast)
{
t.first = steps;
t.second.first = d1;
t.second.second = 'Z';
list.push_back(t);
}
/*
for(int i = 0 ; i < list.size(); i++)
{
cerr << list.first << list.second.first
<< list.second.second << ",";

cerr << endl;
*/
double X = 10e-12, Y = 10e-12, angle;



for(int i = 0; i < list.size(); i++)
{
// cerr << list.first << list.second.first
// << list.second.second << endl;
if(list.second.second == 'Z')
{
if(list.second.first == 'N')
Y += list.first;
else if(list.second.first == 'S')
Y -= list[i].first;
else if(list[i].second.first == 'E')
X += list[i].first;
else if(list[i].second.first == 'W')
X -= list[i].first;
}
else
{
if(list[i].second.first == 'N' && list[i].second.second == 'W')
{
X -= cos(ANGLE) * double(list[i].first);
Y += sin(ANGLE) * double(list[i].first);
// Y += tempY;
// X -= tempX;
}
else if(list[i].second.first == 'N' && list[i].second.second == 'E')
{
X += cos(ANGLE) * double(list[i].first);
Y += sin(ANGLE) * double(list[i].first);
// Y += tempY;
// X += tempX;
}
else if(list[i].second.first == 'S' && list[i].second.second == 'E')
{
X += cos(ANGLE) * double(list[i].first);
Y -= sin(ANGLE) * double(list[i].first);
// Y -= tempY;
// X += tempX;
}
else if(list[i].second.first == 'S' && list[i].second.second == 'W')
{
X -= cos(ANGLE) * double(list[i].first);
Y -= sin(ANGLE) * double(list[i].first);
// Y -= tempY;
// X -= tempX;
}
}
// cerr << X << " " << Y << endl;
}

cout.setf(ios::showpoint);
cout.setf(ios::fixed);
cout.precision(3);
double distance = sqrt(double(Y * Y + X * X));
cout << "Map #" << count << endl;
cout << "The treasure is located at (" << X << "," << Y << ")." << endl;
cout << "The distance to the treasure is " << distance <<"." << endl << endl;
count++;
cin >> temp;
}
return 1;
}[cpp][/cpp]

j_hines
New poster
Posts: 5
Joined: Mon May 24, 2004 6:09 pm

587 WA why?

Post by j_hines » Sun Jun 13, 2004 6:04 pm

Anyone know why this is WA?

[cpp]
#include <iostream>
#include <vector>
#include <cmath>
#include <cctype>
using namespace std;

const double PI=3.1415926535898;
int main()
{
double x, y, d, real;
char ch;
vector<char> map;
int mapNum=0;

while(true)
{
x=0; y=0; d=0;
do
{
cin.get(ch);
map.push_back(ch);
}while(ch != '.' && ch != '\n');
cin.get();

if(map[0] == 'E' && map[1] =='N' && map[2] == 'D')
exit(0);


for(int i=0; i<map.size(); i++)
{
if(isdigit(map))
{
d = (d*10) + (map - '0');
}
else if(isalpha(map) && map != ',' && map != '.')
{
switch(map)
{
case 'N':
if(map[i+1] == 'E')
{
x += (d*sin(PI/4));
y += (d*sin(PI/4));
}
else if(map[i+1] == 'W')
{
x -= (d*sin(PI/4));
y += (d*sin(PI/4));
}
else if(isdigit(map[i-1]))
y += d;
break;
case 'E':
if(isdigit(map[i-1]))
x += d;
break;
case 'S':
if(map[i+1] == 'E')
{
x += (d*sin(PI/4));
y -= (d*sin(PI/4));
}
else if(map[i+1] == 'W')
{
x -= (d*sin(PI/4));
y -= (d*sin(PI/4));
}
else if(isdigit(map[i-1]))
y -= d;
break;
case 'W':
if(isdigit(map[i-1]))
x -= d;
break;

}
d=0;
}

}


cout.setf(ios::fixed);
cout.precision(3);
real = sqrt(pow(x,2) + pow(y,2));

cout << "Map #" << ++mapNum << endl;
cout << "The treasure is located at (" << x << "," << y << ")." << endl;
cout << "The distance to the treasure is " << real << endl << endl;

map.clear();
}


return 0;
}
[/cpp]

jackie
New poster
Posts: 47
Joined: Tue May 04, 2004 4:24 am

Post by jackie » Tue Aug 10, 2004 12:42 pm

try this input
10NW,10NE,10SW,10SE.
if you use windows + VC++ you may get 0.000 but with linux + gcc you get -0.000 which causes WA.

The reason is the difference between the two compiler when processing 'double' multiplication or you can just mention it precision error.

solution:
you may initial x, y with 1e-8(or other small number)

Post Reply

Return to “Volume 5 (500-599)”