SP1876 DRAGONCU - Dragon Curves

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: s $ _{0} $ = 1 and s $ _{n} $ = s $ _{n-1} $ 1r(s $ _{n-1} $ ). i.e. s $ _{0} $ = 1 s $ _{1} $ = 110 s $ _{2} $ = 1101100 s $ _{3} $ = 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 s $ _{10} $ after every unit of movement. At the kth turn, the robot turns to left if the kth character of s $ _{10} $ 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 s $ _{30} $ (with identical initial conditions as above), it will keep moving and then stop after 2 $ ^{31} $ 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**

N/A

N/A