AOJ1275 And Then There Was One

問題リンク And Then There Was One

• 概要

1〜Nの人が円形に並んでいる。番号Mを消し、残った人の中でK番目の人間を消すことを繰り返す。最後に残るのは何番の人か答えよ。
2 <= N <= 10000
1 <= K <= 10000
1 <= M <= N

• 解法

LinkedListを使えば、次に消す人物が(現在インデックス+K-1)%List.size()と即座に分かって便利です。

• ソース

import java.util.LinkedList;
import java.util.Scanner;

//And Then There Was One
public class AOJ1275 {

	void run(){
		Scanner sc = new Scanner(System.in);
		for(;;){
			int n = sc.nextInt(), k = sc.nextInt(), m = sc.nextInt();
			if((n|k|m)==0)break;
			LinkedList<Integer> l = new LinkedList<Integer>();
			for(int i=0;i<n;i++)l.add(i);
			int p = m-1;
			l.remove(p);
			while(l.size()>1){
				p = (p+k-1)%l.size();
				l.remove(p);
			}
			System.out.println(l.get(0)+1);
		}
	}
	
	public static void main(String[] args) {
		new AOJ1275().run();
	}
}