結果
問題 | No.1152 10億ゲーム |
ユーザー | 37zigen |
提出日時 | 2020-07-13 06:21:43 |
言語 | Java21 (openjdk 21) |
結果 |
AC
|
実行時間 | 586 ms / 2,000 ms |
コード長 | 4,512 bytes |
コンパイル時間 | 2,535 ms |
コンパイル使用メモリ | 79,720 KB |
実行使用メモリ | 81,992 KB |
平均クエリ数 | 23.14 |
最終ジャッジ日時 | 2023-09-24 03:54:00 |
合計ジャッジ時間 | 28,769 ms |
ジャッジサーバーID (参考情報) |
judge12 / judge14 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 468 ms
78,788 KB |
testcase_01 | AC | 462 ms
79,092 KB |
testcase_02 | AC | 472 ms
78,620 KB |
testcase_03 | AC | 467 ms
80,032 KB |
testcase_04 | AC | 465 ms
79,880 KB |
testcase_05 | AC | 477 ms
78,932 KB |
testcase_06 | AC | 577 ms
79,624 KB |
testcase_07 | AC | 473 ms
81,980 KB |
testcase_08 | AC | 464 ms
79,092 KB |
testcase_09 | AC | 466 ms
76,840 KB |
testcase_10 | AC | 468 ms
79,828 KB |
testcase_11 | AC | 468 ms
79,520 KB |
testcase_12 | AC | 473 ms
79,800 KB |
testcase_13 | AC | 481 ms
79,336 KB |
testcase_14 | AC | 476 ms
79,520 KB |
testcase_15 | AC | 448 ms
78,980 KB |
testcase_16 | AC | 454 ms
79,584 KB |
testcase_17 | AC | 466 ms
79,684 KB |
testcase_18 | AC | 479 ms
79,612 KB |
testcase_19 | AC | 481 ms
80,096 KB |
testcase_20 | AC | 453 ms
81,992 KB |
testcase_21 | AC | 443 ms
78,332 KB |
testcase_22 | AC | 454 ms
79,012 KB |
testcase_23 | AC | 458 ms
79,908 KB |
testcase_24 | AC | 485 ms
79,464 KB |
testcase_25 | AC | 482 ms
77,988 KB |
testcase_26 | AC | 451 ms
79,884 KB |
testcase_27 | AC | 500 ms
79,928 KB |
testcase_28 | AC | 451 ms
79,896 KB |
testcase_29 | AC | 475 ms
78,764 KB |
testcase_30 | AC | 470 ms
79,556 KB |
testcase_31 | AC | 476 ms
79,580 KB |
testcase_32 | AC | 467 ms
79,508 KB |
testcase_33 | AC | 476 ms
79,952 KB |
testcase_34 | AC | 477 ms
79,624 KB |
testcase_35 | AC | 452 ms
80,560 KB |
testcase_36 | AC | 586 ms
80,328 KB |
testcase_37 | AC | 468 ms
79,644 KB |
testcase_38 | AC | 576 ms
78,820 KB |
testcase_39 | AC | 476 ms
79,456 KB |
testcase_40 | AC | 473 ms
80,540 KB |
testcase_41 | AC | 478 ms
79,608 KB |
testcase_42 | AC | 465 ms
79,624 KB |
testcase_43 | AC | 473 ms
79,104 KB |
testcase_44 | AC | 483 ms
79,164 KB |
testcase_45 | AC | 472 ms
76,840 KB |
testcase_46 | AC | 469 ms
76,812 KB |
testcase_47 | AC | 465 ms
79,380 KB |
testcase_48 | AC | 471 ms
79,044 KB |
testcase_49 | AC | 474 ms
79,428 KB |
ソースコード
import java.io.IOException; import java.io.InputStream; import java.util.ArrayList; import java.util.Arrays; import java.util.Collections; import java.util.HashMap; import java.util.List; import java.util.NoSuchElementException; class FastScanner { private final InputStream in = System.in; private final byte[] buffer = new byte[1024]; private int ptr = 0; private int buflen = 0; private boolean hasNextByte() { if (ptr < buflen) { return true; }else{ ptr = 0; try { buflen = in.read(buffer); } catch (IOException e) { e.printStackTrace(); } if (buflen <= 0) { return false; } } return true; } private int readByte() { if (hasNextByte()) return buffer[ptr++]; else return -1;} private static boolean isPrintableChar(int c) { return 33 <= c && c <= 126;} private void skipUnprintable() { while(hasNextByte() && !isPrintableChar(buffer[ptr])) ptr++;} public boolean hasNext() { skipUnprintable(); return hasNextByte();} public String next() { if (!hasNext()) throw new NoSuchElementException(); StringBuilder sb = new StringBuilder(); int b = readByte(); while(isPrintableChar(b)) { sb.appendCodePoint(b); b = readByte(); } return sb.toString(); } public long nextLong() { if (!hasNext()) throw new NoSuchElementException(); long n = 0; boolean minus = false; int b = readByte(); if (b == '-') { minus = true; b = readByte(); } if (b < '0' || '9' < b) { throw new NumberFormatException(); } while(true){ if ('0' <= b && b <= '9') { n *= 10; n += b - '0'; }else if(b == -1 || !isPrintableChar(b)){ return minus ? -n : n; }else{ throw new NumberFormatException(); } b = readByte(); } } public int nextInt() { return (int)nextLong(); } } public class Main { public static void main(String[] args) { new Main().run(); } HashMap<List<Integer>,Integer> dp=new HashMap<>(); final int INF=Integer.MAX_VALUE/3; final long M=(long)1e9; ArrayList<Integer> divs=new ArrayList<>(); { for (int i=0;i<=9;++i) { for (int j=0;j<=9;++j) { int d=(int)Math.round(Math.pow(2, i)*Math.pow(5, j)); divs.add(d); } } Collections.sort(divs); for (int d:divs) dp.put(List.of(d,d), 0); } int g(int x,int i) { if (i==0&&x%2==0) return x/2; else if (i==1&&x%5==0) return x/5; else if (i==2) return (int)Math.min((long)2*x, M); else if (i==3) return (int)Math.min((long)5*x, M); else return 0; } void build() { for (int t=0;t<100;++t) { for (int x0:divs) { in:for (int x1:divs) { if (dp.containsKey(List.of(x0,x1))) continue; for (int i=0;i<4;++i) { long nx0=g(x0,i); if (nx0==x0 || nx0==0 || M%nx0!=0) continue; if (nx0==x1) { dp.put(List.of(x0,x1), 1); continue in; } } int ret=INF; in2:for (int i=0;i<4;++i) { int nx0=g(x0,i); if (nx0==x0 || nx0==0 || M%nx0!=0) continue; int tmp=0; for (int j=0;j<4;++j) { int nx1=g(x1,j); if (nx1==x1 || nx1==0 || M%nx1!=0) continue; if (!dp.containsKey(List.of(nx0,nx1))) { continue in2; } tmp=Math.max(tmp, 1+dp.get(List.of(nx0,nx1))); } ret=Math.min(ret, tmp); } if (ret!=INF) dp.put(List.of(x0,x1), ret); } } } } void run() { FastScanner sc=new FastScanner(); build(); int x0=sc.nextInt(); boolean first=true; while (true) { int x1=sc.nextInt(); if (x0==x1) { assert(!first); return; } first=false; int cur=dp.get(List.of(x0,x1)); for (int i=0;i<4;++i) { int nx0=g(x0,i); if (nx0==x0 || nx0==0 || M%nx0!=0) continue; if (x1==nx0) { System.out.println(nx0); return; } int next=0; for (int j=0;j<4;++j) { int nx1=g(x1,j); if (nx1==x1 || nx1==0 || M%nx1!=0) continue; next=Math.max(next,dp.get(List.of(nx0,nx1))); } if (next==cur-1) { x0=nx0; System.out.println(x0); if (x0==x1) return; break; } } } } void tr(Object...objects) {System.out.println(Arrays.deepToString(objects));} }