November 2011
Problem 1
Wandering Billy

Once upon a time, Little Billy romped about, passing by candy stores. However, that candy store has since shut down, and he has been deprived of the very essence of his life. In light of this existential crisis, his walks have never been quite the same. Today, he is aimlessly walking from his home (0, 0) to infinity, in search of his lost soul.

Billy's concerned parents would like to know where Billy is after N steps. They know that he can take two types of steps: one unit down or one unit to the right. He follows a predictable pattern: 1 step right, 2 steps down, 3 steps right, 4 steps down, and so on. That is, the sequence of steps begins as follows: R D D R R R D D D D.

The input file DATA1.txt will contain 5 test cases, each consisting of one line, containing the number of steps 0 <= N < 100000.

The output file OUT1.txt will contain 5 lines of output with two space-separated integers each, representing Billy's coordinates after N steps in the corresponding test case.

Sample Input:
Sample Output:
0 0
1 0
1 -1
1 -2
2 -2