ABC #085 C - Otoshidama
問題の概要
問題: AtCoder Beginner Contest #085 C - Otoshidama
お年玉を枚
のお札で合計
円
いただいた。
このとき、10000円札・5000円札・1000円札の枚数を求める。
但し、複数の可能性がある場合はそのうちの1組を出力する。
また、お札の組み合わせが存在しない場合は-1 -1 -1
と出力。
解答例
10000円札 | 5000円札 | 1000円札 | |
---|---|---|---|
枚数 | |
|
|
10000円札・5000円札の全探索: ![O(N^{2})](http://chart.apis.google.com/chart?cht=tx&chl=%20O%28N%5E%7B2%7D%29)
![f:id:farma_11:20180124160631p:plain f:id:farma_11:20180124160631p:plain](https://cdn-ak.f.st-hatena.com/images/fotolife/f/farma_11/20180124/20180124160631.png)
式(1)より、1000円札の枚数を計算によって求めることができる。
したがって、3種類のお札を全探索した場合の計算量
から
へ削減できる。
また、AtCoder上の環境では、平均実行時間7 ms
となった。
10000円札の全探索: ![O(N)](http://chart.apis.google.com/chart?cht=tx&chl=%20O%28N%29)
![f:id:farma_11:20180124160843p:plain f:id:farma_11:20180124160843p:plain](https://cdn-ak.f.st-hatena.com/images/fotolife/f/farma_11/20180124/20180124160843.png)
式(1)及び(2)より、10000万円札の枚数を固定すると、二元一次連立方程式となる。
したがって、3種類のお札を全探索した場合の計算量
から
へ削減できる。
また、AtCoder上の環境では、平均実行時間1 ms
となった。