水面下の夢

競プロやイラストに興味があります.メインブログがここ.同人サークル「かのらぶ」のページはこっち( https://yumechi0525.amebaownd.com ).ブログアイコンはYaQ(@8_9_00)さんから.

京都大学プログラミングコンテスト2014 B.数当てゲーム(2015/06/01)

タイトルのスタイルを[Problem Name] (日付)に変えることにした.
他の人も問題名でタイトル書いている人が多いため,こちらに統一した方がいいかな~ と.
(確かに探しやすさではこっちのほうが良いような気もするんですよね)
ただ,いつ解いたのかを明らかにするため,日付入れるスタイルは続けていこうかなとw

雑談はおいといて,解いた問題を.

回答

Submission #418310 - 京都大学プログラミングコンテスト2014 | AtCoder

初めて対話式? といいますか,print文使って相手からの入力待って,みたいな問題をときました.
これ面白いですね.(最初プリントした後にフラッシュ忘れて,TLEしました)

1から1000の間の数字がパスワードになっていて,こちら側は割り算する数字を出力,そして入力で割り切れるかどうかが"Y"か"N"が返ってきて,最終的なパスワードを出力….ですね.
普通にやるのならば,二分探索なのでしょうが,今回返ってくる情報は割り切れるかどうかです.
200回まで相手側には質問できて,効率よく質問することを考えると,やっぱり素数で割り切れるかどうかを判断すれば良いと思います.
なので,rubyのprimeで素数のリストを持ってきて,あとはループさせながら割り切れるかどうかを確認,割り切れるなら結果を反映して… を繰り返すだけですね.(ただ,その結果の反映をミスっていて,何度も提出しなおした模様)

require 'prime'
primes = Prime.each(1000).to_a
res = 1
primes.each { |prim|
	t = prim * res
	if t > 1000
		break
	end
	puts "? " + t.to_s
	STDOUT.flush
	s = gets.chomp 
	while s == "Y"
		t *= prim
		if t > 1000
			break
		end
		puts "? " + t.to_s
		STDOUT.flush
		s = gets.chomp
	end
	res *= t / (prim * res)
}
 
puts "! " + res.to_s

あとなんでrubyなのかといえば,素数を求めるプログラムを書くのがめんどくさかったからです(白目)
素数扱う際にprimeでパパっと持ってこれるのはやっぱりずるい.