Joseph.java

package DynamicProgramming;


import java.io.*;
import java.util.*;

public class Joseph {
	static boolean solve(int N, int M) {
		int K = N / 2;
		int p = -1;
		List<Integer> arr = new ArrayList<Integer>();
		for (int i = 0; i < N; ++i){
			arr.add(i + 1);
		}
		for (int r = 0; r < K; ++r) {
			p = (p + M) % arr.size();
			arr.remove(p);
			p--;
			if (p < 0){
				p = arr.size() - 1;	
			}
		}
		for (int i = 0; i < arr.size(); ++i){
			if (arr.get(i) != i + 1){
				return false;
			}
		}
		return true;	
	}
	
	public static void main(String[] args) throws IOException {
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		
		int[] ans = new int[14];
		for (int k = 1; k < 14; ++k){
			for (int M = 1; ; ++M){
				if (solve(2 * k, M)){
					ans[k] = M;
					break;
				}
			}
		}
		
		while (true) {
			int K = Integer.parseInt(in.readLine());
			if (K == 0) break;		
			System.out.println(ans[K]);
		}	
		in.close();
	}
}