POJ 2657 - Comfort

http://poj.org/problem?id=2657

概要

N 個のフィールドが円形に並べられており，時計回りに 1 ... N と番号が振られている． そのうち M 個のフィールドには障害物が置かれている．

プレイヤーは 1 番目からスタートし，ゴールの Z 番目を目指す．このときプレイヤーは時計回りにちょうど K だけフィールドを飛び越えることでしか移動できない． また，障害物が置かれているフィールドには移動できない．

例えば N = 13, K = 3, Z = 9 で障害物が一つも無いとき，1, 4, 7, 10, 13, 3, 6, 9 と移動してゴールに辿り着く．

N, Z, M と M 個の障害物の位置が与えられたとき，ゴールに辿り着ける最小の K を答える．

制約

• 2 <= N <= 1000
• 2 <= Z <= N
• 0 <= M <= N-2

解法

すべての K に対してゴールできるかシミュレーションで判定するだけ．

 1 #include <iostream>
 2 #include <vector>
 3 #include <set>
 4 #include <iterator>
 5 using namespace std;
 6 
 7 bool ok(int N, int Z, int K, const set<int>& s)
 8 {
 9   vector<bool> visited(N, false);
10   for (int pos = 0; pos != Z; pos = (pos + K) % N) {
11     if (visited[pos] || s.find(pos) != s.end()) {
12       return false;
13     }
14     visited[pos] = true;
15   }
16   return true;
17 }
18 
19 int main(void)
20 {
21   int N, Z, M;
22   cin >> N >> Z >> M;
23   Z--;
24   set<int> s;
25   for (int i = 0; i < M; i++) {
26     int x;
27     cin >> x;
28     s.insert(x-1);
29   }
30   for (int K = 1; K < N; K++) {
31     if (ok(N, Z, K, s)) {
32       cout << K << endl;
33       break;
34     }
35   }
36   return 0;
37 }