← 返回题目列表

Codeforces · 132/D

D. 莎士比亚语言中的常数

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

莎士比亚是一种广为人知的深奥编程语言,其中的程序看起来像莎士比亚的戏剧,并且数字由华丽的绰号组合给出。在本题中,我们将仔细研究莎士比亚中描述数字的方式。

莎士比亚中的每个常数都是使用算术运算从 2 的非负幂创建的。为简单起见,我们只允许加法和减法,并将寻找需要最少运算次数的给定数字的表示形式。

给定一个整数 n。您必须将其表示为 n = a1 + a2 + ... + am,其中每个 ai 都是 2 的非负幂,可能乘以 -1。找到最小化 m 值的表示。

输入

输入的唯一一行包含一个正整数 n,以二进制表示法表示。符号的长度最多为106。符号的第一位数字保证为1。

输出

输出所需的最小m。之后输出m行。每行的格式必须为“+2^x”或“-2^x”,其中 x 是相应项的幂系数。行的顺序并不重要。

示例

输入 #1

1111

输出 #1

2
+2^4
-2^0

输入 #2

1010011

输出 #2

4
+2^0
+2^1
+2^4
+2^6