Problem:


Score : 300 points

Problem Statement

A programming competition site AtCode provides algorithmic problems.
Each problem is allocated a score based on its difficulty.
Currently, for each integer i between 1 and D (inclusive), there are p_i problems with a score of 100i points.
These p_1 + … + p_D problems are all of the problems available on AtCode.

A user of AtCode has a value called total score.
The total score of a user is the sum of the following two elements:

Base score: the sum of the scores of all problems solved by the user.

Perfect bonuses: when a user solves all problems with a score of 100i points, he/she earns the perfect bonus of c_i points, aside from the base score (1 ≤ i ≤ D).

Takahashi, who is the new user of AtCode, has not solved any problem.
His objective is to have a total score of G or more points.
At least how many problems does he need to solve for this objective?

Constraints

1 ≤ D ≤ 10

1 ≤ p_i ≤ 100

100 ≤ c_i ≤ 10^6

100 ≤ G

All values in input are integers.

c_i and G are all multiples of 100.

It is possible to have a total score of G or more points.

Input

Input is given from Standard Input in the following format:

D G
p_1 c_1
:
p_D c_D

Output

Print the minimum number of problems that needs to be solved in order to have a total score of G or more points. Note that this objective is always achievable (see Constraints).

Sample Input 1

2 700
3 500
5 800

Sample Output 1

3

In this case, there are three problems each with 100 points and five problems each with 200 points. The perfect bonus for solving all the 100-point problems is 500 points, and the perfect bonus for solving all the 200-point problems is 800 points. Takahashi's objective is to have a total score of 700 points or more.

One way to achieve this objective is to solve four 200-point problems and earn a base score of 800 points. However, if we solve three 100-point problems, we can earn the perfect bonus of 500 points in addition to the base score of 300 points, for a total score of 800 points, and we can achieve the objective with fewer problems.

Sample Input 2

2 2000
3 500
5 800

Sample Output 2

7

This case is similar to Sample Input 1, but the Takahashi's objective this time is 2000 points or more. In this case, we inevitably need to solve all five 200-point problems, and by solving two 100-point problems additionally we have the total score of 2000 points.

Sample Input 3

2 400
3 500
5 800

Sample Output 3

2

This case is again similar to Sample Input 1, but the Takahashi's objective this time is 400 points or more. In this case, we only need to solve two 200-point problems to achieve the objective.

Sample Input 4

5 25000
20 1000
40 1000
50 1000
30 1000
1 1000

Sample Output 4

66

There is only one 500-point problem, but the perfect bonus can be earned even in such a case. 



Sample input:
2 700
3 500
5 800


Sample output:
3

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline

