結果
問題 | No.7 プライムナンバーゲーム |
ユーザー | ゆうき |
提出日時 | 2022-10-20 01:39:09 |
言語 | Java21 (openjdk 21) |
結果 |
AC
|
実行時間 | 227 ms / 5,000 ms |
コード長 | 5,318 bytes |
コンパイル時間 | 2,899 ms |
コンパイル使用メモリ | 92,060 KB |
実行使用メモリ | 42,248 KB |
最終ジャッジ日時 | 2024-06-30 00:50:41 |
合計ジャッジ時間 | 6,534 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge3 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 89 ms
39,744 KB |
testcase_01 | AC | 93 ms
39,520 KB |
testcase_02 | AC | 162 ms
42,248 KB |
testcase_03 | AC | 123 ms
41,512 KB |
testcase_04 | AC | 118 ms
41,424 KB |
testcase_05 | AC | 116 ms
41,236 KB |
testcase_06 | AC | 162 ms
41,780 KB |
testcase_07 | AC | 153 ms
41,696 KB |
testcase_08 | AC | 130 ms
41,616 KB |
testcase_09 | AC | 176 ms
41,912 KB |
testcase_10 | AC | 89 ms
39,284 KB |
testcase_11 | AC | 155 ms
41,780 KB |
testcase_12 | AC | 195 ms
41,788 KB |
testcase_13 | AC | 205 ms
41,924 KB |
testcase_14 | AC | 227 ms
42,004 KB |
testcase_15 | AC | 224 ms
42,072 KB |
testcase_16 | AC | 211 ms
42,024 KB |
ソースコード
import java.io.IOException; import java.io.InputStream; import java.io.OutputStream; import java.lang.management.ManagementFactory; import java.util.Arrays; import java.util.LinkedHashSet; import java.util.Set; import java.util.function.IntFunction; class Main{ boolean isDebug = ManagementFactory.getRuntimeMXBean().getInputArguments().toString() .contains("-agentlib:jdwp"); final MyReader in = new MyReader(System.in); final MyWriter out = new MyWriter(System.out); public static void main(final String[] args){ new Main().exe(); } private void exe(){ input(); preCalc(); solve(); out.flush(); } int N = in.it(); private void input(){} private void preCalc(){} String[] dp = new String[N +1]; Set<Integer> primes = primes(N); void solve(){ dp[0] = "Win"; dp[1] = "Win"; out.println(dp(N)); } private String dp(final int n){ if (dp[n] == null) { dp[n] = "Lose"; for (var p:primes) { if (n < p) break; if ("Lose".equals(dp(n -p))) { dp[n] = "Win"; break; } } } return dp[n]; } Set<Integer> primes(final int bound){ Set<Integer> ret = new LinkedHashSet<>(); for (int i = 2;i <= bound;i++) { boolean flg = true; for (final int p:ret) if (i %p == 0) { flg = false; break; } else if (i < p *p) break; if (flg) ret.add(i); } return ret; } /* 定数 */ final int mod = (int) (1e9 +7); final String yes = "Yes"; final String no = "No"; /* 入力 */ static class MyReader{ byte[] buf = new byte[1 <<16]; int head = 0; int tail = 0; InputStream in; public MyReader(final InputStream in){ this.in = in; } byte read(){ if (head == tail) { try { tail = in.read(buf); } catch (IOException e) { e.printStackTrace(); } head = 0; } return buf[head++]; } boolean isPrintable(final byte c){ return 32 < c && c < 127; } boolean isNum(final byte c){ return 47 < c && c < 58; } byte nextPrintable(){ byte ret = read(); return isPrintable(ret) ? ret : nextPrintable(); } int it(){ return (int) lg(); } int[] it(final int N){ int[] a = new int[N]; Arrays.setAll(a,i -> it()); return a; } int[][] it(final int H,final int W){ return arr(new int[H][],i -> it(W)); } int idx(){ return it() -1; } int[] idx(final int N){ int[] a = new int[N]; Arrays.setAll(a,i -> idx()); return a; } int[][] idx(final int H,final int W){ return arr(new int[H][],i -> idx(W)); } long lg(){ byte i = nextPrintable(); boolean negative = i == 45; long n = negative ? 0 : i -'0'; while (isPrintable(i = read())) n = 10 *n +i -'0'; return negative ? -n : n; } long[] lg(final int N){ long[] a = new long[N]; Arrays.setAll(a,i -> lg()); return a; } long[][] lg(final int H,final int W){ return arr(new long[H][],i -> lg(W)); } char[] ch(){ return str().toCharArray(); } char[][] ch(final int H){ return arr(new char[H][],i -> ch()); } String line(){ StringBuilder sb = new StringBuilder(); byte c; while (isPrintable(c = read()) || c == ' ') sb.append((char) c); return sb.toString(); } String str(){ StringBuilder sb = new StringBuilder(); sb.append((char) nextPrintable()); byte c; while (isPrintable(c = read())) sb.append((char) c); return sb.toString(); } String[] str(final int N){ return arr(new String[N],i -> str()); } <T> T[] arr(final T[] arr,final IntFunction<T> f){ Arrays.setAll(arr,f); return arr; } } /* 出力 */ static class MyWriter{ OutputStream out; byte[] buf = new byte[1 <<16]; byte[] ibuf = new byte[20]; int tail = 0; public MyWriter(final OutputStream out){ this.out = out; } void flush(){ try { out.write(buf,0,tail); tail = 0; } catch (IOException e) { e.printStackTrace(); } } void write(final byte b){ buf[tail++] = b; if (tail == buf.length) flush(); } void write(final byte[] b,final int off,final int len){ for (int i = off;i < off +len;i++) write(b[i]); } void write(final char c){ write((byte) c); } void write(long n){ if (n < 0) { n = -n; write('-'); } int i = ibuf.length; do { ibuf[--i] = (byte) (n %10 +'0'); n /= 10; } while (n > 0); write(ibuf,i,ibuf.length -i); } void println(final long n){ write(n); write('\n'); } public void println(final double d){ println(String.valueOf(d)); } void println(final String s){ byte[] b = s.getBytes(); for (byte bb:b) write(bb); write('\n'); } public void println(final char[] s){ for (char bb:s) write(bb); write('\n'); } void println(final int[] a){ for (int i = 0;i < a.length;i++) { if (0 < i) write(' '); write(a[i]); } write('\n'); } } }