結果
問題 |
No.7 プライムナンバーゲーム
|
ユーザー |
|
提出日時 | 2020-05-26 21:40:44 |
言語 | Java (openjdk 23) |
結果 |
AC
|
実行時間 | 221 ms / 5,000 ms |
コード長 | 3,567 bytes |
コンパイル時間 | 2,977 ms |
コンパイル使用メモリ | 79,152 KB |
実行使用メモリ | 46,436 KB |
最終ジャッジ日時 | 2024-10-01 16:34:22 |
合計ジャッジ時間 | 6,517 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 17 |
ソースコード
package yukicoder.level2.no7; import java.util.Collection; import java.util.HashSet; import java.util.Scanner; import java.util.Set; /** * No.7 プライムナンバーゲーム . * https://yukicoder.me/problems/25 <br> * あなたと素数を習ったばかりのEveは、素数のゲームを思いついた。<br> * * ゲームの内容は以下のとおりです。<br> * ・まず初めに、先攻のプレイヤーに2以上の自然数Nが与えられます。<br> * ・その番のプレイヤーはNに対して、「N以下(Nも含む)の素数」のどれかで減算する、<br> * その数をN′とすると、N′が0または1になってしまったら、そのプレイヤーの負けである。<br> * ・その後N′を新たなNとし、相手にその数を渡し、以上を繰り返します。<br> * * <br> * まずあなたが先攻となりゲームを始めます。<br> * この時、どちらも負けないように動くと考える。<br> * 自然数Nが与えられた時、あなたが勝つことが出来る場合Win、それ以外はLoseを返してください。<br> */ public class PrimeNumberGame { private static final String WIN_DISPLAY = "Win"; private static final String LOSE_DISPLATY = "Lose"; private static final int MIN_PRIME_NUMBER = 2; public static void main(String[] args) { new PrimeNumberGame().execute(); } private void execute() { int startingNumber = read(); boolean canWin = judgeWinnableNumber(startingNumber); output(canWin); } //数字を順番にカウントアップする //その数字が勝てるかどうかを判定する //今まで出てきた素数で引いた数が勝てる場合は、相手が勝ってしまうので負け //今まで出てきた素数で引いた数が勝てない場合は、相手が負けるので勝ち //これを与えられた数字になるまで繰り返す /** * * @param startingNumber * @return */ public boolean judgeWinnableNumber(int startingNumber) { Set<Integer> winnableNumbers = new HashSet<>(); Set<Integer> primeNumbers = new HashSet<>(); for (int preprocessingNumber = MIN_PRIME_NUMBER; preprocessingNumber < startingNumber; preprocessingNumber++) { if(isPrime(preprocessingNumber, primeNumbers)) { primeNumbers.add(preprocessingNumber); } if(isWannable(winnableNumbers, primeNumbers, preprocessingNumber)) { winnableNumbers.add(preprocessingNumber); } } return isWannable(winnableNumbers, primeNumbers, startingNumber); } private boolean isWannable(Set<Integer> winnableNumbers, Set<Integer> primeNumbers, int currentNumber) { for (Integer operationNumber : primeNumbers) { if(isWinOperation(currentNumber, operationNumber, winnableNumbers)) { return true; } } return false; } private boolean isWinOperation(int currentNumber, Integer operationNumber, Collection<Integer> winnableNumbers) { Integer nextOpponentNumber = currentNumber - operationNumber; if(nextOpponentNumber <= 1) { return false; } if(winnableNumbers.contains(nextOpponentNumber)) { return false; } return true; } private boolean isPrime(int selfNumber, Set<Integer> primeNumbers) { for (Integer primeNumber : primeNumbers) { if(selfNumber % primeNumber == 0) { return false; } } return true; } private void output(boolean canWin) { System.out.println(canWin ? WIN_DISPLAY : LOSE_DISPLATY); } private int read() { @SuppressWarnings("resource") Scanner sc = new Scanner(System.in); return sc.nextInt(); } }