日々精進

aikoと旅行とプログラミング

【AOJ 1257】And Then There Was One

問題

And Then There Was One | Aizu Online Judge

方針

  • Josephus problemという有名な問題らしい.
  •  {f(n, k) = (f(n-1, k)+k) \bmod n } (ただし,  {f(1, k) = 0 }) という漸化式を解くことで {O(n)}で求まる.

コード

#include <iostream>

using namespace std;

int f(int n, int k){
  if(n == 1) return 0;
  return (f(n-1, k)+k)%n;
}
signed main(){
  int n, k, m;
  while(cin >> n >> k >> m, n || k || m){
    cout << (f(n-1,k)+m)%n+1 << endl;
  }
}