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:
def q3():
    import itertools
    l1 = input().split()
    D = int(l1[0])  # 問題数
    G = int(l1[1])  # 総合スコア

    P = []  # 各スコアごとの問題数
    C = []  # コンプリートボーナス
    for i in range(D):
        l = input().split()
        P.append(int(l[0]))
        C.append(int(l[1]))

    # コンプリートするかしないかの組み合わせ作成 2^D個, する:1 しない:0
    for i in range(D):
        li = list(itertools.product([1, 0], repeat=D))

    ans = float('INF')
    for e in li:
        tmp_sum = 0  # 総得点
        tmp_ans = 0  # 総正解数

        # コンプリートした問題だけを先に足しておく
        for i, flag in enumerate(e):
            tmp_sum += (P[i]*(i+1)*100 + C[i]) * flag
            tmp_ans += P[i]*flag

        # print(tmp_sum, tmp_ans, e)

        # コンプリートボーナスだけで目標点数Gを超えているか？
        if tmp_sum >= G:
            ans = min(ans, tmp_ans)  # ans更新
            continue

        for i in range(D-1, -1, -1):
            if e[i] == 1:
                continue
            for _ in range(0, P[i]):
                tmp_sum += (i+1)*100
                tmp_ans += 1
                # print(i, tmp_sum)

                if tmp_sum >= G:
                    ans = min(ans, tmp_ans)  # ans更新
                    break
            if tmp_sum >= G:
                break

    return ans

if __name__ == "__main__":
    print(q3())

Submission status: Accepted

Solution code:
import itertools
D, G = map(int, input().split())
pc = [list(map(int, input().split())) for _ in range(D)]
bit = itertools.product([0, 1], repeat=D)
ans = 1000
for bi in bit:
    cnt = 0
    score = 0
    nokori = []
    for i in range(D):
        if bi[i] == 0:
            nokori.append([pc[i][0], (i+1)*100])
            continue
        score += pc[i][1] + 100*(i+1)*(pc[i][0])
        cnt += pc[i][0]
    if score >= G:
        ans = min(ans, cnt)
    else:
        for num, point in reversed(nokori):
            for j in range(1, num):
                cnt += 1
                score += point
                if score >= G:
                    ans = min(ans, cnt)
                    break
            else:
                continue
            break
print(ans)

Submission status: Accepted

Solution code:
'''

1 <= D <= 10
1 ≤  pi≤100
100≤ ci≤10**6
100≤ G

＜回答・解説より＞
以下のような選択のみを考慮しても最適解はそれらの選択に含まれます。
• 中途半端に解く配点は 1 種類以下であり、それ以外の配点は完全に解くかまったく解かない。
• 中途半端に解く配点があるなら、それは完全に解く配点以外の配点の中で最も高い配点である。

このような選択をすべて列挙するには、D 種類の配点それぞれに対してその配点を完全に解くか否かを決定し、
必要であれば残りの配点のうち最も高いものを中途半端に解く配点とすればよいです
（中途半端に解く配点の問題を 1 問除きすべて解いても目標点に達しない場合は、完全に解く配点の選択が不適切であったとして無視します）。

↓
考え方
「ある点数帯の問題を全部解く」を全パターン試す。
・目標点数を満たす、最小の問題数（の組み合わせ）をAとする
・Aの次に目標点数に近い（が満たさない、組み合わせ）をBとする。
　→Bに、「完全に解く配点以外の配点の中で最も高い配点」の問題を条件を満たすまで解いて問題数を確認する。B'とする
　　→AとB'のうち、解く問題数が少ないほうを回答とする。

'''
# from collections import deque # キュー、スタックに利用
# import math # 数学的計算に利用
# import numpy as np # 行列計算などに利用

# sys.stdin.readline() # 標準入力の高速化に利用
import sys
input = sys.stdin.readline

inf = float('inf')
is_debug = False

d,g = map(int, input().split())

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

