PKU Judge Online 1012 Joseph

■1012 Joseph

□Problem
Josephの問題がある．これは，1~nまで数字付けされたn人が円状に並び，1の人からm人毎に省いていき，最後に残った人が生き残る，というものである．今回は，0<k<14となるkが与えられ，2k人が並ぶ．前半k人よりも先に後半k人が先に省かれるような最小のmを求めよ．

□Solution
kの範囲が狭いので，先に答えを求めておく．mの計算方法はコードのm(int k)を見て下さい．

□Code

package p1012;

import java.util.*;
import java.lang.*;
import java.math.*;
import java.io.*;

import static java.lang.Math.*;
import static java.util.Arrays.*;

public class Main{

 Scanner sc;

 final int INF=Integer.MAX_VALUE;
 final double EPS=1e-9;

 void run(){
  sc=new Scanner(System.in);
  int[] ans={0, 2, 7, 5, 30, 169, 441, 1872, 7632, 1740, 93313, 459901,
    1358657, 2504881};
  for(;;){
   int k=sc.nextInt();
   if(k==0)
    break;
   println(""+ans[k]);
  }
 }

 void debug(){
  for(int k=1; k<14; k++)
   println("k="+k+", m="+m(k));
 }

 int m(int k){
  int n=k*2;
  LinkedList<Integer> a=new LinkedList<Integer>();
  for(int m=1;; m++){
   a.clear();
   for(int i=0; i<n; i++)
    a.add(i);
   int p=0;
   boolean f=true;
   for(int j=0; j<k; j++){
    p=(p-1+m)%a.size();
    if(a.remove(p)<k){
     f=false;
     break;
    }
   }
   if(f)
    return m;
  }
 }

 void print(String s){
  System.out.print(s);
 }

 void println(String s){
  System.out.println(s);
 }

 public static void main(String[] args){
  // System.setOut(new PrintStream(new BufferedOutputStream(System.out)));
  new Main().run();
 }
}