結果

問題 No.3 ビットすごろく
ユーザー しめはじめしめはじめ
提出日時 2019-06-12 14:14:21
言語 PHP
(8.3.4)
結果
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
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 41 ms
32,532 KB
testcase_01 AC 41 ms
32,528 KB
testcase_02 AC 41 ms
32,532 KB
testcase_03 AC 42 ms
32,404 KB
testcase_04 AC 42 ms
32,528 KB
testcase_05 AC 42 ms
32,528 KB
testcase_06 AC 42 ms
32,532 KB
testcase_07 AC 42 ms
32,268 KB
testcase_08 AC 42 ms
32,404 KB
testcase_09 AC 43 ms
32,400 KB
testcase_10 AC 44 ms
32,400 KB
testcase_11 AC 43 ms
32,340 KB
testcase_12 AC 43 ms
32,404 KB
testcase_13 AC 42 ms
32,400 KB
testcase_14 AC 44 ms
32,656 KB
testcase_15 AC 44 ms
32,528 KB
testcase_16 AC 44 ms
32,532 KB
testcase_17 AC 44 ms
32,404 KB
testcase_18 AC 42 ms
32,272 KB
testcase_19 AC 44 ms
32,532 KB
testcase_20 AC 41 ms
32,404 KB
testcase_21 AC 41 ms
32,528 KB
testcase_22 AC 44 ms
32,528 KB
testcase_23 AC 44 ms
32,212 KB
testcase_24 AC 44 ms
32,528 KB
testcase_25 AC 44 ms
32,404 KB
testcase_26 AC 41 ms
32,148 KB
testcase_27 AC 42 ms
32,532 KB
testcase_28 AC 44 ms
32,532 KB
testcase_29 AC 43 ms
32,532 KB
testcase_30 AC 41 ms
32,268 KB
testcase_31 AC 41 ms
32,532 KB
testcase_32 AC 43 ms
32,144 KB
権限があれば一括ダウンロードができます
コンパイルメッセージ
No syntax errors detected in Main.php

ソースコード

diff # 

<?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