問題
日本でよく使われる紙幣は、10000円札、5000円札、1000円札です。以下、「お札」とはこれらのみを指します。
青橋くんが言うには、彼が祖父から受け取ったお年玉袋にはお札が N枚入っていて、合計で Y円だったそうですが、嘘かもしれません。このような状況がありうるか判定し、ありうる場合はお年玉袋の中身の候補を一つ見つけてください。なお、彼の祖父は十分裕福であり、お年玉袋は十分大きかったものとします。
入出力例
入力例
9 45000
出力例
4 0 5
お年玉袋に10000円札4枚と1000円札5枚が入っていれば、合計枚数が9枚、合計金額が45000円になります。
5000円札9枚という可能性も考えられるため、0 9 0 も正しい出力です。
自分の回答
def otoshidama(number, price)
(0..number).each do |a|
(0..number).each do |b|
(0..number).each do |c|
if a * 10000 + b * 5000 + c * 1000 == price && a + b + c <= number
print ("#{a} #{b} #{c}")
exit
end
end
end
end
print ("#{-1} #{-1} #{-1}")
end
number, price = gets.chomp.split(" ").map(&:to_i)
otoshidama(number, price)この問題からC問題となるのですがとても難しいです。このコードだと、正解になりません。不正解になるのと、実行時間制限超過になります。特に実行時間制限が引っかかります。確かに、お札の枚数が2000枚くらいになると、計算が終わりません。
加えて、eachのところをすべて(0..number)としているので、間違った答えを弾き出します。
自力ではここまでしかできませんでした。
もっとよくする
def otoshidama(number, price)
(0..number).each do |a|
(0..number - a).each do |b|
c = number - a - b
if a * 10000 + b * 5000 + c * 1000 == price && a + b + c <= number
print ("#{a} #{b} #{c}")
exit
end
end
end
print ("#{-1} #{-1} #{-1}")
end
number, price = gets.chomp.split(" ").map(&:to_i)
otoshidama(number, price)他の方の答えを参考にしたところ、2種類のお札の枚数が決まれば、残り一種類のお札の枚数は決まる、と書いてありました。その方のを真似て、eachを一つ減らして、範囲を見直したところ正解となりました。eachを一つ減らすだけで、こんなにも変化するのかと思いました。
B問題までは実行時間制限を意識したことはなかったのですが、これからは、問題も複雑になってくるので、いかに簡単な記述にするのかというところを気をつけなければならないと思いました。
