CF132D Constants in the language of Shakespeare

Shakespeare 是一种广为人知的晦涩编程语言，其程序看起来像莎士比亚的戏剧，数字则由华丽的修饰语组合而成。在本题中，我们将深入研究 Shakespeare 中数字的描述方式。 在 Shakespeare 中，每个常数都是通过非负的 $2$ 的幂次方结合算术运算构成的。为简化问题，我们只允许使用加法和减法，并且需要找到一种表示给定数字的方法，使得所需的运算次数最少。 给定一个整数 $n$，你需要将其表示为 $n = a_1 + a_2 + \cdots + a_m$，其中每个 $a_i$ 都是非负的 $2$ 的幂次方，可以乘以 $-1$。请找出一种表示方式，使得 $m$ 的值最小。

输入仅一行，包含一个正整数 $n$，以其二进制表示给出。该表示的长度不超过 $10^6$，且首位保证为 $1$。

输出所需的最小 $m$。接下来输出 $m$ 行，每行格式为 "+2^x" 或 "-2^x"，其中 $x$ 是对应项的幂次。各行顺序不限。

由 ChatGPT 4.1 翻译