codeforces/PolyCarpAndDividend/main.cpp


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

#include <bits/stdc++.h>

using namespace std;

const int N = 1234567;

int a[12], p[N], e[N];
bool vis[N];

void print(int x) {
  if (x == -1) return;
  print(p[x]);
  printf("%d", e[x]);
}

int main() {
  int n, m;
  scanf("%d", &n);
  for (int i = 0; i < n; i++) {
    scanf("%d", a + i);
  }
  sort(a, a + n);
  scanf("%d", &m);
  int cnt = 0;
  queue < pair <int, int> > q;
  q.push(make_pair(-1, 0));
  while (!q.empty()) {
    int u = q.front().first;
    int x = q.front().second;
    q.pop();
    for (int i = 0; i < n; i++) {
      int v = (x * 10 + a[i]) % m;
      if (u == -1 && a[i] == 0) continue;
      if (!vis[v]) {
        vis[v] = true;
        q.push(make_pair(cnt, v));
        e[cnt] = a[i];
        p[cnt++] = u;
      }
      if (v == 0) {
        print(cnt - 1);
        return 0;
      }
    }
  }
  puts("-1");
  return 0;
}