← 返回题目列表

AtCoder · abc105_c

C. 基数 -2 号

中文机器翻译题面 查看原题

分数: 300 点

问题陈述

给定一个整数 N,找到基地 -2 的表示 N.

在这里, S 是基础 -2 的表示 N 当以下全部满足时:

  • S 是一个由以下组成的字符串 0 和 1.
  • 除非 S = 0,首字符 S is 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,底座 -2 的表示 M 是唯一确定的。

约束

  • 输入中的每个值都是整数。
  • -10^9 \leq N \leq 10^9

输入

输入由标准输入按以下格式给出:

N

输出

打印底座 -2 的表示 N.


示例输入 1

-9

示例输出 1

1011

As (-2)^0 + (-2)^1 + (-2)^3 = 1 + (-2) + (-8) = -9, 1011 是基础 -2 的表示 -9.


示例输入 2

123456789

示例输出 2

11000101011001101110100010101

示例输入 3

0

示例输出 3

0