ABC155 E - Payment (500)

ある桁に対して、全額払うかまったく払わずにおつりとしてもらうかのどちらかが最善になる

下の桁から見ていく

その桁の値が10以上なら10以上の部分を一つ上の桁に渡す

その桁の値が5未満ならその桁はその額を払うことにする

その桁の値が5より大きいならその桁はおつりとして受け取ることにする

上はお釣りとしてもらう時と支払う時の必要枚数が2枚以上離れていて繰り上げても1枚しか影響がないので、貪欲に決める

その桁の値が5の場合は一つ上の値が5未満か5以上かで支払うかお釣りかを決める

最上桁だけ実装上繰り上がり先がないので注意する