def ceil(a, b):
    if a%b == 0:
        return a//b
    else:
        return (a//b) + 1

def main():
    D, G = map(int, input().split())
    pc = [list(map(int, input().split())) for i in range(D)]

    ans = int(1e9)
    for i in range(2**D):
        score = 0
        count = 0
        check = [False] * D
        for j in range(D):
            p, c = pc[j]
            if i&1:# 問題jを全て解く
                score += 100 * (j+1) * p + c
                count += p
                check[j] = True
            i >>= 1
        if score < G:
            for j in range(D):
                if not check[D-1-j]:
                    check[D-1-j] = True
                    p, c = pc[D-1-j]
                    tmp = ceil(G - score, (D-j) * 100)
                    if tmp < p:
                        count += tmp
                        score += tmp * (D-j) * 100
                    break
        if score >= G:
            # print(score, check, count)
            ans = min(ans, count)
    
    print(ans)




if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
d, g = map(int, input().split())

scores = []
sum = []
for i in range(d):
    a, b = map(int, input().split())
    scores.append([a, b])
    sum.append((i + 1) * 100 * a + b)

def ans(goal, p_num):
    if p_num <= 0:
        return float("INF")

    # 一番スコアの高い問題を必要な分か、あるいは限界まで解く。
    n = min(int(goal / (100 * p_num)), scores[p_num - 1][0])

    # できる限りまで高得点問題を解いたときの特典
    s = 100 * p_num * n

    # 全部解いたら、ボーナスを追加した点数を s とする
    if n == scores[p_num - 1][0]:
        s = sum[p_num - 1]

    # まだgoalに達していなかった場合、再帰関数に放り込む
    if goal > s:
        n += ans(goal - s, p_num - 1)

    return min(n, ans(goal, p_num - 1))

print(ans(g, d))

Submission status: Accepted

Solution code:
import sys
d,g=map(int,input().split())
p=[0]*d
c=[0]*d
for i in range(d):
    p[i],c[i]=map(int,input().split())
ans=float('inf')
for i in range(1<<d):
    su=0
    left=-1
    cnt=0
    for j in range(d):
        if (i>>j)&1:
            su+=p[j]*(j+1)*100
            su+=c[j]
            cnt+=p[j]
        else:
            left=max(left,j)
    if su<g:
        for j in range(p[left]):
            su+=100*(left+1)
            cnt+=1
            if su>=g:
                break
    if su>=g:
        ans=min(ans,cnt)
print(ans)

Submission status: Accepted

Solution code:
d, g = list(map(int, input().split(' ')))

pcd = [None] * d
for i in range(d):
    pcd[i] = list(map(int, input().split(' ')))


ans = float('inf')
for i in range(2 ** d):
    num = 0
    count = 0
    m = -1
    for j in range(d):
        if (i >> j) & 1:
            num += pcd[j][0] * 100 * (j + 1) + pcd[j][1]
            count += pcd[j][0]
        else:
            m = j
    if m != -1:
        k = 0
        while(k < pcd[m][0] and num < g):
            num += (m + 1) * 100
            k += 1
        count += k
    if num >= g:
        ans = min([ans, count])

print(ans)

Submission status: Accepted

Solution code:
from collections import deque
import itertools, math
d,g = list(map(int,input().split()))
pc = [list(map(int,input().split())) for _ in range(d)]
g /= 100

#ans = sum([pc[x][0] for x in range(d)])
ans = float('inf')
for bit in range(1<<d):
  cnt = 0
  point = 0
  pat = set(range(1,d+1))
  
  for i in range(d):
    if bit & (1<<i):
      point += pc[i][0]*(i+1) + pc[i][1]//100
      cnt += pc[i][0]
      pat.discard(i+1)
  
  if point < g:
      next = max(pat)
      n = min(pc[next-1][0], math.ceil((g - point)/(next)))
      cnt += n
      point += n*(next)
    
  if point >= g:
      #print(ans,cnt)
      ans = min(ans,cnt)


print(ans)

Submission status: Accepted

Solution code:
d,g=map(int,input().split())
l=[list(map(int,input().split())) for i in range(d)]
cnt=30000
for i in range(2**d):
    cntd=0
    div=i
    score=0
    allsolved=[False]*d
    for j in range(d)[::-1]:
        if div//(2**j):
            allsolved[j]=True
            cntd+=l[j][0]
            score+=100*(j+1)*l[j][0]+l[j][1]
        div%=(2**j)
    rem=max(0,g-score)
    for h in range(d)[::-1]:
        if allsolved[h]:continue
        if rem<=100*(h+1)*(l[h][0]-1):
            cntd+=(rem+100*(h+1)-1)//(100*(h+1))
            rem=0
            break
        else:
            cntd+=l[h][0]-1
            rem-=100*(h+1)*(l[h][0]-1)
    if rem<=0 and cntd < cnt:cnt=cntd
print(cnt)

Submission status: Accepted

Solution code:
if __name__ == "__main__":

    # 入力取得
    d, g = map(int, input().split())

    p = [0]*d
    c = [0]*d
    for i in range(d):
        p[i], c[i] = map(int, input().split())

    result = 99999999

    # 処理
    # ビット全探索(0:一問も解かない、1:全問解く)
    for i in range(1 << d):

        now_answer_count = 0
        now_point = 0

        # まず、全問解く問題を解いた場合の回答数と点数を取得。
        for j in range(d):
            # 全問解く場合
            # 数値 × 文字列 のパターンじゃない場合、判定条件は「i & 1 << j」でＯＫ。
            # この場合は数値 × list。
            if i & 1 << j:
                # 加算する
                # 回答数を加算
                now_answer_count += p[j]
                # 点数を加算
                now_point += p[j] * (j+1) * 100
                # コンプリートポイントを加算
                now_point += c[j]

        # print("--全問回答完了時--")
        # print(bin(i))
        # print("回答数:" + str(now_answer_count))
        # print("点数:" + str(now_point))

        # 2020/03/30 反省点
        # テストパターンb6だけ不正解。
        # 全ての問題に回答する場合の考慮が不足していた。
        # 以下のコードで対応する。
        if now_point >= g:
            result = min(result, now_answer_count)

        # 次に、途中まで回答する問題を回答した場合の検証。
        j = 0
        for j in range(d):

            # print("--一部回答シュミレーション--" + str(j))
            # 全問解く場合(何もしない)
            if i & 1 << j:
                pass
            # 一問も解かない場合
            # Ｘ問回答したらどうなるか？をシュミレーションする。
            else:
                for k in range(p[j] + 1):
                    # print("回答数:" + str(k))
                    # print("加算点数:" + str(100*(j+1)*k))
                    work_now_point = 100*(j+1)*k

                    # 点数が必要点に達した場合
                    if now_point + work_now_point >= g:
                        # print("点数が足りた:")
                        # print("点数が足りた:回答数：" + str(now_answer_count + k))
                        # 回答数を更新する。
                        result = min(result, now_answer_count + k)

    print(result)

Submission status: Accepted

Solution code:
D,G=map(int, input().split())
li = []
for i in range(D):
  li.append(list(map(int, input().split())))

min_n=10**9
n = 0
s=0
for ind in range(2**D):
  n=0
  s=0
  for j in range(D):
    if ind>>j & 1:
      s += (j+1)*100*li[j][0]+li[j][1]
      n+=li[j][0]
  # print(s)
  if s < G:
    for j in range(D-1,-1,-1):
      if ind>>j & 1 == 0:
        tmp = (G-s) / ((j+1)*100)
        if (G-s) % ((j+1)*100) != 0:
          tmp += 1
        if tmp > 0:
          if tmp>=li[j][0]:
            tmp=li[j][0]-1
          s += (j+1)*100*tmp
          n+= tmp
      if s >= G:
        # print(tmp)
        break
  if s >= G:
    if n<min_n:
      # print(ind)
      min_n=n

print(int(min_n))

Submission status: Accepted

Solution code:
import sys

import bisect

# from collections import Counter, deque, defaultdict
# import copy
# from heapq import heappush, heappop, heapify
# from fractions import gcd

# import itertools

# from operator import attrgetter, itemgetter
# import math

# import numpy as np

readline = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)


