少し前に解いた問題と似た雰囲気があるからどうにかなった。
[最後に使った数字][これまでの余り]を状態にしたBFSで計算できる。筆算を思い浮かべる。
こういう問題は面白いと感じる。
- class MultiplesWithLimit {
- public:
- string minMultiples(int N, vector <int> D)
- {
- sort(D.begin(), D.end());
- const int MOD = 10000;
- const int LAST = 10;
- bool vis[LAST][MOD];
- fill(&vis[0][0], &vis[LAST - 1][MOD], false);
- int len[LAST][MOD];
- fill(&len[0][0], &len[LAST - 1][MOD], 0);
- pair<int, int> path[LAST][MOD];
- queue< pair<int, int> > q;
- for (int n = 1; n < 10; ++n) {
- if (binary_search(D.begin(), D.end(), n)) continue;
- q.push(make_pair(n, n % N));
- vis[n][n % N] = true;
- }
- pair<int, int> p = make_pair(-1, -1);
- for (; q.size(); q.pop()) {
- p = q.front();
- if (vis[p.first][p.second] && p.second == 0) break;
- for (int n = 0; n < 10; ++n) {
- if (binary_search(D.begin(), D.end(), n)) continue;
- int m = (p.second * 10 + n) % N;
- if (vis[n][m]) continue;
- vis[n][m] = true;
- path[n][m] = p;
- q.push(make_pair(n, m));
- }
- }
- if (p.second) return "IMPOSSIBLE";
- string s;
- while (true) {
- if (s.size() && p.second == 0) break;
- s += '0' + p.first;
- p = path[p.first][p.second];
- }
- reverse(s.begin(), s.end());
- if (9 <= s.size()) {
- char buff[100];
- int size = s.size();
- sprintf(buff, "%c%c%c...%c%c%c(%d digits)",
- s[0], s[1], s[2], s[size-3], s[size-2], s[size-1], size);
- s = string(buff);
- }
- return s;
- }
- };
0 件のコメント :
コメントを投稿