No.286 Modulo Discount Store
問題文
個の商品がそれぞれ定価円で売られているお店がある。
このお店で商品を購入する時、「今まで買った商品の"定価"の金額を合計して1000で割った余り()の料金分」を購入ごとに値引きしてくれるという。
ただし、購入する商品が値引き後0円未満になる場合は、0円で購入する。
あなたは、同じものを買わずに個の商品を全て購入したいと思っている。
このとき個の商品をすべて購入するときに、最小の購入金額の合計はいくらか計算してください。
商品を購入する順番は自由であるが、同時には購入できず1つずつしか購入できない。
入力
入力は全て整数で与えられる。
商品の定価の値段を表す。
出力
個の商品をすべて購入するときに、最小の合計の購入金額はいくらか計算してください。
サンプル
サンプル1
入力
3 100 200 300
出力
200
商品、商品、商品の順に購入する。
100円の商品を購入する。この時、まだ何も買ってないので割引はない、100円で購入する。
200円の商品を購入する。この時、商品を購入しているので100円引きされ、(200-100=)100円で購入できる。
300円の商品を購入する。この時、商品,商品を購入しているので300円引きされ、0円で購入できる。
よって、200円ですべて購入できる。
サンプル2
入力
3 1000 900 800
出力
1000
商品、商品、商品の順に購入する。
900円の商品を購入する。この時、まだ何も買ってないので割引はない、900円で購入する。
1000円の商品を購入する。この時、商品を購入しているので900円引きされ、100円で購入できる。
800円の商品を購入する。この時、商品,商品を購入しているので900円引きされ
(割引額は今までの購入した定価の金額1900円の1000で割った余りの900円である)、0円で購入できる。
よって、1000円ですべて購入できる。購入する順番を入れ替えても1000円未満で購入する方法はない。
サンプル3
入力
5 10000 1000 100 10 1
出力
10877
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。