結果
問題 |
No.3 ビットすごろく
|
ユーザー |
![]() |
提出日時 | 2016-11-07 15:01:06 |
言語 | Java (openjdk 23) |
結果 |
AC
|
実行時間 | 153 ms / 5,000 ms |
コード長 | 1,453 bytes |
コンパイル時間 | 2,384 ms |
コンパイル使用メモリ | 78,628 KB |
実行使用メモリ | 54,440 KB |
最終ジャッジ日時 | 2024-07-01 08:09:26 |
合計ジャッジ時間 | 7,762 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 33 |
ソースコード
import java.util.*; public class Main { private static Scanner sc = new Scanner(System.in); public static void main(String[] args) throws Exception { int n = sc.nextInt(); int[] dp = new int[n+1]; Deque<Pair> que = new ArrayDeque<>(); que.addLast(new Pair(1, 1)); dp[1] = 1; while (true) { if (que.isEmpty()) break; Pair p = que.pollFirst(); int m = count(p.val); int nn = p.val-m; int np = p.val+m; int nc = p.cnt+1; if (nn>0) { if (dp[nn]==0) { dp[nn] = nc; que.addLast(new Pair(nn,nc)); } } if (np<=n) { if (dp[np]==0) { dp[np] = nc; que.addLast(new Pair(np,nc)); } } } if (dp[n]==0) { System.out.println(-1); } else { System.out.println(dp[n]); } } private static int count(int val) { String s = Integer.toBinaryString(val); int ret = 0; for (int i = 0;i < s.length();i++) { if (s.charAt(i)=='1') ret++; } return ret; } static class Pair { public int val; public int cnt; public Pair(int a, int b) { val = a; cnt = b; } } }