Problem D
Power Signs
“Increase my killing power, eh?”– Homer Simpson
You are probably familiar with the binary representation of integers, i.e. writing a nonnegative integer $n$ as $\sum _{i=0}^ k a_ i \cdot 2^ i$, where each $a_ i$ is either $0$ or $1$. In this problem, we consider a so called signed binary representation, in which we still write $n$ as $\sum _{i=0}^{k} a_ i \cdot 2^ i$, but allow $a_ i$ to take on the values $-1$, $0$ and $1$. For instance, $n=13$ can be represented as
\[ (1, 0, 0, -1, -1) = 2^4 - 2^1 - 2^0. \]The binary representation of a number is unique, but obviously, the signed binary representation is not. In certain applications (e.g. in cryptography), one seeks to write a number $n$ in signed binary representation with as few non-zero digits as possible. For example, we consider the representation $(1, 0, 0, -1)$ to be a better representation of $n = 7$ than $(1, 1, 1)$. Your task is to write a program which will find such a minimal representation.
Input
The input consists of a single line containing a positive integer $n < 2^{100\, 000}$ written in binary, without leading zeros.
Output
For each line of input, output one line containing the signed binary representation of $n$ that has the minimal number of non-zero digits, using the characters ‘-’ for $-1$, ‘0’ for $0$ and ‘+’ for $+1$. The number should be written without leading zeros. If there are several minimal representations, output the one that is lexicographically smallest (by the ASCII ordering, in which $‘\texttt{+}‘ < ‘\texttt{-}‘ < ‘\texttt{0}‘$).
| Sample Input 1 | Sample Output 1 |
|---|---|
10000 |
+0000 |
| Sample Input 2 | Sample Output 2 |
|---|---|
1111 |
+000- |
| Sample Input 3 | Sample Output 3 |
|---|---|
10111 |
++00- |
