2068 Nim

「2068 Nim」の編集履歴（バックアップ）一覧はこちら

「2068 Nim」(2006/04/17 (月) 02:12:57) の最新版変更点

追加された行は緑色になります。

削除された行は赤色になります。

**2068 Nim
**問題
http://acm.pku.edu.cn/JudgeOnline/problem?id=2068
**解答方針
動的計画法．table[i][j]には残り i+1 個で j+1 人目のターンならば，j+1人目のプレイヤーは勝利できるか否かを格納する．
**解答例
 import java.util.*;
 
 public class Main {
     public static void main(String[] args) {
         Scanner sc = new Scanner(System.in);
         while(true){
             int n = sc.nextInt();
             if(n==0) break;
             int s = sc.nextInt();
             int[] max = new int[2*n];
             for(int j=0;j<2*n;j++){
                 max[j] = sc.nextInt();
             }
             
             boolean[][] table = new boolean[s][2*n];
             for(int j=0;j<2*n;j++) table[0][j] = false;
             for(int i=0;i<s;i++){
                 for(int j=0;j<2*n;j++){
                     boolean win = false;
                     for(int k=Math.max(i-max[j],0);k<i;k++){
                         int nextj = (j+1)%(2*n);
                         if(table[k][nextj]==false){
                             win = true;
                             break;
                         }
                     }
                     table[i][j] = win;
                 }
             }
             
             if(table[s-1][0]) System.out.println("1");
             else System.out.println("0");
         }
     }
 }