タイトルのスタイルを[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でパパっと持ってこれるのはやっぱりずるい.