Base -2 Number

题目描述

给定一个整数 $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$ 表示是唯一确定的。

输入格式

标准输入的格式如下： $N$

输出格式

输出 $N$ 的基 $-2$ 表示。

-9

1011

123456789

11000101011001101110100010101

0

0

提示

输入中的每个值都是整数。 $-10^9 \leq N \leq 10^9$由于 $(-2)^0 + (-2)^1 + (-2)^3 = 1 + (-2) + (-8) = -9$，$1011$ 是 $-9$ 的基 $-2$ 表示。

标签: AtCoder|abc105C

来源

AtCoder|abc105C