URAL 1495. One-two, One-two 2

Author: 2015-09-14

ACM

, ,

1. 题目

http://acm.timus.ru/problem.aspx?space=1&num=1495

1495. One-two, One-two 2

Time limit: 2.0 second
Memory limit: 64 MB
A year ago the famous gangster Vito Maretti woke up in the morning and realized that he was bored of robbing banks of round sums. And for the last year he has been taking from banks sums that have only digits 1 and 2 in their decimal notation. After each robbery, Vito divides the money between N members of his gang. Your task is to determine the minimal stolen sum which is a multiple of N.

Input

The input contains the number N (1 ≤ N ≤ 106).

Output

Output the minimal number which is a multiple of N and whose decimal notation contains only digits 1 and 2. If it contains more than 30 digits or if there are no such numbers, then output “Impossible”.

Samples

input output 
5

Impossible

8

112
Problem Author: Igor Chevdar
Problem Source: XIII-th USU Junior Contest, October 2006

2. 思路

给出一个数字N，求N的一个最小的整数倍，该整数倍只由数字1和数字2组成，30位数字内找不到则输出Impossible。

以位数为单位，按照余数对所求整数倍进行BFS，30位以内找到余数为0的数字即为答案，否则输出Impossible。

此题也有动态规划的解法。

3. 代码

对Digit 进行BFS，Digit包括数字digit ，当前余数mod 和前一个数字在队列中的位置pre 。在队列中使用标志ADD_DIGIT_FLAG 对位数进行计数。首先将1和2入队，将ADD_DIGIT_FLAG 入队。然后依次出队各个元素：如果遇到ADD_DIGIT_FLAG ，则将位数计数digitCnt 加1；否则分别追加数字1和数字2，并分别计算新的余数。直到找到余数为0的数字，回溯得到完整的答案；30位内找不到则输出Impossible。使用calculated[mod] 来标记余数mod是否已经出现过，如已出现过则不必重复计算。

#include <cstdio>

const int MAX_DIGITS_NUM = 30;
const int MAX_TRIAL_NUM = 1000001;
const int ADD_DIGIT_FLAG = -1;

struct Digit {
    int digit, mod, pre;
};

void solveE6g_OneTwoOneTwo2();
void setDigit(Digit &d, int digit, int mod, int pre);

int main() {
    solveE6g_OneTwoOneTwo2();
}

Digit queue[MAX_TRIAL_NUM];
bool calculated[MAX_TRIAL_NUM];
void solveE6g_OneTwoOneTwo2() {
    int n;
    scanf("%d", &n);
    
    int front = 0, rear = 0;
    setDigit(queue[front++], 1, 1 % n, -1);
    calculated[1 % n] = true;
    
    setDigit(queue[front++], 2, 2 % n, -1);
    calculated[2 % n] = true;
    
    setDigit(queue[front++], ADD_DIGIT_FLAG, -1, -1);
    
    bool found = false;
    int digitCnt = 1, lastDigitIdx;
    while (rear < front) {
        Digit curr = queue[rear++];
        if (curr.digit == ADD_DIGIT_FLAG) {
            if (front == rear) {
                break;
            }
            else {
                setDigit(queue[front++], ADD_DIGIT_FLAG, -1, -1);
                if (++digitCnt > MAX_DIGITS_NUM) {
                    break;
                }
                else {
                    continue;
                }
            }
        } else if (curr.mod == 0) {
            found = true;
            lastDigitIdx = rear - 1;
            break;
        }
        
        int newMod = (curr.mod * 10 + 1) % n;
        if (!calculated[newMod]) {
            setDigit(queue[front++], 1, newMod, rear - 1);
            calculated[newMod] = true;
        }
        
        newMod = (curr.mod * 10 + 2) % n;
        if (!calculated[newMod]) {
            setDigit(queue[front++], 2, newMod, rear - 1);
            calculated[newMod] = true;
        }
    }
    
    if (found) {
        int result[MAX_DIGITS_NUM + 1], cnt = 0;
        for (int i = lastDigitIdx; i != -1; i = queue[i].pre, ++cnt) {
            result[cnt] = queue[i].digit;
        }
        for (int i = cnt - 1; i >= 0; --i) {
            printf("%d", result[i]);
        }
        printf("\n");
    }
    else {
        printf("Impossible\n");
    }
    
}

void setDigit(Digit &d, int digit, int mod, int pre) {
    d.digit = digit;
    d.mod = mod;
    d.pre = pre;
}