1018.cpp

哈尔滨工业大学ACM 竞赛网上在线试题集锦的源代码

/*  This Code is Submitted by wywcgs for Problem 1018 on 2005-12-26 at 15:54:05 */ 
#include <cstdio>
#include <queue>
#include <algorithm>
using namespace std;

const int MAX = 5120;
const int N_MAX = 16;
typedef pair<int, int> pii;

int main()
{
	bool pos[MAX];
	int n, m, u[N_MAX], i, j;
	int r[MAX];
	pii prev[MAX];
	queue<int> queue;

	while(scanf("%d", &n) != EOF) {
		scanf("%d", &m);
		for(i = 0; i < m; i++) scanf("%d", &u[i]);
		memset(pos, false, sizeof(pos));
		for(i = 0; i < m; i++) prev[u[i]] = pii(-1, u[i]);
		sort(u, u+m);
		bool find = false;
		if(n != 0) {
			while(!queue.empty()) queue.pop();
			for(i = 0; i < m; i++) {
				if(u[i] == 0) continue;
				else if(u[i]%n == 0) {
					printf("%d\n", u[i]);
					find = true; break;
				} else {
					queue.push(u[i]%n);
					pos[u[i]%n] = true;
				}
			}
			while(!find && !queue.empty()) {
				int t = queue.front(); queue.pop();
				for(i = 0; i < m; i++) {
					int mod = (t*10+u[i]) % n;
					if(mod == 0) {
						int top = 0; r[top++] = u[i];
						for(j = t; j != -1; j = prev[j].first) r[top++] = prev[j].second;
						while(top > 0) putchar(r[--top]+'0');
						putchar('\n');
						find = true; break;
					} else if(!pos[mod]) {
						pos[mod] = true;
						prev[mod] = pii(t, u[i]);
						queue.push(mod);
					}
				}
			}
		}
		if(!find) printf("0\n");
	}
	
	
	return 0;
}