SPOJ/onezero.cpp at master · vfonic/SPOJ · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
#include <algorithm>
#include <cctype>
#include <climits>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <list>
#include <map>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <vector>

#define inf 1000000000
#define MAXN 20000

using namespace std;

int main() {
    int t;
    scanf("%d", &t);

    int n;
    int been[MAXN];
    int which[MAXN];
    for (int qwertz = 0; qwertz < t; ++qwertz) {
        scanf("%d", &n);

        if (n == 1) {
            printf("1\n");
            continue;
        }

        memset(been, -1, sizeof been);
        been[1] = 0;
        queue<int> kju;
        for (kju.push(1); !kju.empty(); kju.pop()) {
            int num = kju.front();

            if (!num) {
                stack<int> stog;
                while (been[num]) {
                    stog.push(which[num]);
                    num = been[num];
                }

                printf("1");
                while (!stog.empty()) {
                    printf("%d", stog.top());
                    stog.pop();
                }
                printf("\n");
                break;
            }

            for (int i = 0; i < 2; ++i) {
                int next = (num*10+i)%n;
                if (been[next] == -1) {
                    been[next] = num;
                    which[next] = i;
                    kju.push(next);
                }
            }
        }
    }

    return 0;
}