11519 - Logo 2

[armansuleimenov]

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]

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

[azk84]

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]

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?

[Abednego]

One more tricky case:

Code: Select all

1
1
bk ?

Make sure you print "0" and not "-0". I'm still at WA though.

[kantaki]

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]

Finally AC! Had to use eps = 1e-2. So much precision error