def main():
    '''メイン処理'''
    # 各点数帯の問題を全て解くor全て解かない　の組み合わせパターンは、2**d通り
    points_list = []
    for i in range(2**d):
        # 全て解くフラグのリスト
        solve_list = [0] * d
        # n桁の2進数文字列を生成
        bin_str = bin(i)[2:].zfill(d)
        # 2進数で1の立っている桁をフラグとみなし、全て解くフラグを1へ書き換え
        for j in range(d):
            if bin_str[j] == '1':
                solve_list[j] = 1

        solve_num = 0
        points = 0
        for k in range(d):
            if solve_list[k] == 1:
                q_num, bonus = M[k]
                solve_num += q_num
                points += (q_num*(k+1)*100) + bonus
        points_list.append([solve_num, points, solve_list])
    
    if is_debug:
        print(sorted(points_list))
    
    min_solve_num = inf
    for index, [solve_num, points, solve_list] in enumerate(sorted(points_list, reverse=True)):
        next_loop = False
        if points >= g and solve_num < min_solve_num:
            # 目標点数を満たす、最小の問題数（の組み合わせ）をAとする
            a_ans = [solve_num, points]
            min_solve_num = solve_num
        elif points < g and solve_num < min_solve_num:
            ## Aの次に目標点数に近い（が満たさない、組み合わせ）をBとし、追加で解いて目標点数を満たせばmin_solve_numを更新
            # 解いていない問題の中で、得点が高い順に解いて、目標点を超えた時点のsolve_numをここまでのmin_solve_numと比較する
            for i in range(len(solve_list)-1,-1,-1):
                if solve_list[i] == 0:
                    q_num = M[i][0]
                    for _ in range(q_num):
                        points += (i+1)*100
                        solve_num += 1
                        if solve_num >= min_solve_num:
                            next_loop = True
                        elif points >= g and solve_num < min_solve_num:
                            min_solve_num = solve_num # 条件を満たす問題数があったら、ここまでの最小値を更新
                        
                        if next_loop:
                            break
                if next_loop:
                    break

    if is_debug:
        print(a_ans)
    print(min_solve_num)


if __name__ == "__main__":
    # ファイル実行時に、main()関数を実行
    main()

Submission status: Accepted

