174AC - ABC104C: All Green
ABC104-C (300 points)
問題
点の問題がそれぞれ 問, 計 問の問題が与えられ, 総合スコアを以下のように計算するとき, 点以上の総合スコアを獲得するために解かなければならない最少の問題数を求める.
- 基本スコア:解いた問題すべての配点の合計.
- コンプリートボーナス: 点を付けられた 問の問題すべてを解くと, 基本スコアとは別に 点を獲得.
- 総合スコア:基本スコアとコンプリートボーナスの合計.
- 入力は全て整数.
- は全て100の倍数.
- 総合スコアを 点以上にすることは可能.
方針
- なので, 各点数の問題群について全て解く or 解かないで ケースを全探索.
import math # input D, G = map(int, input().split()) Problems = [list(map(int, input().split())) for _ in range(D)] ans = float('inf') for i in range(1 << D): # bit全探索 solved = [a for a in range(D)] # 全て解く=ボーナス点をもらう問題群 count = 0 point = 0 for j in range(D): # 全て解く=ボーナス点をもらう問題群の点数合計 if i & (1 << j): # (j + 1) * 100 点の問題を全て解く場合 count += Problems[j][0] point += Problems[j][0] * (j + 1) * 100 + Problems[j][1] solved.remove(j) # (j + 1) * 100 点の問題は全て解答済 if point < G and len(solved) > 0: k = max(solved) if math.ceil((G - point) / ((k + 1) * 100)) > Problems[k][0] - 1: continue else: count += math.ceil((G - point) / ((k + 1) * 100)) ans = min(ans, count) else: ans = min(ans, count) print(ans)