ABC #085 C - Otoshidama
問題の概要
問題: AtCoder Beginner Contest #085 C - Otoshidama
お年玉を枚 のお札で合計円 いただいた。 このとき、10000円札・5000円札・1000円札の枚数を求める。
但し、複数の可能性がある場合はそのうちの1組を出力する。
また、お札の組み合わせが存在しない場合は-1 -1 -1
と出力。
解答例
10000円札 | 5000円札 | 1000円札 | |
---|---|---|---|
枚数 |
10000円札・5000円札の全探索:
式(1)より、1000円札の枚数を計算によって求めることができる。 したがって、3種類のお札を全探索した場合の計算量からへ削減できる。
また、AtCoder上の環境では、平均実行時間7 ms
となった。
10000円札の全探索:
式(1)及び(2)より、10000万円札の枚数を固定すると、二元一次連立方程式となる。 したがって、3種類のお札を全探索した場合の計算量からへ削減できる。
また、AtCoder上の環境では、平均実行時間1 ms
となった。