結果
問題 |
No.3 ビットすごろく
|
ユーザー |
![]() |
提出日時 | 2017-06-16 23:02:08 |
言語 | Java (openjdk 23) |
結果 |
AC
|
実行時間 | 148 ms / 5,000 ms |
コード長 | 806 bytes |
コンパイル時間 | 2,459 ms |
コンパイル使用メモリ | 78,872 KB |
実行使用メモリ | 41,724 KB |
最終ジャッジ日時 | 2024-07-01 08:44:49 |
合計ジャッジ時間 | 8,129 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 33 |
ソースコード
import java.util.ArrayDeque; import java.util.Arrays; import java.util.Deque; import java.util.Scanner; public class Main { static Scanner in = new Scanner(System.in); public static void main(String[] args) { int n = in.nextInt(); int[] d = new int[n + 1]; Arrays.fill(d, Integer.MAX_VALUE); d[1] = 1; Deque<Integer> q = new ArrayDeque<>(); q.add(1); while (q.size() > 0) { int a = q.poll(), b = bit(a); if (0 < a - b && d[a - b] > d[a] + 1) { d[a - b] = d[a] + 1; q.add(a - b); } if (a + b <= n && d[a + b] > d[a] + 1) { d[a + b] = d[a] + 1; q.add(a + b); } } System.out.println(d[n] == Integer.MAX_VALUE ? -1 : d[n]); } public static int bit(int n) { int s = 0; while (n > 0) { if (n % 2 == 1) { s++; } n /= 2; } return s; } }