結果
問題 |
No.3 ビットすごろく
|
ユーザー |
![]() |
提出日時 | 2016-01-13 15:30:51 |
言語 | Java (openjdk 23) |
結果 |
AC
|
実行時間 | 68 ms / 5,000 ms |
コード長 | 2,260 bytes |
コンパイル時間 | 2,208 ms |
コンパイル使用メモリ | 78,188 KB |
実行使用メモリ | 52,092 KB |
最終ジャッジ日時 | 2024-07-01 07:41:52 |
合計ジャッジ時間 | 5,187 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 33 |
ソースコード
// 1...N // start=1 // goal=N // その場に書かれている数字の2進数で表現した時の1のビット数 だけ「前」または「後」に進めることができる。 // (1未満とN+1以上のマスには移動することは出来ない、正確にNにならないとゴールできない) // 自然数Nを与えられた時、ゴールに到達できる最短の移動数(開始のマスへも移動にカウントする)を求めてください。 // 到達できない場合は-1を出力してください。 // 開始のマスがすでにゴールになっている場合もあリます。 import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.Arrays; import java.util.Queue; import java.util.ArrayDeque; public class Main { public static final int INF=10001;//Integer.MAX_VALUE; public static void main(String[] args) throws Exception { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); String line = br.readLine(); int n=Integer.parseInt(line); int[] dp = new int[n+1]; Arrays.fill(dp, INF); Queue<Integer> queue = new ArrayDeque<Integer>(); dp[1]=1; queue.add(1); // int moveCount = 1; while(0 < queue.size()) { Integer now = queue.poll(); int move = Integer.bitCount(now);//getMoveCount(j); if( 0 < now+move && now+move <= n ) { int next = now+move; if( dp[now]+1 < dp[next]) { dp[next] = Math.min( dp[now]+1, dp[next] ); queue.add(next); } } if( 0 < now-move && now-move <= n ) { int next = now-move; if( dp[now]+1 < dp[next] ) { dp[next] = Math.min( dp[now] + 1, dp[next] ); queue.add(next); } } } if( dp[n] == INF ) System.out.println(-1); else System.out.println(dp[n]); } // public static int getMoveCount(int x) // { // int count=0; // for( int i = 32-1; i >= 0; i-- ) { // if( ( n >> i ) & 1 ) count++; // } // return count; // } }