587

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

Moderator: Board moderators

Postby 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;
}
yatsen
Learning poster
 
Posts: 68
Joined: Fri Nov 23, 2001 2:00 am
Location: taiwan

Postby junjieliang » Fri Dec 07, 2001 10:45 am

Try initialising x and y to 10e-12 instead of 0.
junjieliang
Experienced poster
 
Posts: 169
Joined: Wed Oct 31, 2001 2:00 am
Location: Singapore

Postby 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?
yatsen
Learning poster
 
Posts: 68
Joined: Fri Nov 23, 2001 2:00 am
Location: taiwan

Postby 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.
junjieliang
Experienced poster
 
Posts: 169
Joined: Wed Oct 31, 2001 2:00 am
Location: Singapore

587

Postby 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;
}
galgamet
New poster
 
Posts: 5
Joined: Thu May 09, 2002 9:29 pm

HI~

Postby 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.
10153EN
Experienced poster
 
Posts: 148
Joined: Sun Jan 06, 2002 2:00 am
Location: Hong Kong

Postby 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!!!
Magus
New poster
 
Posts: 5
Joined: Thu May 09, 2002 9:34 am

Postby 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

587 treasure every where

Postby ali_chan » Thu Aug 22, 2002 11:02 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

Postby 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.
supermin
New poster
 
Posts: 37
Joined: Sat Oct 12, 2002 9:54 am
Location: (Taiwan)

Postby 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...
ayaw
New poster
 
Posts: 18
Joined: Fri May 23, 2003 3:52 pm

Postby 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
Rene
New poster
 
Posts: 13
Joined: Mon May 05, 2003 4:40 am
Location: Shanghai,China

587 WA

Postby 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[i].first << list[i].second.first
<< list[i].second.second << ",";

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



for(int i = 0; i < list.size(); i++)
{
// cerr << list[i].first << list[i].second.first
// << list[i].second.second << endl;
if(list[i].second.second == 'Z')
{
if(list[i].second.first == 'N')
Y += list[i].first;
else if(list[i].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]
a_jain
New poster
 
Posts: 3
Joined: Sun Oct 20, 2002 7:36 pm

587 WA why?

Postby 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[i]))
{
d = (d*10) + (map[i] - '0');
}
else if(isalpha(map[i]) && map[i] != ',' && map[i] != '.')
{
switch(map[i])
{
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]
j_hines
New poster
 
Posts: 5
Joined: Mon May 24, 2004 6:09 pm

Postby 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)
jackie
New poster
 
Posts: 47
Joined: Tue May 04, 2004 4:24 am

Next

Return to Volume V

Who is online

Users browsing this forum: No registered users and 1 guest