2013-08-11 22:34:01| 人氣1,575| 回應0 | 上一篇 | 下一篇

[UVA][greedy] 11166 - Power Signs

推薦 0 收藏 0 轉貼0 訂閱站台

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 ∑a_i2ⁱ, 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 ∑a_i2ⁱ, but allow a_i to take on the values -1, 0 and 1. We write a signed binary representation of a number as a vector (a_k, a_k_-1, ..., a₁, a₀). For instance, n = 13 can be represented as (1, 0, 0, -1, -1) = 2⁴ - 2¹ - 2⁰.

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 ≤ 2⁵⁰⁰⁰⁰ 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

+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;
}

我要檢舉

#11166#Power Signs#greedy

台長： Morris