AOJ 1275 And Then There Was One

And Then There Was One | Aizu Online Judge

ヨセフスの問題とか、ヨセフスの芋とか言われるやつ。

n人いて、m番目の人からはじめてk間隔で処刑していくヨセフスの問題という設定。

シミュレーションだと間に合わないので、「ヨセフスの問題」とかでググると、

f(n,k) = (f(n-1,k) + k) Mod n (ただし、f(1,k) = 0)という漸化式が見つかる。

それをそのまま関数に書き出すと、O(n)で残る人が判定できる。

ただし、この関数は0-indexed(0~n-1番目)の形で返ってくるのと、m人目からはじまるので上手く工夫してやる。

サンプルが合わない人へ: m番目の人はまず初めに処刑されます。(重要)

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

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