DWITE Online Computer Programming Contest

Wandering Billy

November 2011
Problem 1

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 < 100,000.

The output file OUT1.txt will contain 5 lines of output, each with two space-separated integers 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