def main():
    d, g = list(map(int, readline().split()))
    pc = [list(map(int, readline().split())) for _ in range(d)]

    ans = INF

    for bit in range(1 << d):
        solve = 0
        score = 0
        for i in range(d):
            point = (i + 1) * 100
            if (bit >> i) & 1:
                solve += pc[i][0]
                comp = pc[i][1]
                score += (point * pc[i][0] + comp)

        rem = g - score
        if rem > 0:
            for i in range(d - 1, -1, -1):
                point = (i + 1) * 100
                num = pc[i][0] - 1
                if not ((bit >> i) & 1):
                    if rem <= num * point:
                        solve += (rem + point - 1) // point
                        rem = 0
                        break
                    else:
                        solve += num
                        rem -= num * point

        if rem <= 0:
            ans = min(ans, solve)

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
d,g=map(int,input().split())
P=[0]*d
C=[0]*d
for i in range(d):
  P[i],C[i]=map(int,input().split())
dp=[[-10**10]*(sum(P)+111) for i in range(d+1)]
for i in range(sum(P)+1):
  dp[0][i]=0
for i in range(1,d+1):
  dp[i][0]=0
for i in range(1,d+1):
  for j in range(1,(sum(P)+1)):
    dp[i][j]=max(max(dp[i-1][j-k]+i*100*k for k in range(P[i-1])),dp[i-1][j-P[i-1]]+i*100*P[i-1]+C[i-1],dp[i][j-1])
