UVa440 Eeny Meeny Moo

UVa

問題文
http://uva.onlinejudge.org/external/4/440.html

問題概要
1からNまでの数列それぞれにランダムに対応させた地域のネットを遮断していく。方法は公平性を極めたいので、遮断の順序にランダム性を導入する。ランダム性は、数列を循環させた上ではじめから見てm番目を順に遮断していく方法とする。このとき一度遮断した地域の番号は取り除きながら考える。ただウルムは凄いプログラマーの出身地なので、遮断を最後に回したい。それが可能な最小のmを求めよ。

解法
ヨセフス問題と同じと考えると分かりやすい。ヨセフス問題は PCK や いつだかの ICPC アジア地区予選など様々な所で出ている。
ループでmを決め打ちする。nは150が上限なのでmの上限は適当に10000としている。
ヨセフス問題は、vectorを使うと楽かもしれない。vectorの最後と最初を連結させるのとm番目を削除するのができれば、vectorのサイズが1になるまでm番目の削除繰り返していけばよいとなる。

int Joseph(int n, int m) {
  vector<int> v;
  int cnt=0;
  for(int i=0; i<n; i++) v.push_back(i+1);
  for(vector<int>::iterator it = v.begin(); v.size()>1; cnt++) {
    if(it == v.end()) it = v.begin();
    if(cnt%m==0) it = v.erase( it );
    else it++;
  }
  return v[0];
}
 
int main() {
  int n;
  while(cin >> n && n) {
    int ans = 1<<29;
    for(int m=2; m<10000; m++) {
      if(Joseph(n, m) == 2) {
        cout << m << endl;
        break;
      }
    }
  }
   
  return 0;
}