174AC - ABC104C: All Green

ABC104-C (300 points)
問題

 i \times 100 \ (1 \leq i \leq D) 点の問題がそれぞれ  p_i 問, 計  p_1 + p_2 + \ldots + p_D 問の問題が与えられ, 総合スコアを以下のように計算するとき,  G 点以上の総合スコアを獲得するために解かなければならない最少の問題数を求める.

  • 基本スコア:解いた問題すべての配点の合計.
  • コンプリートボーナス:  100i 点を付けられた  p_i 問の問題すべてを解くと, 基本スコアとは別に  c_i 点を獲得.
  • 総合スコア:基本スコアとコンプリートボーナスの合計.
  •  1 \leq D \leq 10
  •  1 \leq p_i \leq 10^2
  •  1 \leq c_i \leq 10^6
  •  100 \leq G
  • 入力は全て整数.
  •  c_i, G は全て100の倍数.
  • 総合スコアを  G 点以上にすることは可能.
方針
  •  1 \leq D \leq 10 なので, 各点数の問題群について全て解く or 解かないで  2^D ケースを全探索.
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)