PKU 2657-Comfort

問題概要

円形に並んだN個のマスを持つボードゲームがあり，各マスには1からNと反時計周りに番号が付けられている．
プレイヤーは最初1のマスに駒を置く．プレイヤーの目的は駒をZ番目のマスに移動させることである．
プレイヤーが出来る唯一の行動はkマス次に進むことでマスに障害物があった場合は失敗する．
N，Z，障害物のあるマスの情報が与えられたとき，プレイヤーが目的を達成出来る最小のkを求めよ．

解法

全てのkについて試す．O(N^3)だが間に合ってしまう．

実装(C++)

#include <iostream>
#include <cstring>
using namespace std;
int N,Z,M,k;
int ob[1000];
bool check(int K){
	int s=0;
	while(1){
		s=(s+K)%N;
		if(s==0)return false;
		if(s==Z)return true;
		if(ob[s])return false;
	}
}
int main() {
	for(;cin>>N>>Z>>M;){
		memset(ob,0,sizeof(ob));
		Z--;
		for(int i=0;i<M;i++){
			cin>>k;ob[k-1]=1;
		}
		for(int i=0;i<=N;i++){
			if(check(i)){
				cout<<i<<endl;
				break;
			}
		}
	}
	return 0;
}