Document

Hits and Blows
問題作成:泉
解答作成:荒木、三廻部
英訳:泉
解説:荒木
問題の説明
• 一人が、0123～9876の4桁の数字(異なる桁に同じ
数字(0～9)を含まない)のうち一つを秘密の数字とし
て選ぶ。
• もう一人が、それを以下の手順を繰り返して推測す
る。
– 何か数字を言い、それに対してhitの数とblowの数を教え
てもらう。hitとは場所も数字もあっている桁、blowとは場
所が異なるが数字があっている桁
– 0123 にたいして0324を言った場合は、hit:2,blow:1
• これまでのやり取りの履歴が与えられる
• これまでのやり取りから秘密の数字が分かる
時はその数字を出力する。
• そうではないが、次にある数字を言えば、そ
れに対する答えから秘密の数字が分かるな
らば、その言うべき数字のうち最小のものを
出力する。
• 上記のいずれでもない場合は????を出力す
る。
解法
• 全探索
• 0123～9876から、履歴のhitとblowに矛盾しないも
のだけを残す。
• 残ったものが一つだけならその数字を出力する。
• 残ったものが二個以上なら、次に言うべき数字の候
補を0123～9876の小さい方から順に一つずつ選び、
その数字を言った時の応答を残った数字全てにつ
いて調べる。残った数字全てで応答が異なるなら、
その選んだ数字を言えばよいので、それを出力する。
• どの数字を言っても応答が被ってしまうなら、????
を出力する。
Sample Inputでの動作例
• 履歴が以下の通り
– 0123 hit:0 blow:4
– 1230 hit:0 blow:4
• 履歴にマッチする数字は2301か3012
• 0123～9876の小さい方から、次に言う数字の候補
を一つずつ調べる。
– 0123…2301の時はhit:0 blow:4, 3012の時はhit:0
blow:4 被ってしまう
– 0132…2301の時はhit:0 blow:4, 3012の時はhit:1
blow:3 被らないので0132が答え。
注意
• 先頭の0を出力する処理をきちんとしましょう。
• 答えを出力する箇所が複数あるのに、一箇
所しかその処理を入れていないプログラムが
ありました。
結果
• Submit:12
• Accept:6(first accept: __________57分)
• ちなみにコンテスト前予想では全チーム解くと
思っていました…。頑張ってください。

Download Report