AtCoder-ABC208 A - Rolling Dice / B - Factorial Yen Coin【Python解答例】
AtCoder Beginner Contest208のA とB問題についてPythonの解答例を記事にしていきます。
AtCoder Beginner Contest 208 - AtCoder
AtCoder Beginner Contest208 A - Rolling Dice
問題文
1,2,…,6 の出目がある 6 面サイコロを A 回振ったとき、出た目の合計が B になることはありますか?
制約
・1≤A≤100
・1≤B≤1000
・A,B は整数である。
解答例
a, b = map(int,input().split()) min_num = a max_num = a * 6 if b >= min_num and b <= max_num: print("Yes") else: print("No")
解説
問題文の通り1から6までの出目があるサイコロをA回振って、出た目の合計がBになることがあるか答える問題です。
サイコロをA回振ったときの出目合計の最小値はすべて1が出た場合で1×Aになります。
この最小値をmin_numに格納しました。
出目合計の最大値はすべて6が出たときでmax_numにA×6を代入します。
最後にBがmin_num以上でmax_num以下ならば、Bを出すことが可能なのでYesを、それ以外はNoを出力すればOKです。
AtCoder Beginner Contest208 B - Factorial Yen Coin
問題文
高橋王国では 1! 円硬貨 ,2! 円硬貨 ,…,10! 円硬貨が流通しています。ここで、N!=1×2×⋯×N です。
高橋君は全ての種類の硬貨を 100 枚ずつ持っており、P 円の商品をお釣りが出ないようにちょうどの金額を支払って買おうとしています。
問題の制約下で条件を満たす支払い方は必ず存在することが証明できます。
最小で何枚の硬貨を使えば支払うことができますか?
制約
・1≤P≤10^7
・P は整数である。
解答例
p = int(input()) coin = [] tmp = 1 for i in range(1,11): tmp *= i coin.append(tmp) ans = 0 for j in reversed(range(10)): ans += p // coin[j] p = p % coin[j] print(ans)
解説
1!~10!硬貨があり、ちょうどP円を払うときの最小の硬貨枚数を答える問題です。
硬貨の価値が階乗なので、貪欲に価値が高い硬貨から払えるだけ払えば最小の硬貨枚数が求まりました。
coin配列には1!~10!硬貨の価値を格納します。
ループでは価値の高い硬貨から支払えるだけ支払っていき、硬貨の枚数をansに足しあわせていきました。
ループを抜けたあとで解答であるansを出力すればACでした。
ABC208の関連記事はこちら
ebisuke33.hatenablog.com