DRAGONCU - Dragon Curves

no tags 

Define r(s) to be the complement of the reverse of the binary string s. i.e. Reverse s and then convert all 1's to 0's and all 0's to 1's.
Further define a sequence of binary string as follow: s0 = 1 and sn = sn-11r(sn-1). i.e.
s0 = 1
s1 = 110
s2 = 1101100
s3 = 110110011100100
...

We then program a robot to move at a steady speed of 1 unit per second and make a right-angle turn according to the characters of s10 after every unit of movement. At the kth turn, the robot turns to left if the kth character of s10 is a 1, and to right otherwise. The figure below shows the whole path of the robot.

The robot is placed at the origin (the small circle) and face east originally. It ends up at the coordinates (-32,32) (the small spot) after 2048 seconds. The path of the robot is known as a dragon curve, a pretty well-known pattern of fractal.

If the robot is now programmed with input string s30 (with identical initial conditions as above), it will keep moving and then stop after 231 seconds. We want to know the location of the robot at any given time.


Input Format:
Input consists of multiple problem instances. Each instance consists of a single non-negative integer n, where n <= 109. The input data is terminated by a "-1". There will be less than 5000 test cases.

Output Format:
For each input integer n, print out the location of the robot right after n second since the robot starts its journey with input string s30. The location should be printed with the format "(x,y)" in a single line.

Sample Input:
1
2
3
2048
1000000000
-1

Sample Output:
(1,0)
(1,1)
(0,1)
(-32,32)
(9648,-31504)

hide comments
BLB: 2013-04-16 15:45:04

always gives NZEC even when I'v done return 0;


Added by:Prasanna
Date:2007-10-08
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ERL JS-RHINO NODEJS PERL6 VB.NET
Resource:NITT ACM ICPC Local Contest 2007 [Tsinghua]