読者です 読者をやめる 読者になる 読者になる

土下座しながら探索中

主に競技プログラミング

AOJ 1275 : And Then There Was One

問題リンク:And Then There Was One | Aizu Online Judge

問題概要:
n個の石で輪をつくる
m番目の石から始めてk個おきで石をとっていく
最後に残る石は何番めの石か?

使用した言語;C++

解法;
実際にvectorにつめて消していった
が、この問題はヨセフスの問題というらしく
f(n,k) = (f(n-1,k)+k)modn ただし f(1,k) = 0
という漸化式を使えば高速でとけるらしい
が、mから始めなければならないのでそのまま上の式を利用してもうまくいかないのでそこは考えないといけない


コード:

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

int main()
{
  int n,k,m;
  while(cin >> n >> k >> m, (n || k || m))
    {
      vector<int> stone;
      for(int i=1;i<=n;i++)
	stone.push_back(i);
 
      m--;
      for(;stone.size() > 1;)
	stone.erase(stone.begin()+m),m = (m+k-1)%stone.size();
      cout << stone[0] << endl;
    }    
  return 0;
}