解いた問題

2/29/2012

SRM524 Div2 Hard

1000
少し前に解いた問題と似た雰囲気があるからどうにかなった。
[最後に使った数字][これまでの余り]を状態にしたBFSで計算できる。筆算を思い浮かべる。
こういう問題は面白いと感じる。
  1. class MultiplesWithLimit {  
  2. public:  
  3.   string minMultiples(int N, vector <int> D)   
  4.   {  
  5.     sort(D.begin(), D.end());  
  6.       
  7.     const int MOD = 10000;  
  8.     const int LAST = 10;  
  9.   
  10.     bool vis[LAST][MOD];  
  11.     fill(&vis[0][0], &vis[LAST - 1][MOD], false);  
  12.   
  13.     int len[LAST][MOD];  
  14.     fill(&len[0][0], &len[LAST - 1][MOD], 0);  
  15.   
  16.     pair<intint> path[LAST][MOD];      
  17.   
  18.     queue< pair<intint> > q;  
  19.     for (int n = 1; n < 10; ++n) {  
  20.       if (binary_search(D.begin(), D.end(), n)) continue;  
  21.       q.push(make_pair(n, n % N));  
  22.       vis[n][n % N] = true;  
  23.     }  
  24.   
  25.     pair<intint> p = make_pair(-1, -1);  
  26.     for (; q.size(); q.pop()) {  
  27.       p = q.front();  
  28.       if (vis[p.first][p.second] && p.second == 0) break;  
  29.       for (int n = 0; n < 10; ++n) {  
  30.         if (binary_search(D.begin(), D.end(), n)) continue;  
  31.         int m = (p.second * 10 + n) % N;  
  32.         if (vis[n][m]) continue;  
  33.         vis[n][m] = true;  
  34.         path[n][m] = p;  
  35.         q.push(make_pair(n, m));  
  36.       }  
  37.     }          
  38.   
  39.     if (p.second) return "IMPOSSIBLE";  
  40.   
  41.     string s;  
  42.     while (true) {  
  43.       if (s.size() && p.second == 0) break;  
  44.       s += '0' + p.first;  
  45.       p = path[p.first][p.second];  
  46.     }  
  47.     reverse(s.begin(), s.end());  
  48.       
  49.     if (9 <= s.size()) {  
  50.       char buff[100];  
  51.       int size = s.size();  
  52.       sprintf(buff, "%c%c%c...%c%c%c(%d digits)",   
  53.               s[0], s[1], s[2], s[size-3], s[size-2], s[size-1], size);  
  54.       s = string(buff);  
  55.     }  
  56.   
  57.     return s;  
  58.   }  
  59.   
  60. };  

0 件のコメント :

コメントを投稿