Solution code:
d,g=map(int,input().split())
pc=[list(map(int,input().split())) for i in range(d)]
ans=float("inf")
tmp=0
for i in range(2**d):
    count=0
    s=0
    nokori=set(range(1,d+1))
    for k in range(d):
        if i &(1<<k):
            s+=pc[k][0]*(k+1)*100+pc[k][1]
            count+=pc[k][0]
            nokori.discard(k+1)
    if s<g:
        use=max(nokori)
        n=min(pc[use-1][0],-(-(g-s)//(use*100)))
        count+=n
        s+=n*use*100
    if s>=g:
        ans=min(ans,count)
print(ans)

Submission status: Accepted

Solution code:
D, G = map(int,input().split())
p,C = [],[]
for i in range(D):
    p_,c_ = map(int,input().split())
    p.append(p_)
    C.append(c_)
ans = float('inf')
 
for i in range(2**D):
    s, k = 0, 0
 
    for j in range(D):
        if (i>>j) & 1:
            s += p[j]*(j+1)*100 + C[j] 
            k += p[j]
    if s >= G:
        ans = min(ans, k)
    else:
        for l in range(D-1, -1, -1):
            if (i>>l) & 1 == 0: 
                if s+(l+1)*100*p[l]<G:
                    break
                else:
                    rem = G - s
                    k += -(-rem//((l+1)*100))
                    ans = min(ans, k)
print(ans)

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):
  sum=0
  count=0
  nokori=set(range(1,d+1))
  for i in range(d):
    if bit&(1<<i):
      sum += p[i]*100*(i+1)+c[i]
      count+= p[i]
      nokori.discard(i + 1)
  if sum<g:
    a=g-sum
    num=max(nokori)
    n=min(p[num-1],-(-a//(num*100)))
    count+=n
    sum+=n*num*100
  if sum>=g:
    ans=min(ans,count)
    
print(ans)

Submission status: Accepted

Solution code:
def main():
    D,G = [int(x) for x in input().split()]
    min_cnt = 0
    bonus = []
    for i in range(D):
        p,c = [int(x) for x in input().split()]
        bonus.append((p,c))
        min_cnt += p
    # print(bonus)
    # print(min_cnt)

    for bit in range(1<<D):
        score = 0
        cnt = 0
        for i,(p,c) in enumerate(bonus):
            if (1<<i) & bit:
                score += 100*(i+1)*p+c
                cnt += p
        # print(bin(bit),i,score,cnt,min_cnt)
        if score >= G:
            min_cnt = min(min_cnt, cnt)
        else:
            for i in reversed(range(0,D)):
                if (1<<i) & bit:
                    continue
                pi,ci = bonus[i]
                for j in range(pi-1):
                    score += 100*(i+1)
                    cnt += 1
                    # print(bin(bit),i,j,p,c,score,cnt,min_cnt)
                    if score >= G:
                        # print('break')
                        min_cnt = min(min_cnt, cnt)
                        break
    print(min_cnt)

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)]
ans = float("inf")

for bit in range(1<<d):
  sum=0
  count=0
  nokori=set(range(1,d+1))
  for i in range(d):
    if bit&(1<<i):
      sum += pc[i][0]*100*(i+1)+pc[i][1]
      count+= pc[i][0]
      nokori.discard(i + 1)
  if sum<g:
    a=g-sum
    num=max(nokori)
    n=min(pc[num-1][0],-(-a//(num*100)))
    count+=n
    sum+=n*num*100
  if sum>=g:
    ans=min(ans,count)
print(ans)

Submission status: Accepted

Solution code:
d, g = map(int, input().split())
A, B = [], []
for _ in range(d):
    a, b = map(int, input().split())
    A.append(a)
    B.append(b)
ans = float('inf')

for i in range(2**d):
    s, k = 0, 0 #s:得点, k:解いた問題数

    for j in range(d):
        if (i>>j)&1:
            s+=A[j]*(j+1)*100 + B[j] #pj+1問全て解く
            k+=A[j] #解いた問題数
    if s >= g:
        ans = min(ans, k)
    else:
        for l in range(d-1, -1, -1):
            if (i>>l)&1 == 0: #これまでにまだ解いていない問題
                if s+(l+1)*100*A[l]<g: #全部解いても超えない
                    s+=(l+1)*100*A[l]
                    k+=A[l]
                else:
                    rem = g-s #目標点までの残りの点数
                    k += -(-rem//(l+1)//100)
                    ans = min(ans, k)
print(ans)

Submission status: Accepted

Solution code:
d, g = map(int, input().split())
pc_ls = []
for i in range(d):
    p, c = map(int, input().split())
    pc_ls.append([p, c])

ptns = []
for i in range(2 ** d):
    ptn = []
    for j in range(d):
        if ((i >> j) & 1):
            ptn.append(j)
    ptns.append(ptn)

ret = 10 ** 10

for item in ptns:
    cnt = 0
    pnt = 0
    for val in item:
        cnt += pc_ls[val][0]
        pnt += (100 * (val + 1)) * pc_ls[val][0] + pc_ls[val][1]
    left = g - pnt
    if left <= 0:
        ret = min(ret, cnt)
    else:
        for i in range(1, d + 1):
            if (d - i) in item:
                continue
            else:
                max_val = (100 * (d - i + 1)) * pc_ls[-i][0]
                if max_val < left:
                    cnt += pc_ls[-i][0]
                    left -= max_val
                else:
                    cnt += (left + 100 * (d - i + 1) -
                            1) // (100 * (d - i + 1))
                    break
        ret = min(ret, cnt)

print(ret)

Submission status: Accepted

Solution code:
from math import ceil

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

c_list = []
ans = 0
for i in range(d):
    p, c = [int(x) for x in input().split()]
    c_list.append((100 * (i + 1) * p + c, p))
    ans += p
c_list = list(reversed(c_list))

for i in range(2 ** d):
    s = 0
    temp_ans = 0
    flag = True
    for j in range(d):
        temp = (i >> j) & 1
        if temp == 1:
            s += c_list[j][0]
            temp_ans += c_list[j][1]
            if s >= g:
                break
        elif flag:
            k = j
            flag = False
    else:
        temp_s = (d - k) * 100
        temp = ceil((g - s) / temp_s)
        if  temp < c_list[k][1]:
            s += temp_s * temp
            temp_ans += temp
    if s >= g and temp_ans < ans:
        ans = temp_ans
print(ans)

Submission status: Accepted

Solution code:
d , g = map(int, input().split())
pc = [list(map(int, input().split()))for i in range(d)]
x=[]
y=[0]*d
ac=[0]*d
for i in range(d):
    ac[i]=pc[i][0]*(i+1)*100+pc[i][1]

def dfs(n,m,y,now):
    if now==n:
        z=y.copy()
        x.append(z)
        return
    for i in range(m):
        y[now]=i
        dfs(n,m,y,now+1)
dfs(d,3,y,0)
mi = 1000
for i in x:
    sum = 0
    cost = 0
    stock = []
    sum2 = 0
    cost2 = 0
    for j in range(d):
        if i[j]==1:
            sum+=ac[j]
            cost+=pc[j][0]
            sum2+=ac[j]
            cost2+=pc[j][0]
        if i[j]==2:
            stock+=[(j+1)*100]*pc[j][0]
            sum2+=pc[j][0]*(j+1)*100
            cost2+=pc[j][0]
    if sum2<g:
        continue
    stock.sort()
    if abs(sum2-g)>abs(sum-g):
        while sum<g and stock:
            sum+=stock.pop()
            cost+=1
        if sum>=g:
            mi=min(mi,cost)
    else:
        while sum2>g and stock:
            sum2-=stock.pop()
            cost2-=1
        cost+=1
        mi=min(mi,cost2)

print(mi)

Submission status: Accepted

Solution code:
d,g=map(int,input().split())
A,B=[],[]
for i in range(d):
    a,b=map(int,input().split())
    A.append(a)
    B.append(b)
ans=float("inf")
for i in range(2**d):
    s,k=0,0
    for j in range(d):
        if (i>>j)&1:
            s+=A[j]*(j+1)*100+B[j]
            k+=A[j]
    if s>=g:
        ans=min(ans,k)  
    else:
        for l in range(d-1,-1,-1):
            if (i>>l)&1==0:
                if s+(l+1)*100*A[l]<g:
                    s+=(l+1)*100*A[l]
                    k+=A[l]
                else:
                    rem=g-s
                    k+=-(-rem//(l+1)//100)
                    ans=min(ans,k)
print(ans)

Submission status: Accepted

Solution code:
import math

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())

point =[i*100 for i in range(1, d+1)]
ans = float("inf")

for i in range(1<<d):
  score = 0
  cnt = 0
  for j in range(d):
    if i>>j &1:
      cnt += p[j]
      score += point[j]*p[j] + c[j]
  if score >= g:
    ans = min(ans, cnt)
    continue
  for j in range(d)[::-1]:
    if i >> j &1:
      continue
    x = min(math.ceil((g-score)/point[j]), p[j]-1)
    cnt += x
    score += point[j]*x
    if score >= g:
      ans =min(ans, cnt)
      break
print(ans)

Submission status: Accepted

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

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

res = float('inf')

for i in range(2**D):
  score, solved = 0, 0
  all_solved = []

  for j in range(D):
    if (i>>j)&1:
      score += 100*(j+1)*p[j] + c[j]
      solved += p[j]
      all_solved.append(j)
      if score >= G: break

  if score < G:
    for k in range(D-1, -1, -1):
      if k not in all_solved:
        for num in range(p[k]):
          score += 100*(k+1)
          solved += 1
          if score >= G: break
        if score >= G: break
        score += c[k]

  if score >= G:
    res = min(res, solved)

print(res)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-

D,G = list(map(int, input().rstrip().split()))
pc_list = [list(map(int, input().rstrip().split())) for i in range(D)]
#-----

bit = 1 << D
min_cnt = 10*100

for b in range(bit):
    score = 0
    cnt = 0
    
    for i in range(D):
        if b & (1 << i):
            p = pc_list[i][0]
            c = pc_list[i][1]
            
            score += p * (100*(i+1)) + c
            cnt += p
    
    if score >= G:
        min_cnt = min(min_cnt, cnt)
    
    else:
        flag = False
        
        for i in reversed(range(len(pc_list))):
            if flag:
                break
            
            if b & (1 << i):
                continue
            
            p = pc_list[i][0]
            
            for j in range(p-1):
                score += 100*(i+1)
                cnt += 1
                
                if score >= G:
                    min_cnt = min(min_cnt, cnt)
                    flag = True
                    break

print(min_cnt)

Submission status: Accepted

Solution code:
import math
a,b=map(int,input().split())
List=[list(map(int,input().split())) for i in range(a)]
ans=10000000000000
for i in range(2**a):
  s=0
  c=0
  t=True
  x=0
  y=0
  for j in range(a):
    if (i>>j) & 1:
      s+=(a-j)*100*List[a-1-j][0]+List[a-1-j][1]
      c+=List[a-1-j][0]
    else:
      if t:
        x=(a-j)*100
        y=List[a-1-j][0]
        t=False
  if b<=s:
    if ans>c:
      ans=c
  else:
    if math.ceil((b-s)/x)<=y:
      c+=math.ceil((b-s)/x)
      if ans>c:
        ans=c
print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
import math

def solve(D: int, G: int, p: "List[int]", c: "List[int]"):
    ans = 1e9
    for bit in range(2 ** D):
        sum = 0
        rest_max = -1
        num = 0

        for i in range(D):
            if bit & 1 << i:
                sum += (i + 1) * 100 * p[i] + c[i]
                num += p[i]
            else:
                rest_max = i
        
        if sum < G:
            remain = G - sum
            s1 = 100 * (rest_max + 1)
            need = math.ceil(remain / s1)
            if need >= p[rest_max]:
                continue
            num += need
        ans = min(ans, num)

    print(ans)
    return


# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    D = int(next(tokens))  # type: int
    G = int(next(tokens))  # type: int
    p = [int()] * (D)  # type: "List[int]"
    c = [int()] * (D)  # type: "List[int]"
    for i in range(D):
        p[i] = int(next(tokens))
        c[i] = int(next(tokens))
    solve(D, G, p, c)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys


def solve(D: int, G: int, p: "List[int]", c: "List[int]"):
    ans = 1e9
    for bit in range(2 ** D):
        sum = 0
        rest_max = -1
        num = 0

        for i in range(D):
            if bit & 1 << i:
                sum += (i + 1) * 100 * p[i] + c[i]
                num += p[i]
            else:
                rest_max = i
        
        if sum < G:
            # remain = G - sum
            # need = int(remain / (100 * (rest_max + 1)))
            s1 = 100 * (rest_max + 1)
            need = int((G - sum + s1 - 1) / s1)
            if need >= p[rest_max]:
                continue
            num += need
        ans = min(ans, num)

    print(ans)
    return


# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    D = int(next(tokens))  # type: int
    G = int(next(tokens))  # type: int
    p = [int()] * (D)  # type: "List[int]"
    c = [int()] * (D)  # type: "List[int]"
    for i in range(D):
        p[i] = int(next(tokens))
        c[i] = int(next(tokens))
    solve(D, G, p, c)

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())
point = [i*100 for i in range(1,d+1)]
ans = float("inf")

for i in range(1<<d):
    score = 0
    cnt = 0
    for j in range(d):
        if i>>j & 1:
            cnt += p[j]
            score += point[j] * p[j] + c[j]
    if score >= g:
        ans = min(cnt,ans)
        continue
    for j in range(d)[::-1]:
        if i>>j & 1: continue
        x = min((g-score+point[j]-1)//point[j],p[j]-1)
        cnt += x
        score += point[j]*x
        if score >= g:
            ans = min(ans, cnt)
            break
print(ans)

Submission status: Accepted

Solution code:
import sys
import math
sys.setrecursionlimit(1000000) # 再帰上限を増やす

def main():
    input = sys.stdin.readline  # 文字列に対してinputした場合は、rstripするのを忘れずに！
    D, G = map(int, input().rstrip().split())
    problem_list = []
    for i in range(1, D+1):
        p, c = map(int, input().rstrip().split())
        problem_list.append((p, c + (i * 100 * p), i * 100))

    min_problems = 10**9
    for bit in range(1 << D):
        problem_num = 0
        total_score = 0
        unsolved_problems = None

        for i in range(D):
            if bit & (1 << i):
                # ボーナスポイントを取得
                problem_num += problem_list[i][0]
                total_score += problem_list[i][1]
                if problem_num >= min_problems:
                    break
            else:
                # ボーナスポイントを取得しない
                unsolved_problems = problem_list[i]

        if problem_num >= min_problems:
            continue

        if G <= total_score:
            min_problems = min(min_problems, problem_num)
        else:
            diff = G - total_score
            num, _, score = unsolved_problems
            needed_num = math.ceil(diff / score)
            if num > needed_num:
                problem_num += needed_num
                total_score += needed_num * score
                min_problems = min(min_problems, problem_num)
    print(min_problems)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
D, G = list(map(int, input().split()))
p, c = [0,], [0,]
for _ in range(D):
    pi, ci = list(map(int, input().split()))
    p.append(pi)
    c.append(ci)
ans = 1010
for i in range(2 ** D):
    score = 0
    solve = [False] * D
    for j in range(D):
        if i >> j & 1:
            solve[j] = True
        else:
            continue
    score = sum([100 * (j + 1) * p[j + 1] + c[j + 1] for j in range(D) if solve[j]])
    num = sum([p[j + 1] for j in range(D) if solve[j]])
    maxp = len(list(filter(lambda x: not x, solve)))
    if maxp != 0:
        for i in range(1, p[maxp]):
            if score >= G:
                break
            score += 100 * maxp
            num += 1
    if score < G:
        num = 1010
    ans = min(num, ans)
print(ans)

Submission status: Accepted

Solution code:
d, g = map(int, input().split())
src = [list(map(int, input().split())) for _ in range(d)]

ans = 10**10
for b in range(2**d):
  score = 0
  ac = 0
  for k in range(d):
    if b&(1<<k):
      p,c = src[k]
      score += c
      ac += p
      score += p*(k+1)*100
  if score >= g:
    ans = min(ans, ac)
    continue
  for k in range(d-1, -1, -1):
    if b&(1<<k)==0:
      p, c = src[k]
      if score +p*(k+1)*100 < g:
        score += p*(k+1)*100
        ac += p
      else:
        rem = g-score
        ac += -(-rem // (k+1) // 100)
        ans = min(ans, ac)
        break
print(ans)

Submission status: Accepted

Solution code:
d, g = map(int, input().split())
pc = [list(map(int, input().split())) for i in range(d)]
ans = float("inf")

for i in range(2**d):
    sum_temp = 0
    count_temp = 0
    remain = set(range(1, d+1))
    for j in range(d):
        if i >> j & 1:
            sum_temp += 100 * (j + 1) * pc[j][0] + pc[j][1]
            count_temp += pc[j][0]
            remain -= {j+1}
    if sum_temp < g:
        use = max(remain)
        n = min(pc[use - 1][0], -(-(g - sum_temp) // (use * 100)))
        count_temp += n
        sum_temp += n * 100 * use
    if sum_temp >= g:
        ans = min(ans, count_temp)

print(ans)

Submission status: Accepted

Solution code:
from itertools import product

d, g = map(int, input().split())
q = [list(map(int, input().split())) for _ in range(d)]

bits = product((0, 1), repeat=d)

least_cnt = float('inf')

for bit in bits:
    sum_of_points = 0
    cnt = 0
    cnt_increment = 0
    
    for i in range(d):
        if bit[i]:
            sum_of_points += 100*(i+1)*q[i][0] + q[i][1]
            cnt += q[i][0]
    
    if sum_of_points < g:
        for i in reversed(range(d)):    # 大きい方から探す
            if not bit[i]:
                if sum_of_points + 100*(i+1)*q[i][0] < g:   # ほぼ全問解いても点数が足りない
                    continue
                while sum_of_points < g:
                    sum_of_points += 100*(i+1)
                    cnt += 1
                break
    if sum_of_points >= g:
        least_cnt = min(least_cnt, cnt)

print(least_cnt)

Submission status: Accepted

Solution code:
d, g = map(int, input().split())
pc = [list(map(int, input().split())) for _ in range(d)]
ans = 10**7

for i in range(2**d):
    tmp = []
    a, n = 0, 0
    for j in range(d):
        if i >> j & 1:
            tmp.append(j)
    for j in tmp:
        a += (j+1) * 100 * pc[j][0] + pc[j][1]
        n += pc[j][0]
    if a >= g:
        ans = min(ans, n)
    else:
        for j in range(d):
            if not j in tmp:
                alpha = 0
                for k in range(1, pc[j][0]+1):
                    alpha += (j+1) * 100
                    if a + alpha >= g:
                        if n + k < ans:
                            a += alpha
                            n += k
                            ans = n
                            break

print(ans)

Submission status: Accepted

Solution code:
d, g = map(int, input().split())
pc = [list(map(int, input().split())) for i in range(d)]
ans = float("inf")

def func(i, sum, count, remain): 
    global ans
    #iはi*100点の問題を解くかどうか判断した後を示す
    #sumはi*100点の問題までで合計何点か
    #countはi+100点の問題までで何問といたか
    #remainは何番目の問題が残っているかを示す

    #ベースラインとして，d番目まで判断したら終わり
    if i == d:
        #もしgに届かなければ，残った問題のうち一番大きいものを解く
        if sum < g:
            use = max(remain)
            n = min(pc[use -1][0], -(-(g-sum) // (use * 100)))
            count += n
            sum += n * use * 100
        if sum >= g:
            ans = min(ans, count)
    else:
        func(i+1, sum, count, remain)
        func(i+1, sum+pc[i][0]*(i+1)*100+pc[i][1], count+pc[i][0], remain-{i+1})

func(0, 0, 0, set(range(1, d+1)))
print(ans)

Submission status: Accepted

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians, log2
from itertools import accumulate, permutations, combinations, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce
import numpy as np
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7
 
D, G = MAP()
pc = [LIST() for _ in range(D)]

count_min = 1001

for i in range(1<<D):
	count = 0
	sum = 0
	i = list("{:b}".format(i).zfill(D))
	#print(i)
	for j in range(D):
		if i[j] == "1":
			count += pc[j][0]
			sum += pc[j][0]*100*(j+1) + pc[j][1]

	if sum >= G:
		if count < count_min:
			#print("更新", count_min, ">", count)
			count_min = count

	else:
		for j in range(D-1, -1, -1):
			if i[j] == "0":
				remain_count = -(-(G-sum)//(100*(j+1)))
				#print(remain_count)
				if remain_count >= pc[j][0]:
					count = 1001
					break
				else:
					count += remain_count

				if count < count_min:
					#print("更新", count_min, ">", count)
					count_min = count

print(count_min)

Submission status: Accepted

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians, log2
from itertools import accumulate, permutations, combinations, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce
import numpy as np
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7
 
D, G = MAP()
pc = [LIST() for _ in range(D)]

count_min = 1001

for i in range(1<<D):
	count = 0
	sum = 0
	i = list("{:b}".format(i).zfill(D))
	#print(i)
	for j in range(D):
		if i[j] == "1":
			count += pc[j][0]
			sum += pc[j][0]*100*(j+1) + pc[j][1]

	if sum >= G:
		if count < count_min:
			#print("更新", count_min, ">", count)
			count_min = count

	else:
		for j in range(D-1, -1, -1):
			if i[j] == "0":
				remain_count = ceil((G-sum)/(100*(j+1)))
				#print(remain_count)
				if remain_count >= pc[j][0]:
					count = 1001
					break
				else:
					count += remain_count

				if count < count_min:
					#print("更新", count_min, ">", count)
					count_min = count

print(count_min)