回答
#60773 No.305 鍵(2) - yukicoder
今度は桁数が大きいため,単純な総当りではダメです.
幾つか解決方法があると思いますが,私の解決方法を.
このクエリは,投げると X locked のように帰ってきて,Xがいくつ合っていたのか,という情報を取れます.
というわけで,ある桁から0から1ずつ変えてみて,前回までの結果と一致数が異なっていれば,その桁についてはあたっているかどうかを確定できることがわかります.
現在"i"を見ているとすると,現在の一致数>前回の一致数の場合,iがその桁では一致している数とみなせます.
現在の一致数<前回の一致数の場合,i-1がその桁では一致している数とみなせます(もしかしてこれ成立するの,0と1をチェックした場合のみかも)
現在の一致数=現在の一致数の場合,その桁についてはまだあっている数がわからないので,iを1増やします….
みたいな方針で調べれば,全探索といえど,回数はかなり抑えることが出来ます.
コンテスト中に解くことが出来てよかった…
res = "" cnt = 0 curdigit = 0 lastnum = -1 while res != "unlocked" do inp = format("%010d", cnt) puts inp STDOUT.flush num, res = gets.chomp.split(" ") num = num.to_i if num == 10 break end if lastnum == -1 cnt += 10 ** curdigit lastnum = num elsif lastnum < num curdigit += 1 lastnum = -1 elsif lastnum > num cnt -= 10 ** curdigit curdigit += 1 lastnum = -1 else cnt += 10 ** curdigit lastnum = num end end