11519 - Logo 2

Moderator: Board moderators

armansuleimenov
New poster
Posts: 15
Joined: Tue Sep 25, 2007 3:07 am
Location: Astana, Kazakhstan
Contact:

11519 - Logo 2

Our team submitted this problem 5 times during the contest, and got WA each time. The idea behind our approach is the following: if the missing number is in the command "lt" or "rt", just brute-force over all possible degrees [0,359] and return the degree with which we come back to point (0,0).

If the missing number is in the command "fd" or "bk", then simulate the walk until "?" (store the coordinates in (xx,yy) ), then simulate the walk after "?" (starting from (0,0), then we finally reach (x,y), then move the coordinate system to make final point (0,0), hence the point where we started is (-x, -y)). Finally the answer is sqrt ( (xx+x)*(xx+x) + (yy+y)*(yy+y) ).

Is there something wrong with the logic or it is precision problem?

My code:

Code: Select all

``````#define For(i,b) for(int i = 0; i < (int)b; ++i)
#define Fori(i,a,b) for(int i = a; i < (int)b; ++i)
#define mp make_pair

const long double EPS = 1e-9L;
const long double PI = acos(-1.0);

#define sqr(a) ((a)*(a))
using namespace std;

typedef long long ll;

long double dist(long double x1, long double y1, long double x2, long double y2)
{
return sqrt(sqr(x1-x2)+sqr(y1-y2));
}

ll f(ll val)
{
return ((labs(val)/360)+1) * 360;
}

pair<string, ll> a[1010];
ll n,idx,degree;

pair<long double,long double> go()
{
ll deg=0;
long double x=0,y=0;
For(i,n)
{
string s;ll r;
s=a[i].first;
r=a[i].second;
if(r==-1) r = degree;
//	  db(x),db(y);
switch(s[0])
{
break;
break;
case 'l': deg = (deg+r) % 360;
break;
case 'r':deg = (deg-r+f(r)) % 360;
break;
default:
break;
}
//	  db(deg),db(x),db(y);
}
return mp(x,y);
}

string itos (int i) {stringstream s; s << i; return s.str();}
ll stoi (string s) {istringstream in(s); ll ret; in >> ret; return ret;}

int main ()
{
int t;
cin>>t;
For(z,t)
{
scanf("%lld\n",&n);
ll res=-1;
string s,cmd,x;
idx=-1;
For(i,n)
{
getline(cin,s);
istringstream in(s);
in>>cmd>>x;
if(x=="?")
{
a[i]=mp(cmd,-1);
idx=i;
}
else
{
a[i]=mp(cmd,stoi(x));
}
}
if((a[idx].first=="lt") || (a[idx].first=="rt"))
{
for(degree=0;degree<360;++degree)
//	  degree=90;
{
//  a[idx].second=degree;
pair<long double,long double> cur = go();
//      db(cur.first),db(cur.second);
if(fabs(cur.first)<EPS && fabs(cur.second)<EPS)
{
res=degree;
goto L;
}
}
}
else
{
ll deg=0;
long double x=0,y=0;
For(i,idx)
{
string s;ll r;
s=a[i].first;
r=a[i].second;
//	  if(r==-1) r = degree;
switch(s[0])
{
break;
break;
case 'l': deg = (deg+r) % 360;
break;
case 'r':deg = (deg-r+f(r)) % 360;
break;
default:
break;
}
//	  db(deg),db(x),db(y);
}
long double xx=x,yy=y;
x=0,y=0;
//      int d=deg;
Fori(i,idx+1,n)
{
string s;ll r;
s=a[i].first;
r=a[i].second;
//	  if(r==-1) r = degree;
switch(s[0])
{
break;
break;
case 'l': deg = (deg+r) % 360;
break;
case 'r':deg = (deg-r+f(r)) % 360;
break;
default:
break;
}
//	  db(deg),db(x),db(y);
}
long double X = -1. * x, Y = -1. * y;
res = (ll)dist(X,Y,xx,yy);
} // of else
L: cout<<res<<endl;
}
return 0;
}

``````

Leonid
Experienced poster
Posts: 146
Joined: Thu Dec 22, 2005 5:50 pm
Contact:

Re: Waterloo ACM Programming Contest Fall 2: Logo 2

You probably have a bug somewhere
My idea is the same...

azk84
New poster
Posts: 14
Joined: Sat Sep 13, 2008 7:50 pm
Location: Tehran
Contact:

Re: Waterloo ACM Programming Contest Fall 2: Logo 2

I did the same for "fd" and "bd", but for "lt" and "rt" I just save current x & y values, when ? comes, and then simply omit it. Finally, I just calculate the degree between this two lines: a line from (savedX,savedY) to (0,0), and a line from (savedX,savedY) to (FinishX, FinishY). I got AC at first try with this approach.

Abednego
A great helper
Posts: 281
Joined: Tue Sep 10, 2002 5:14 am
Location: Mountain View, CA, USA
Contact:

Re: Waterloo ACM Programming Contest Fall 2: Logo 2

I can't seem to get it either. Here is my input file, in case somebody finds it useful.

Code: Select all

``````7
5
fd 100
lt 120
fd ?
lt 120
fd 100
6
fd 3
rt 90
fd 4
rt 90
rt ?
fd 5
3
fd 100
lt ?
fd 100
4
fd 100
lt 180
rt ?
fd 100
7
fd 100
rt 90
fd 100
rt 90
bk ?
rt 90
fd 100
5
fd 100
lt 120
fd 100
lt ?
fd 100
5
fd 100
lt 120
fd 100
rt ?
fd 100
``````

Code: Select all

``````100
53
180
0
-100
120
240
``````
I doubt they have a special judge for this problem, so make sure you never print "-0" instead of "0". (I had that problem with case #4.)

Does anyone have trickier test cases?
If only I had as much free time as I did in college...

Abednego
A great helper
Posts: 281
Joined: Tue Sep 10, 2002 5:14 am
Location: Mountain View, CA, USA
Contact:

Re: Waterloo ACM Programming Contest Fall 2: Logo 2

One more tricky case:

Code: Select all

``````1
1
bk ?
``````
Make sure you print "0" and not "-0". I'm still at WA though.
If only I had as much free time as I did in college...

kantaki
New poster
Posts: 10
Joined: Tue May 29, 2007 6:18 pm

11519 - Logo 2

I think that solution of this problem is calculating the angle or the distance.
But I've got WA.

Code: Select all

``````I've got AC.
``````
I didnt think range of y < 0.

forthright48
New poster
Posts: 37
Joined: Wed Mar 14, 2012 11:57 am