【搜索、bfs】Find The Multiple

Problem

Given a positive integer n, write a program to find out a nonzero multiple m of n whose decimal representation contains only the digits 0 and 1. You may assume that n is not greater than 200 and there is a corresponding m containing no more than 100 decimal digits.

给定一个正整数n，编写一个程序找出一个N 的非零倍数M，其十进制表示仅包含数字0和1。您可以假设N 不大于200，并且对应的M 包含不超过100位小数。

Input

The input file may contain multiple test cases. Each line contains a value of n (1 <= n <= 200). A line containing a zero terminates the input.

输入文件可能包含多个测试用例。每一行包含一个值n (1 <= n <= 200)。包含0的行终止输入。

Output

For each value of n in the input print a line containing the corresponding value of m. The decimal representation of m must not contain more than 100 digits. If there are multiple solutions for a given value of n, any one of them is acceptable.

对于输入中的每个n值，打印一行包含m的对应值。m的十进制表示形式不能包含超过100位的数字。如果给定的n有多个解，其中任何一个都是可接受的。

Sample Input

Sample Output

10

100100100100100100

111111111111111111

一道搜索题。虽然题目说M 的长度不会超过100（啊，第一眼看到可吓死我了）， 不过实际上答案最小的长度并不会超过unsigned long long，也不知道long long 行不行，反正开最大就对了。
因为是只由0和1构成的数，所以答案由最小等于1 起，只需要考虑 *10和（*10）+1即可，那么就只需要以1 为起点bfs 就好了。
下面是代码。

#include<iostream>

#include<cstdio>

#include<queue>

using namespace std;

typedef  unsigned long long  Long;

queue<Long> q;

int main()

{

    int n;

    Long a;

    while (cin >>n&& n)

    {

        while(! q.empty()) q.pop();

        q.push();

        while (! q.empty())

        {

            a= q.front();

            q.pop();

            if (a% n== ) break;

            Long b= a* ;

            q.push(b);

            b+= ;

            q.push(b);

        }

        cout << a << endl;

    }

    return ;

}

end；

巴特西

【搜索、bfs】Find The Multiple

最新文章

热门文章