結果

問題 No.3 ビットすごろく
ユーザー atfr
提出日時 2016-08-22 16:25:30
言語 PHP
(843.2)
結果
TLE  
実行時間 -
コード長 1,622 bytes
コンパイル時間 378 ms
コンパイル使用メモリ 30,968 KB
実行使用メモリ 42,892 KB
最終ジャッジ日時 2024-11-07 22:35:18
合計ジャッジ時間 7,210 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 3 TLE * 1 -- * 29
権限があれば一括ダウンロードができます
コンパイルメッセージ
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