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

view plainprint?

1. package p1012;  
2.   
3. import java.util.*;  
4. import java.lang.*;  
5. import java.math.*;  
6. import java.io.*;  
7.   
8. import static java.lang.Math.*;  
9. import static java.util.Arrays.*;  
10.   
11. public class Main{  
12.   
13.  Scanner sc;  
14.   
15.  final int INF=Integer.MAX_VALUE;  
16.  final double EPS=1e-9;  
17.   
18.  void run(){  
19.   sc=new Scanner(System.in);  
20.   int[] ans={0, 2, 7, 5, 30, 169, 441, 1872, 7632, 1740, 93313, 459901,  
21.     1358657, 2504881};  
22.   for(;;){  
23.    int k=sc.nextInt();  
24.    if(k==0)  
25.     break;  
26.    println(""+ans[k]);  
27.   }  
28.  }  
29.   
30.  void debug(){  
31.   for(int k=1; k<14; k++)  
32.    println("k="+k+", m="+m(k));  
33.  }  
34.   
35.  int m(int k){  
36.   int n=k*2;  
37.   LinkedList<Integer> a=new LinkedList<Integer>();  
38.   for(int m=1;; m++){  
39.    a.clear();  
40.    for(int i=0; i<n; i++)  
41.     a.add(i);  
42.    int p=0;  
43.    boolean f=true;  
44.    for(int j=0; j<k; j++){  
45.     p=(p-1+m)%a.size();  
46.     if(a.remove(p)<k){  
47.      f=false;  
48.      break;  
49.     }  
50.    }  
51.    if(f)  
52.     return m;  
53.   }  
54.  }  
55.   
56.  void print(String s){  
57.   System.out.print(s);  
58.  }  
59.   
60.  void println(String s){  
61.   System.out.println(s);  
62.  }  
63.   
64.  public static void main(String[] args){  
65.   // System.setOut(new PrintStream(new BufferedOutputStream(System.out)));  
66.   new Main().run();  
67.  }  
68. }  

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();
 }
}