11509 - Touring Robot

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
baodog
Experienced poster
Posts: 202
Joined: Wed Jul 04, 2007 6:53 am

11509 - Touring Robot

Post by baodog » Thu Oct 02, 2008 8:09 am

I cannot understand this problem.
1) You have to follow the order of the points? 0->1->2->3 ... ->n-1->0 and facing 1?
2) The sample IO makes no sense to me. In the first example,
you go (0,0) -> (3,0), turn -> (1,0) -> (0,0) turn to face (1,0).
That's 2 turns!

Help is appreaciated to explain the 2 examples. Thanks!

zhouerjin
New poster
Posts: 5
Joined: Wed Oct 01, 2008 4:52 pm

Re: 11509 - Touring Robot

Post by zhouerjin » Thu Oct 02, 2008 12:26 pm

in this problem a turn means 2*pi

User avatar
andmej
Experienced poster
Posts: 158
Joined: Sun Feb 04, 2007 7:45 pm
Location: Medellin, Colombia

Re: 11509 - Touring Robot

Post by andmej » Thu Oct 02, 2008 5:10 pm

I think the problem description is very ambiguous too. Anyway...
The robot must visit all points in order.
The sequence of points is "circular", in the sense that after visiting the last point the robot must visit again the first point.
The robot finishes looking in the same direction that he started. (That's why the answer is always an integer).
What you have to print is the number of 360º rotations that the robot will make. In other words, the total number of degrees "swept" by the robot's line of sight divided by 360 (Or 2*pi).

Some more test cases:

Code: Select all

4
0 0
1 0
1 1
0 1
3
0 0
1 1
2 0
0
Correct output is:

Code: Select all

1
2
Runtime errors in Pascal are reported as Wrong Answers by the online judge. Be careful.

Are you dreaming right now?
http://www.dreamviews.com

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

Re: 11509 - Touring Robot

Post by azk84 » Fri Oct 03, 2008 3:27 pm

My program calculates angle of new direction and subtracts it from angle of previous direction and adds the result to a variable that keeps total degrees that the robot turned, when a new point is read from input. And finally it divides it by 2*pi and rounds it to nearest integer.
I tested it for every test case that I could, and it gives correct answer, but I got WA :( . I think it's because of floating points. Is there another way that doesn't use floating point operations? Plz help me.

User avatar
andmej
Experienced poster
Posts: 158
Joined: Sun Feb 04, 2007 7:45 pm
Location: Medellin, Colombia

Re: 11509 - Touring Robot

Post by andmej » Fri Oct 03, 2008 3:35 pm

How are you calculating angles? I used atan2 and doubles for the calculations and then print the answer like this (without rounding):

Code: Select all

printf("%.0lf\n", ans/(2*pi));
Runtime errors in Pascal are reported as Wrong Answers by the online judge. Be careful.

Are you dreaming right now?
http://www.dreamviews.com

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

Re: 11509 - Touring Robot

Post by azk84 » Fri Oct 03, 2008 9:34 pm

Thanks andmej, I changed my code to print with your printf and I used atan2 instead of atan (I haven't known that atan2 exists and is so simple, special thanks to you :) ). But I still get WA. Could you give some more tricky test cases plz?

User avatar
andmej
Experienced poster
Posts: 158
Joined: Sun Feb 04, 2007 7:45 pm
Location: Medellin, Colombia

Re: 11509 - Touring Robot

Post by andmej » Sat Oct 04, 2008 6:09 pm

Try these cases:

Code: Select all

3
-10 -2
4 -6
1 7
9
7 9
2 10
-5 4
0 -3
10 10
-7 7
2 -7
-4 0
4 7
4
-6 2
6 5
-7 4
3 9
5
-4 0
-9 0
1 6
7 4
3 -2
10
7 8
-8 4
9 -9
3 -7
-7 -7
8 -1
7 0
10 9
-2 -3
-3 -2
6
10 0
-10 -10
0 -10
-6 -10
9 -3
-2 -7
7
4 -1
-4 6
-8 -7
9 1
-8 0
-4 -2
6 -9
3
-3 -8
-9 0
-8 4
5
7 2
-7 -2
3 8
1 0
0 0
5
-7 -1
-2 2
-2 1
7 10
-8 6
0
My output:

Code: Select all

1
4
2
3
5
3
3
2
3
2
Runtime errors in Pascal are reported as Wrong Answers by the online judge. Be careful.

Are you dreaming right now?
http://www.dreamviews.com

omar_elruby
New poster
Posts: 2
Joined: Mon Jan 05, 2009 8:34 pm

Re: 11509 - Touring Robot

Post by omar_elruby » Wed Jan 07, 2009 11:04 am

My program gives right output for the above test cases, however i'm still getting WA :(:( ...
are there other critical inputs to test my program ??!!!!

waiting for help :) ...
thanks in advance :) ...

red_apricot
New poster
Posts: 48
Joined: Sun Jun 22, 2014 6:14 am

Re: 11509 - Touring Robot

Post by red_apricot » Sun Aug 23, 2015 11:48 am

I believe there are test cases with n > 1024, I got AC when I changed my N from 0x400 to (1<<20).

Post Reply

Return to “Volume 115 (11500-11599)”