11519 - Logo 2

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

Moderator: Board moderators

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

11519 - Logo 2

Post by armansuleimenov » Sun Oct 05, 2008 12:55 am

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 rad(a) ((1.*(a)*PI)/180.)
#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])
	    {
	    case 'f': x+=1.*r*cos(rad(deg)); y+=1.*r*sin(rad(deg));
	      break;
	    case 'b': x+=1.*r*cos(rad((deg+180)%360)); y+=1.*r*sin(rad((deg+180)%360));
	      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])
	    {
	    case 'f': x+=1.*r*cos(rad(deg)); y+=1.*r*sin(rad(deg));
	      break;
	    case 'b': x+=1.*r*cos(rad((deg+180)%360)); y+=1.*r*sin(rad((deg+180)%360));
	      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])
	    {
	    case 'f': x+=1.*r*cos(rad(deg)); y+=1.*r*sin(rad(deg));
	      break;
	    case 'b': x+=1.*r*cos(rad((deg+180)%360)); y+=1.*r*sin(rad((deg+180)%360));
	      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

Post by Leonid » Sun Oct 05, 2008 7:40 am

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

Post by azk84 » Sun Oct 05, 2008 5:08 pm

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.

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

Post by Abednego » Thu Oct 23, 2008 6:33 am

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
and my answers:

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

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

Post by Abednego » Thu Oct 23, 2008 6:43 am

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

Post by kantaki » Sat Mar 21, 2009 5:33 pm

I think that solution of this problem is calculating the angle or the distance.
But I've got WA.
Please tell me some advice.

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
Location: Bangladesh
Contact:

Re: 11519 - Logo 2

Post by forthright48 » Fri Jan 17, 2014 8:31 pm

Finally AC! Had to use eps = 1e-2. So much precision error :(
What ever happens, happens for good. Even when we get WA :p
http://www.forthright48.com

Post Reply

Return to “Volume 115 (11500-11599)”