Friday, September 10, 2010

ACM: 130 – Roman Roulette

simulation,但規則有點看不懂,看了中譯才搞清楚...

CODE

#include <iostream>
#include <vector>
using namespace std;

int n, k;
int kill(int i, vector<int> v);

int main(){
  int i, t;
  vector<int> r;
  
  while( (cin >> n >> k) && (n != 0) ){
    r.clear();
    for(i=1; i<=n; ++i)
      r.push_back(i);
    
    t = kill(0, r) - 1;
    t = (n - t) % n;
    cout << t + 1 << endl;
  }//while
  return 0;
}

int kill(int i, vector<int> v){
  int p;
  --i;
  while( v.size() > 1 ){
    i = p = (i+k) % v.size(); //p: killed
    v.erase(v.begin()+i);
    i = (i+k-1) % v.size(); //i: burier
    v.insert(v.begin()+p, v[i]);
    if( i >= p )
      ++i;
    v.erase(v.begin()+i);
    if( i >= p )
      i = p % v.size();
    else
      i = (p - 1) % v.size();
  }
  return v[0];
}

No comments:

Post a Comment