ABC #085 C - Otoshidama

問題の概要


問題: AtCoder Beginner Contest #085 C - Otoshidama

 お年玉を N (1 \leq N \leq 2000) のお札で合計 Y (1000 \leq Y \leq 2 \times 10^{7}) いただいた。 このとき、10000円札・5000円札・1000円札の枚数を求める。

 但し、複数の可能性がある場合はそのうちの1組を出力する。 また、お札の組み合わせが存在しない場合は-1 -1 -1と出力。

解答例


10000円札 5000円札 1000円札
枚数  X_{10}  X_{5}  X_{1}

10000円札・5000円札の全探索:  O(N^{2})

f:id:farma_11:20180124160631p:plain

 式(1)より、1000円札の枚数 X_{1}を計算によって求めることができる。 したがって、3種類のお札を全探索した場合の計算量 O(N^{3})から O(N^{2})へ削減できる。

 また、AtCoder上の環境では、平均実行時間7 msとなった。

10000円札の全探索:  O(N)

f:id:farma_11:20180124160843p:plain

 式(1)及び(2)より、10000万円札の枚数 X_{10}を固定すると、二元一次連立方程式となる。 したがって、3種類のお札を全探索した場合の計算量 O(N^{3})から O(N)へ削減できる。

  また、AtCoder上の環境では、平均実行時間1 msとなった。