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; }