結果
問題 | No.3 ビットすごろく |
ユーザー | tetsu |
提出日時 | 2018-03-04 15:00:22 |
言語 | Java21 (openjdk 21) |
結果 |
AC
|
実行時間 | 88 ms / 5,000 ms |
コード長 | 2,836 bytes |
コンパイル時間 | 3,631 ms |
コンパイル使用メモリ | 77,856 KB |
実行使用メモリ | 54,388 KB |
最終ジャッジ日時 | 2023-09-14 00:56:35 |
合計ジャッジ時間 | 6,953 ms |
ジャッジサーバーID (参考情報) |
judge13 / judge14 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 44 ms
49,312 KB |
testcase_01 | AC | 43 ms
49,572 KB |
testcase_02 | AC | 44 ms
49,564 KB |
testcase_03 | AC | 54 ms
51,492 KB |
testcase_04 | AC | 48 ms
49,804 KB |
testcase_05 | AC | 65 ms
51,968 KB |
testcase_06 | AC | 57 ms
49,636 KB |
testcase_07 | AC | 53 ms
50,024 KB |
testcase_08 | AC | 62 ms
50,608 KB |
testcase_09 | AC | 67 ms
51,096 KB |
testcase_10 | AC | 70 ms
51,616 KB |
testcase_11 | AC | 68 ms
51,356 KB |
testcase_12 | AC | 68 ms
51,372 KB |
testcase_13 | AC | 55 ms
49,700 KB |
testcase_14 | AC | 79 ms
51,540 KB |
testcase_15 | AC | 84 ms
53,300 KB |
testcase_16 | AC | 74 ms
52,148 KB |
testcase_17 | AC | 85 ms
53,576 KB |
testcase_18 | AC | 53 ms
49,704 KB |
testcase_19 | AC | 86 ms
53,136 KB |
testcase_20 | AC | 48 ms
49,836 KB |
testcase_21 | AC | 46 ms
49,804 KB |
testcase_22 | AC | 73 ms
51,528 KB |
testcase_23 | AC | 85 ms
53,812 KB |
testcase_24 | AC | 88 ms
54,388 KB |
testcase_25 | AC | 87 ms
53,732 KB |
testcase_26 | AC | 44 ms
49,440 KB |
testcase_27 | AC | 54 ms
49,612 KB |
testcase_28 | AC | 82 ms
52,000 KB |
testcase_29 | AC | 71 ms
51,720 KB |
testcase_30 | AC | 45 ms
49,600 KB |
testcase_31 | AC | 44 ms
49,436 KB |
testcase_32 | AC | 68 ms
51,592 KB |
ソースコード
package yukicoder; import java.io.BufferedReader; import java.io.IOException; import java.io.InputStream; import java.io.InputStreamReader; import java.util.ArrayList; import java.util.Arrays; import java.util.Comparator; import java.util.PriorityQueue; import java.util.StringTokenizer; public class P3 { static long[] dist; static long INF = 100000000000000000L; static ArrayList<ArrayList<Edge>> adj; static class Edge { int to; long w; Edge(int _to, long _w) { this.to = _to; this.w = _w; } @Override public String toString() { return "(to=" + to + ", w=" + w + ")"; } } static class NextNode { int id; long cost; NextNode(int _id, long _cost) { id = _id; cost = _cost; } } static void initG(int V) { // V: the number of vertexes for(int i=0; i<V; i++) { adj.add(new ArrayList<Edge>()); } } static void dijkstra(int s) { Arrays.fill(dist, INF); dist[s] = 0; PriorityQueue<NextNode> pq = new PriorityQueue<NextNode>(new Comparator<NextNode>() { public int compare(NextNode n1, NextNode n2) { if(n1.cost > n2.cost) return 1; else if(n1.cost==n2.cost) return 0; else return -1; } }); pq.add(new NextNode(s, 0)); while(!pq.isEmpty()) { NextNode cn = pq.poll(); if(cn.cost > dist[cn.id]) continue; for(Edge e : adj.get(cn.id)) { if(cn.cost + e.w < dist[e.to]) { dist[e.to] = cn.cost + e.w; pq.add(new NextNode(e.to, dist[e.to])); } } } } public static void main(String[] args) throws IOException { MyScanner sc = new MyScanner(System.in); int n = sc.nextInt(); dist = new long[n+1]; adj = new ArrayList<ArrayList<Edge>>(n+1); initG(n+1); for(int i=1; i<=n; i++) { int d = digit(i); if(0<=i+d && i+d<=n) adj.get(i).add(new Edge(i+d, 1)); if(0<=i-d && i-d<=n) adj.get(i).add(new Edge(i-d, 1)); } dijkstra(1); if(dist[n]>=INF) { System.out.println(-1); } else { System.out.println(dist[n]+1); } } public static int digit(int n) { int ret = 0; while(n>0) { if(n%2==1) ret++; n/=2; } return ret; } static class MyScanner { BufferedReader br; StringTokenizer st; public MyScanner(InputStream s) { br=new BufferedReader(new InputStreamReader(s)); } public String nextLine() throws IOException { return br.readLine(); } public String next() throws IOException { while(st==null || !st.hasMoreTokens()) st=new StringTokenizer(br.readLine()); return st.nextToken(); } public int nextInt() throws IOException { return Integer.parseInt(next()); } public double nextDouble() throws IOException { return Double.parseDouble(next()); } public boolean ready() throws IOException { return br.ready(); } public long nextLong() throws IOException { return Long.parseLong(next()); } } }