디지털 세계에 익숙치 않은 소들이 이진수를 사용하여 계산하는 계산기를 만들려고 노력하고 있다. 그런데 2 진수가 아니라 -2 진수 체계를 사용하는 계산기를 만들었다. 이 수 체계를 사용한다면 부호를 사용할 필요가 없기 때문에 그들은 아주 만족하고 있다.
당신이 알고 있듯이 r 진법을 사용한다면 오른쪽에서 왼쪽으로 각 자리의 가중치는 r^0 , r^1 , r^2 ,... 이다.
-2 진법 체계에서는 오른쪽에서 왼쪽으로 가중치는 1 , -2 , 4 , -8 , 16 , -32 ,... 가 된다.
그러므로 1 부터 차례대로 쓰면
1, 110, 111, 100, 101, 11010, 11011, 11000, 11001, ...음수도 부호없이 나타낼 수 있다. -1 부터 차례대로 표시하면
11, 10, 1101, 1100, 1111, ...이들을 도와 10 진수를 입력으로 받아 -2 진법으로 출력하는 프로그램을 작성하는 것이 문제이다. 수의 범위는 -2,000,000,000..2,000,000,000 이다.
입력 -13 출력 110111
출처:USACO 2006 February Bronze