結果

問題 No.3 ビットすごろく
コンテスト
ユーザー しめはじめ
提出日時 2019-06-12 14:14:21
言語 PHP
(843.2)
結果
AC  
実行時間 44 ms / 5,000 ms
コード長 1,152 bytes
コンパイル時間 1,056 ms
コンパイル使用メモリ 32,272 KB
実行使用メモリ 32,656 KB
最終ジャッジ日時 2024-07-01 09:21:38
合計ジャッジ時間 3,471 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 33
権限があれば一括ダウンロードができます
コンパイルメッセージ
No syntax errors detected in Main.php

ソースコード

diff #
raw source code 

<?php
// 移動数（1の立った個数を数える）
function GetMoveStep( $n ){
  $step = $n;
  $n = $n - (($n >> 1) & 0x55555555);
  $n = ($n & 0x33333333) + (($n >> 2) & 0x33333333);
  $n = ($n + ($n >> 4)) & 0x0f0f0f0f;
  $n = $n + ($n >> 8);
  $n = $n + ($n >> 16);
  return $n & 0x3f;
}

// 入力値
$n = trim( fgets( STDIN ) );
// キュー
$queue[] = 1;
// 回数記録用
$dist = array();
$dist[1] = 1;
for( $i = 2; $i <= 10000; $i++ ){
    $dist[$i] = -1;
}
//番兵
$banpei = 0;

while( count( $queue ) > 0 && $banpei < 10000 ){
    
    // キューの頭（現在地）を取得して除く
    $idx = $queue[0];
    array_shift( $queue );
    // 移動先を得る
    $step = GetMoveStep( $idx );
    $pos_f = $idx + $step;
    $pos_b = $idx - $step;
    // 移動先に対して加算していく、キューも貯める
	if ( $pos_f >= 1 && $pos_f <= $n && $dist[$pos_f] == -1 ) {
		$dist[$pos_f] = $dist[$idx] + 1;
		$queue[] = $pos_f;
	}
	if ( $pos_b >= 1 && $pos_b <= $n && $dist[$pos_b] == -1 ) {
		$dist[$pos_b] = $dist[$idx] + 1;
		$queue[] =  $pos_b;
	}
    //暴走防止番兵
    $banpei++;
}
printf( "%d\n", $dist[$n] );
0