i=-1
while dp[d][i]<g:
  i=i+1
print(i)

Submission status: Accepted

Solution code:
D,G = map(int,input().split())
p = [0]*D
c = [0]*D
for i in range(D):
    p[i], c[i] = map(int,input().split())

ans = float('inf')

for bit in range(1 << D):
    temp_score = 0
    solved_num = 0
    uncompleted_idx = -1
    for i in range(D):
        if (bit & (1<<i)):
            temp_score += p[i]*100*(i+1) + c[i] #コンプリートする得点帯
            solved_num += p[i]
        else:
            uncompleted_idx = max(uncompleted_idx,i)


    if G <= temp_score:
        ans = min(ans,solved_num)
        continue
    # 半端に解く問題（未コンプのうち最も配点の高い問題）をシミュレーション
    if uncompleted_idx == -1:
        continue

    for j in range(p[uncompleted_idx]):
        temp_score += 100*(uncompleted_idx+1)
        solved_num += 1
        if G <= temp_score:
            ans = min(ans,solved_num)
            break
print(ans)

Submission status: Accepted

Solution code:
import math

D,G = map(int,input().split())
pc = [list(map(int,input().split()))for _ in range(D)]

minimam=float('INF')

digit = "0"+str(D)+"b"

for i in range(2**D):
  pattern = str(format(i,digit))
  #この完答パターンのときの完答に伴う問題数と得点を算出する
  point = 0
  count = 0
  for j in range(D):
    if pattern[j]=="1":
      count += pc[j][0]
      point += pc[j][0]*100*(j+1)+pc[j][1]
  #ポイントがGに未達の場合、残りの問題を解いてみて、Gに到達するか検証。
  #到達する場合でなおかつ問題数が最小であれば記録する。
  last0 = pattern.rfind("0")
  r = G -point
  if r > 0:
    if last0==-1:
      continue
    tmp = math.ceil(r/(100*(last0+1)))
    if tmp < pc[last0][0]:
      minimam = min(minimam,tmp+count)
  else:
    minimam = min(minimam,count)

print(minimam)

Submission status: Accepted

Solution code:
def main():
    D,G = map(int,input().split())
    score = []
    for i in range(D):
        p,c = map(int,input().split())
        score.append((p,c))
    ans = 2**60
    for mask in range(2**D):
        s = 0
        num = 0
        rest = -1
        for i in range(D):
            if (mask >> i&1):
                s += 100*(i+1)*score[i][0]+score[i][1]
                num += score[i][0]
            else:
                rest = i
        if s < G:
            s1 = 100*(rest+1)
            need = (G-s+s1-1)//s1
            if need >= score[rest][0]:
                continue
            num += need
        ans = min(ans,num)

    print(ans)
if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
D, G = [int(n) for n in input().split(' ')]

p = []
c = []
for _ in range(D):
    temp = [int(n) for n in input().split(' ')]
    p += [temp[0]]
    c += [temp[1]]

ans = 10**9
for flag in range(1<<D):
    score = 0
    cnt = 0
    
    for i in range(D):  # コンプリートボーナス
        if flag & 1<<i:
            score += c[i] + 100*(i+1)*p[i]
            cnt += p[i]
            
    if score >= G:
        if cnt < ans:
            ans = cnt
    
    for i in range(D, 0, -1):
        if flag & 1<<(i-1):
            continue    
        for n in range(p[i-1]):
            score += 100*i
            cnt += 1
            if cnt == 3:
                pass
            if score >= G:
                if cnt < ans:
                    ans = cnt

print(ans)

Submission status: Accepted

Solution code:
#!python3

INF = -(10 ** 15)

# input
D, G = list(map(int, input().split()))
p, c = [None] * D, [None] * D
for i in range(D):
    p[i], c[i] = list(map(int, input().split()))


