

Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 300 点
問題文
整数 N が与えられるので、N の -2 進数表現を求めてください。
ここで、S が N の -2 進数表現であるとは、以下を全て満たすことです。
- S は
0
および1
のみからなる文字列である - S =
0
でなければ S の先頭の文字は1
である - S = S_k S_{k-1} ... S_0 とすると、S_0 \times (-2)^0 + S_1 \times (-2)^1 + ... + S_k \times (-2)^k = N が成り立つ
なお、任意の整数 M に対して M の -2 進数表現が一意に定まることが証明できます。
制約
- 入力はすべて整数である
- -10^9 \leq N \leq 10^9
入力
入力は以下の形式で標準入力から与えられる。
N
出力
N の -2 進数表現を出力せよ。
入力例 1
-9
出力例 1
1011
(-2)^0 + (-2)^1 + (-2)^3 = 1 + (-2) + (-8) = -9 なので 1011
は -9 の -2 進数表現です。
入力例 2
123456789
出力例 2
11000101011001101110100010101
入力例 3
0
出力例 3
0
Score : 300 points
Problem Statement
Given an integer N, find the base -2 representation of N.
Here, S is the base -2 representation of N when the following are all satisfied:
- S is a string consisting of
0
and1
. - Unless S =
0
, the initial character of S is1
. - Let S = S_k S_{k-1} ... S_0, then S_0 \times (-2)^0 + S_1 \times (-2)^1 + ... + S_k \times (-2)^k = N.
It can be proved that, for any integer M, the base -2 representation of M is uniquely determined.
Constraints
- Every value in input is integer.
- -10^9 \leq N \leq 10^9
Input
Input is given from Standard Input in the following format:
N
Output
Print the base -2 representation of N.
Sample Input 1
-9
Sample Output 1
1011
As (-2)^0 + (-2)^1 + (-2)^3 = 1 + (-2) + (-8) = -9, 1011
is the base -2 representation of -9.
Sample Input 2
123456789
Sample Output 2
11000101011001101110100010101
Sample Input 3
0
Sample Output 3
0