[UVA][greedy] 11166 - Power Signs
Problem B
Power Signs
Input: Standard Input
Output: Standard Output
"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 ∑ai2i,
where each ai is either 0 or 1.
In this problem, we consider a so called signed binary representation,
in which we still write n as ∑ai2i,
but allow ai to take on the
values -1, 0 and 1. We write a signed binary representation of a number as a
vector (ak, ak-1, ..., a1, a0). For
instance, n = 13 can be represented as (1, 0, 0, -1, -1) = 24
- 21 - 20.
The binary representation of a number is unique, but obviously, the signed binary representation is not. In certain applications (e.g. 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 several test cases (at most 25), one per line. Each test case consists of a positive integer n ≤ 250000 written in binary without leading zeros. The input is terminated by a case where n = 0, which should not be processed.
Output
For each line of input, output one line containing the signed binary representation of n that has the minimum 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 possible answers, output the one that is lexicographically smallest (by the ASCII ordering).
Sample Input Output for Sample Input
10000111110111
0
|
+0000+000-++00-
|
Problem setter: Per Aurtrin
Special Thanks: Mikael Goldmann
要最少化非 0 標記，如果有相同個數時，則輸出字典順序最小。
'+' < '0'
greedy 的思路為, 011...110 則最後一個 1 換成 -, 前方的 0 換成 +
=> +00...0-0
可是對於 11 可以表示成 ++ 或者是 +0-，然而要最小化且字典順序最小，因此 ++ 會比較好。
而 0+0 不用改成 +-0，沒有達到最小化。
對於 11 這種要特別考慮，如果前方還有非 0 的話，則考慮 +0-，反之 ++ 即可。
#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
char s[50005];
int val[65536];
int main() {
int i, j;
while(scanf("%s", s) == 1) {
if(!strcmp(s, "0"))
break;
int n = strlen(s);
memset(val, 0, sizeof(val));
for(i = 0, j = n-1; i < n; i++, j--)
val[i] = s[j]-'0';
for(i = 0; i < n; i++) {
if(val[i] == 1) {
j = i;
while(val[j]) {
if(val[j] == 1)
j++;
else
break;
}
if(i+2 < j || (i+2 == j) && j < n) {
val[i] = -1;
val[j]++;
i++;
while(i < j)
val[i] = 0, i++;
i--;
}
while(val[n]) n++;
}
}
i = n+10;
while(i > 0 && val[i] == 0) i--;
for(; i >= 0; i--) {
if(val[i] == 1)
putchar('+');
else if(val[i] == 0)
putchar('0');
else
putchar('-');
}
puts("");
}
return 0;
}