mini notes

競技プログラミングの解法メモを残していきます。

CODE FESTIVAL 2016 qual B D - Greedy customers (700)

問題:D - Greedy customers

解答:Submission #9879171 - CODE FESTIVAL 2016 qual B

メモ:小さい数から売ってゆくとよさそう。 最初は1を売ってゆく。最初の数が1になるまで売る。すると次は2を売ることになる。

次の数が5である場合、2を2つ売ると5-4=1でちょうどよいが、次の数が4の場合は2を1つ売ると4-2で2となる。すると次からは2を売れなくなってしまう。このような場合は、3を売ることで4-3=1となり、売れる個数は変わらずに売るものは2のままとできる。

ただし2自体が出てしまうとどうしようもなく、次からは3を売ってゆくことになる。これを繰り返す。