結果

問題 No.3 ビットすごろく
ユーザー atfratfr
提出日時 2016-08-22 16:25:30
言語 PHP
(8.3.4)
結果
TLE  
実行時間 -
コード長 1,622 bytes
コンパイル時間 378 ms
コンパイル使用メモリ 30,968 KB
実行使用メモリ 42,892 KB
最終ジャッジ日時 2024-11-07 22:35:18
合計ジャッジ時間 7,210 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ
（要ログイン）

テストケース

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

ソースコード

diff # 

<?php

class MyClass {

	private $N;
	private $count_min;
	
	function __construct($n) {
		$this->N = $n;
	}
	
	public function changeBinary($num = 0) {
		$binary = array();
		if(!$num) return 0;
		for ($tmp_num = $num; $tmp_num >= 1; $tmp_num /= 2){
			if($tmp_num % 2 == 1) {
				$tmp_num--;
				array_unshift($binary, 1);
			} else {
				array_unshift($binary, 0);
			}
		}
		return implode('', $binary);
	}
	
	public function countBinaryOne($num) {
		$binary = $this->changeBinary($num);
		return substr_count($binary, 1);
	}
	
	public function init() {
		$this->count_min = 0;
	}
	
	public function searchStart() {
		$this->init();
		$this->loop();
		if($this->count_min > 0) {
			return $this->count_min;
		}
		return -1;
	}
	
	public function checkGoal($num) {
		if($num != $this->N) return false;
		return true;
	}
	
	public function checkRoute($num) {
		if($num < 1) return false;
		elseif($num > $this->N) return false;
		return true;
	}
	
	public function loop($now = 1, $count = 1, $passed = array()) {
		
		if(!$this->checkRoute($now)) {
			return false;
		}
		elseif(isset($passed[$now]) && $passed[$now] === true) {
			return false;
		}
		
		if($this->checkGoal($now)) {
			if($this->count_min == 0 || $this->count_min > $count) {
				$this->count_min = $count;
			}
			return true;
		}
		
		$passed[$now] = true;
		
		$binary_one_check = $this->countBinaryOne($now);
		$this->loop($now + $binary_one_check, $count + 1, $passed);
		$this->loop($now - $binary_one_check, $count + 1, $passed);
	}
	
}

while($input = fgets(STDIN)) {
	$class = new MyClass((int)$input);
	echo $class->searchStart() . PHP_EOL;
}
0