GCJ Round 1B Problem B. Close Match
https://code.google.com/codejam/contest/11254486/dashboard#s=p1
問題
桁がところどころ ? で伏せられている 2 つの整数 C, J が与えられる。? に好きな数字を入れていいので C と J の差の絶対値を最小化せよ。
- 1≦|C|,|J|≦18
解法
左から数字を決定していく。
左から 4 つまで一致していて 5 つ目で差ができたとする。
92535*** 92534***
このとき *** の部分をどのように決めても差は正になる。極端な例としては次のような場合があるが、これも差は正である。
92535000 92534999
したがって一度不一致になったら上はできるだけ小さく、下はできるだけ大きくするのが最適である。
DFS した。
