結果
問題 | No.153 石の山 |
ユーザー |
![]() |
提出日時 | 2015-09-11 17:22:25 |
言語 | Java (openjdk 23) |
結果 |
AC
|
実行時間 | 123 ms / 5,000 ms |
コード長 | 1,132 bytes |
コンパイル時間 | 2,274 ms |
コンパイル使用メモリ | 79,056 KB |
実行使用メモリ | 41,644 KB |
最終ジャッジ日時 | 2024-10-14 14:39:44 |
合計ジャッジ時間 | 6,750 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 27 |
ソースコード
import java.util.Arrays;import java.util.HashSet;import java.util.LinkedList;import java.util.Scanner;import java.util.Set;import java.util.TreeSet;public class Main {public static int grundy(int n, int[] memo){if(memo[n] >= 0){ return memo[n]; }if(n == 1){ return memo[n] = 0; }TreeSet<Integer> set = new TreeSet<Integer>();if(n >= 2){set.add(grundy(n / 2, memo) ^ grundy(n / 2 + (n % 2), memo));}if(n >= 3){if(n % 3 == 0){set.add(grundy(n / 3, memo) ^ grundy(n / 3, memo) ^ grundy(n / 3, memo));}else if(n % 3 == 1){set.add(grundy(n / 3, memo) ^ grundy(n / 3, memo) ^ grundy(n / 3 + 1, memo));}else{set.add(grundy(n / 3, memo) ^ grundy(n / 3 + 1, memo) ^ grundy(n / 3 + 1, memo));}}for(int i = 0; ; i++){if(!set.contains(i)){return memo[n] = i;}}}public static void main(String[] args) {Scanner sc = new Scanner(System.in);final int N = sc.nextInt();int[] memo = new int[N + 1];Arrays.fill(memo, -1);System.out.println(grundy(N, memo) == 0 ? "B" : "A");//System.out.println(Arrays.toString(memo));}}