Codeforces Round #427 B. The number on the board

codeforces.com

ある長い数字n(最大10万桁)について、すべての桁の合計はk以上であり、幾つかの桁が書き換えられた数字(桁数は同じ)が与えられる。最小で何桁書き換えられたとかんがえられるか？

与えられた書き換え済みの数字についてまずは桁の合計を計算する。これがk未満であれば、幾つかの桁を書き換えてkにする。この時、0の桁の数～9の桁の数をカウントし、0から順番に貪欲に書き換えていく。O(log n)。