def main():
    dp = [[INF] * 1001 for _ in range(D + 1)]
    dp[0][0] = 0
    for i in range(1, D + 1):
        dp[i][0] = 0
        for j in range(1, 1001):
            for k in range(p[i-1]):
                if k > j:
                    break
                dp[i][j] = max(dp[i][j], dp[i-1][j-k] + 100 * i * k)
            if p[i-1] <= j:
                dp[i][j] = max(dp[i][j], dp[i-1][j-p[i-1]] + 100 * i * p[i-1] + c[i-1])

    for j in range(1, 1001):
        if dp[-1][j] >= G:
            print(j)
            return


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
d, g = map(int, input().split())
pc = [list(map(int, input().split())) for _ in range(d)]
    
def dfs(i, sum, count, nokori):
    global ans
    if i == d:
        if sum < g:
            use = max(nokori)
            n = min(pc[use-1][0], -(-(g-sum)//(use*100)))
            count += n
            sum += n * use * 100
        if sum >= g:
            ans = min(ans, count)
    else:
        dfs(i+1, sum, count, nokori)
        dfs(i+1, sum+pc[i][0]*(i+1)*100+pc[i][1], count+pc[i][0], nokori-{i+1})
ans = float("inf")
dfs(0, 0, 0, set(range(1, d+1)))
print(ans)

Submission status: Accepted

Solution code:
# この問題はbit全探索で解く
D, G = map(int, input().split())  # 1~Dのスコア帯, 目標の点数G
# 問題を受け取る
problems = [list(map(int, input().split())) for _ in range(D)]  # pi問存在している, ボーナスci点

# 状態を列挙する
all_status = []
for i in range(1 << D):
    tmp = []
    for j in range(D):
        if (i >> j) & 1:
            tmp.append(1)
        else:
            tmp.append(0)
    all_status.append(tmp)
# 状態の列挙が終わった
ans = float('inf')
for status in all_status:
    # status中の1が立っている部分の問題を全て解く
    score = 0
    solve_count = 0
    for i in range(len(status)):
        if status[i] == 1:
            # i番目の問題を全て解く
            score += (i+1)*100*problems[i][0] + problems[i][1]
            solve_count += problems[i][0]
    # 対象の問題を全部解き終えた
    if score >= G:
        ans = min(ans, solve_count)
    else:
        # 足りない問題を解く
        for i in reversed(range(len(status))):
            if status[i] == 0:  # 解いていない問題の中で一番ポイントが高いものを解く
                for j in range(problems[i][0]):  # 1問ずつ解く
                    score += (i+1)*100
                    solve_count += 1
                    if score >= G:
                        ans = min(ans, solve_count)
                        break
                break
print(ans)

Submission status: Accepted

Solution code:
import math

D, G = map(int, input().split())
lst = [list(map(int, input().split())) for _ in range(D)]

digit = '0' + str(D) + 'b'
ans = float('INF')
for i in range(2**D):
    bit = list(str(format(i, digit)))
    p = 0
    cnt = 0
    last = -1
    for j in range(D):
        if bit[j] == '1':
            p += lst[j][1] + lst[j][0]*100*(j+1)
            cnt += lst[j][0]
        else:
            last = j
    r = G - p
    if r > 0 and last > -1:
        tmp = math.ceil(r/(100*(last+1)))
        if tmp < lst[last][0]:
            cnt += tmp
            ans = min(ans, cnt)
    elif r <= 0:
        ans = min(ans, cnt)

print(ans)

Submission status: Accepted

Solution code:
import math

D,G = map(int,input().split())
pc = [list(map(int,input().split()))for i in range(D)]

digit = "0"+str(D)+"b"
ans = float('INF')
for i in range(2**D):
  pattern = list(str(format(i,digit)))
  point = 0
  count = 0
  last0 = -1
  for j in range(D):
    if pattern[j] =="1":
      point += pc[j][1]+pc[j][0]*100*(j+1)
      count += pc[j][0]
    else:
      last0 = j
  r = G - point
  if r > 0 and last0 > -1:
    tmp = math.ceil(r/(100*(last0+1)))
    if tmp < pc[last0][0]:
      count += tmp
      ans = min(ans,count)
  elif r <= 0:
    ans = min(ans,count)
  
print(ans)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline

d, g = [int(x) for x in input().split()]
pc = [[int(x) for x in input().split()] for _ in range(d)]

ans = float("inf")

for i in range(2 ** d):
    s = set() # コンプリートボーナスをもらう
    for j in range(d):
        if (i >> j) & 1:
            s.add(j)
    cnt = 0
    total = 0
    for k in s:
        cnt += pc[k][0]
        total += (k + 1)*pc[k][0]*100 + pc[k][1]
    if total >= g:
        ans = min(ans, cnt)
        continue
    for l in range(d - 1, -1, -1):
        flag = 0
        if l in s:
            continue
        for m in range(1, pc[l][0]):
            total += (l + 1) * 100
            cnt += 1
            if total >= g:
                flag = 1
                break
        if flag:
            break
    if total >= g:
        ans = min(ans, cnt)

print(ans)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline

d, g = [int(x) for x in input().split()]
pc = [[int(x) for x in input().split()] for _ in range(d)]

ans = float("inf")

for i in range(2 ** d):
    i_bin = bin(i)[2:].zfill(d)
    s = set() # コンプリートボーナスをもらう
    for j in range(len(i_bin)):
        if i_bin[j] == "1":
            s.add(j)
    cnt = 0
    total = 0
    for k in s:
        cnt += pc[k][0]
        total += (k + 1)*pc[k][0]*100 + pc[k][1]
    if total >= g:
        ans = min(ans, cnt)
        continue
    for l in range(d - 1, -1, -1):
        flag = 0
        if l in s:
            continue
        for m in range(1, pc[l][0]):
            total += (l + 1) * 100
            cnt += 1
            if total >= g:
                flag = 1
                break
        if flag:
            break
    if total >= g:
        ans = min(ans, cnt)

print(ans)

Submission status: Accepted

Solution code:
def main():
    d,g = (int(x) for x in input().split())
    g //= 100
    pc = []
    for _ in range(d):
        p,c = (int(x) for x in input().split())
        pc.append((p,c // 100))

    ans = 10**10
    for i in range(1 << d):
        cnt, total = 0, 0
        max = -1
        for j in range(d):
            if (i >> j) & 1:
                p,c = pc[j]
                cnt += p
                total += c + p * (j + 1)
            else:
                max = j + 1

        if  total < g:
            rem = (g - total + max - 1) // max
            if rem >= pc[max - 1][0]:
                continue
            cnt += rem

        ans = min(ans, cnt)

    print(ans)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from itertools import product
d, g = list(map(int, input().split()))
pl = [0] * d
cl = [0] * d
for i in range(d):
    pl[i], cl[i] = map(int, input().split())
INF = float("inf")
ans = INF
for bit in product([0, 1], repeat=d):
    anss = 0
    score = 0
    I = 0
    for i in range(d):
        if bit[i] == 0:
            I = i
        else:
            score += pl[i]*100*(i+1)
            score += cl[i]
            anss += pl[i]

    for _ in range(pl[I]):
        if score >= g:
            ans = min(ans, anss)
            break
        else:
            score += (I+1)*100
            anss += 1
    if score >= g:
        ans = min(ans, anss)

print(ans)

Submission status: Accepted

Solution code:
d,g = map(int,input().split())
li = []
ans = []
for i in range(d):
  pc = list(map(int,input().split()))
  li.append(pc)
for bit in range(1<<d):
  problem = 0
  pt = 0
  cnt = 0
  for i in range(d):
    if ((bit >> i) & 1):
      problem += li[i][0]
      pt += 100*(i+1)*li[i][0] + li[i][1]
  if pt >= g:
    ans.append(problem)
  else:
    for j in range(d-1,-1,-1):
      if ((bit >> j) & 1) == 0:
        for k in range(li[j][0]):
          if pt >= g:
            break
          cnt += 1
          problem += 1
          pt += 100*(j+1)
    ans.append(problem)
          
print(min(ans))

Submission status: Accepted

Solution code:
d,g = map(int,input().split())
P, C = [], []
probs = set([i for i in range(d)])
for _ in range(d):
    p,c = map(int,input().split())
    P.append(p)
    C.append(c)
res = float('inf')
for i in range(2**d):
    tmp = []
    score = 0
    cnt = 0
    for j in range(d):
        if ((i>>j)&1):
            tmp.append(j)
    for k in tmp:
        score += (k+1)*100*P[k] + C[k]
        cnt += P[k]    
    if score >= g:
        res = min(res, cnt)
    else:
        x = list(probs - set(tmp))
        x.sort(reverse=True)
        for x_ in x:
            for _ in range(P[x_]):
                score += (x_+1)*100
                cnt += 1
                if score >= g:
                    res = min(res, cnt)
                    break
print(res)

Submission status: Accepted

Solution code:
import math
D, G = list(map(int, input().split()))

arr = []
for i in range(1, D + 1):
    p, c = list(map(int, input().split()))
    arr.append([i * 100, p, c])

min_n_solved_problems = 1e100
for i in range(2 ** D):
    solved_flag = [False] * D
    score = 0
    n_solved_problems = 0
    for j in range(D):
        if ((i >> j) & 1):
            solved_flag[j] = True
            point, num, bonus = arr[j]
            score += point * num + bonus
            n_solved_problems += num
        else:
            biggest_unsolved_ind = j

    if score < G:
        point, num, bonus = arr[biggest_unsolved_ind]
        n_add = math.ceil((G - score) / arr[biggest_unsolved_ind][0])
        if n_add > num - 1: # If we use num - 1 of the biggest one and still cannot reach, it's not the case
            continue
        score += n_add * point
        n_solved_problems += n_add

    if min_n_solved_problems > n_solved_problems:
        min_n_solved_problems = n_solved_problems
print(min_n_solved_problems)

Submission status: Accepted

Solution code:
import math

D, G = list(map(int, input().split()))
pc = [list(map(int, input().split())) for _ in range(D)]

digit = '0'+str(D)+'b'
minimam = float("inf")

for i in range(2**D):
    pattern = list(str(format(i, digit)))
    point = 0
    count = 0
    tmp = -1
    for j in range(D):
        if pattern[j] == "1":
            p = pc[j][0]
            c = pc[j][1]
            point += p*100*(j+1)+c
            count += p
        else:
            tmp = j
    r = G - point
    if r > 0 and tmp > -1:
        countTmp = math.ceil(r/(100*(tmp+1)))
        # count += countTmp
        if countTmp < pc[tmp][0]:
            count += countTmp
        else:
            continue
    minimam = min(count, minimam)

print(minimam)

Submission status: Accepted

Solution code:
import math

D,G = map(int,input().split())
pc = [list(map(int,input().split())) for i in range(D)]

digit = '0'+str(D)+'b'
rangeEnd = 2**D
minimam = float('INF')
for i in range(rangeEnd):#完答パターンごとのループ
  pattern = list(str(format(i,digit)))
  point = 0 #獲得ポイント初期化
  count = 0 #initialize the problem counter
  tmp = -1
  for j in range(D):
    if pattern[j]=="1":
      p = pc[j][0]
      c = pc[j][1]
      point += p*100*(j+1)+c
      count += p
    else:
      tmp = j #store the maximam problem number remaining
  r = G - point
  if r > 0 and tmp >- 1:#there are neccery points still.
    countTmp = math.ceil(r/(100*(tmp+1)))
    if countTmp < pc[tmp][0]:
      count += countTmp
    else:
      continue
  minimam = min(count, minimam)
  
print(minimam)

Submission status: Accepted

Solution code:
import math

D,G=map(int,input().split())
pc = [list(map(int,input().split()))for i in range(D)]
digits = '0'+str(D)+'b'

minpn = float('INF')

for i in range(2**D):
  maxIndex = -1
  s = list(format(i, digits))
  point = 0
  pcounter = 0
  for j in range(D):
    if s[j]=='1':
      #increce the c and (the p)*100*(j+1)
      point += pc[j][1]
      point += pc[j][0]*100*(j+1)
      pcounter += pc[j][0]
    else:
      maxIndex=j
  remainingP = G - point
  if  remainingP <= 0:
    minpn = min(pcounter, minpn)
  else:
    if 100*(maxIndex+1)*(pc[maxIndex][0]-1)>=remainingP:
      pcounter+=math.ceil(remainingP/(100*(maxIndex+1)))
      minpn = min(pcounter, minpn)

print(minpn)

Submission status: Accepted

Solution code:
def LI():
	return [ int(s) for s in input().split() ]
D,G = LI()

problems = [LI() for _ in range(D)]

cnt_pnum = 0
cnt_score = 0
min_pnum = 10000000

for i in range(2**D):
  bonus = []
  cnt_pnum = 0
  cnt_score = 0
  for j in range(D):
    if i >> j & 1:
      bonus.append(j)
      cnt_score+=100*(j+1)*problems[j][0] + problems[j][1]
      cnt_pnum += problems[j][0]
      
  for j in reversed(range(D)):
    if not (i >> j & 1):
      for k in range(problems[j][0]):
        if cnt_score >= G:
          break
        cnt_score+=100*(j+1)
        cnt_pnum += 1
    if cnt_score >= G:
      if cnt_pnum < min_pnum:
      	min_pnum = cnt_pnum
      break
    
print(min_pnum)

Submission status: Accepted

Solution code:
import sys
def input(): return sys.stdin.readline().rstrip()

def main():
    D, G = map(int, input().split())
    pc = [tuple(map(int, input().split())) for _ in range(D)]

    ans = 10 ** 9
    for i in range(2 ** D):
        sum_v = 0
        cnt = 0
        for j, (p, c) in enumerate(pc):
            if i & 1 << j:
                sum_v += (j+1) * 100 * p + c
                cnt += p
        if sum_v >= G:
            if cnt < ans:
                ans = cnt
            continue
        for j, (p, c) in enumerate(pc[::-1]):
            k = D - j
            if (i & 1 << k-1) == 0:
                for _ in range(p):
                    sum_v += k * 100
                    cnt += 1
                    if sum_v >= G:
                        if cnt < ans:
                            ans = cnt
                        break
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
def input(): return sys.stdin.readline().rstrip()

def main():
    D, G = map(int, input().split())
    pc = [tuple(map(int, input().split())) for _ in range(D)]

    ans = 10 ** 9
    for i in range(2 ** D):
        sum_v = 0
        cnt = 0
        for j, (p, c) in enumerate(pc):
            if i & 1 << j:
                sum_v += (j+1) * 100 * p + c
                cnt += p
        if sum_v >= G:
            if cnt < ans:
                ans = cnt
            continue
        for j, (p, c) in enumerate(pc[::-1]):
            k = D - j
            if not (i & 1 << k-1):
                for _ in range(p):
                    sum_v += k * 100
                    cnt += 1
                    if sum_v >= G:
                        if cnt < ans:
                            ans = cnt
                        break
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
# -*- coding: utf-8 -*-


def main():
    D, G = map(int, input().split())

    PC = [list(map(int, input().split())) for _ in range(D)]

    result = 0
    new_dp = [0] * 1001

    for d, pc in enumerate(PC, 1):
        dp = new_dp[:]

        p, c = pc
        result += p

        s = {x: x * 100 * d for x in range(p)}
        s[p] = p * 100 * d + c

        for i in range(1, result + 1):
            for j in range(0, i + 1):
                if i - j > p:
                    continue
                else:
                    new_dp[i] = max(new_dp[i], dp[j] + s[i - j])

    for i, a in enumerate(new_dp):
        if a >= G:
            print(i)
            exit()


if __name__ == "__main__":
    main()