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 math
import itertools
import sys
input = sys.stdin.readline

def main():
    D, G = map(int, input().split())
    spc_list = [[(i+1) * 100] + [int(v) for v in input().split()] for i in range(D)]
    max_scores = [spc[0] * spc[1] + spc[2] for spc in spc_list]
    min_q = float("inf")
    for q_list in itertools.permutations(list(range(D))):
        score = 0
        q_num = 0
        for q_idx in q_list:
            if score + max_scores[q_idx] < G:
                score += max_scores[q_idx]
                q_num += spc_list[q_idx][1]
            else:
                q_num += min(math.ceil((G-score) / spc_list[q_idx][0]), spc_list[q_idx][1])
                score = G
                """
                for _ in range(spc_list[q_idx][1]):
                    score += spc_list[q_idx][0]
                    q_num += 1
                    if score >= G:
                        break
                score += spc_list[q_idx][2]
"""
            if score >= G:
                break
        if q_num < min_q:
            min_q = q_num
    print(min_q)


if __name__ == '__main__':
    main()

Submission status: Accepted

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

res = 1000
for i in range(2**D):
    pts = 0
    num = 0
    hzero = False
    zd = -1
    for j in range(D):
        if (i >> j) & 1:
            pts += P[D-j-1][0]*(D-j)*100+P[D-j-1][1]
            num += P[D-j-1][0]
        else:
            if not hzero:
                zd = D-j-1
                hzero = True

    if pts >= G:
        res = min(res, num)
    else:
        if hzero:
            for j in range(1, P[zd][0]):
                pts += 100*(zd+1)
                num += 1
                if pts >= G:
                    res = min(res, num)
                    break

print(res)

Submission status: Accepted

Solution code:
d,g=map(int,input().split())
spc=[]
c=[]
for i in range(d):
    pi,ci=map(int,input().split())
    si=pi*100*(i+1)+ci
    av=si//pi
    spc.append([av,si,pi,ci,100*(i+1)])

#print(spc)

spc.sort(reverse=True)
#print(spc)

#r=g
#icnt=0
#for i in range(d):
#   r=r-spc[i][1]
#   icnt=icnt+spc[i][2]
#   if r<=0:
#       break
#print(r,icnt)


dmin=10000
for i in range(d):
    for j in range(2**d):
#        print("d=",d,"i=",i,"j=",j,j//2,j%2)
        icnt=0
        sisum=0
        j2=j
        for i2 in range(d):
            if i2!=i:
                if j2%2==1:
                    sisum=sisum+spc[i2][1]
                    icnt=icnt+spc[i2][2]
#            if sisum>g:
#               break
#                print("j=",j,icnt,sisum)
            j2=j2//2
        
        for k in range(spc[i][2]):
            sisum=sisum+spc[i][4]
            icnt=icnt+1
#            print("k",k,icnt,sisum)
            if sisum>=g:
                break
        if k==spc[i][2]-1 :
            sisum=sisum+spc[i][3]
#        if sisum>=g :
#            print("kend",icnt,sisum)
        if sisum>=g and icnt<dmin :
            dmin=icnt
#            print("dmin=",dmin,sisum)
    
print(dmin)

Submission status: Accepted

Solution code:
# coding: utf-8
# Your code here!

D,G = map(int,input().split())
p,c = [],[]
res = 1<<30
for i in range(D):
    x,y = map(int,input().split())
    p.append(x)
    c.append(y)
for i in range(2**D):
    sum_x,cnt = 0,0
    for j in range(D):
        if i&(1<<j):
            sum_x+=c[j]+p[j]*100*(j+1)
            cnt+=p[j]
    if(sum_x<=G):
        for j in reversed(range(D)):
            if i&(1<<j): continue
            for k in range(p[j]):
                if sum_x>=G: break
                sum_x+=100*(j+1)
                cnt+=1
    if(res>cnt): res=cnt
print(res)

Submission status: Accepted

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

min_ac1 = 1000
min_ac2 = 1000
for i in range(2 ** d):
    points = 0
    ac = 0
    for j in range(d):
        if ((i >> j) & 1) == 1:
            points += pc[j][0] * 100 * (j + 1) + pc[j][1]
            ac += pc[j][0]
    if points < g:
        l = "{:010b}".format(i)
        l = l[10-d:]
        for k in range(d):
            if l[k] == "0":
                tmp = k
                break
        tmp = -(tmp - d)
        if (g - points + tmp * 100 - 1) // (tmp * 100) < pc[tmp - 1][0]:
            tmp_ac = ac + (g - points + tmp * 100 - 1) // (tmp * 100)
            if tmp_ac < min_ac1:
                min_ac1 = tmp_ac
    if points >= g:
        if ac < min_ac2:
            min_ac2 = ac
    #print(bin(i), ac, points, min_ac1, min_ac2)
print(min(min_ac1, min_ac2))

Submission status: Accepted

Solution code:
import math
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)
#print(p,c)
ans=float('inf')
for i in range(2**d):
    cnt=0
    score=0
    maxim = 0  # 解かれていない中で最大の配点のやつ
    for j in range(d):
        #ボーナスもらう問題
        if (i>>j)&1:
            cnt+=p[d-1-j]
            score+=(d-j)*100*p[d-1-j]+c[d-1-j]
        else:
            maxim=max(maxim,d-1-j)

    left=g-score
    if left<=0:
        ans=min(ans,cnt)
    else:
        if left<=100*(maxim+1)*(p[maxim]-1):
            count=math.ceil(left/(100*(maxim+1)))
            ans=min(ans,cnt+count)

print(ans)

Submission status: Accepted

Solution code:

d,g = map(int,input().split(' '))
pc = []
for _ in range(d):
    p,c = map(int,input().split(' '))
    pc.append((p,c))

ans = 10000000

for i in range(2**d):
    cnt = 0
    score = 0
    max_flg = 0
    for j in range(d):
        #print(str(i) + ' ' + str(j))
        if((i>>j)&1 == 1):
            score += pc[j][0]*(j+1)*100+pc[j][1]
            cnt += pc[j][0]
        else:
            max_flg = j
    
    #print(str(score) + ' '+ str(cnt))
    if(score >= g):
        ans = min(ans,cnt)
    elif(score + (pc[max_flg][0]-1)*(max_flg+1)*100 < g):
        continue
    else:
        for k in range(pc[max_flg][0]):
            if(score + k*(max_flg+1)*100 >= g):
                ans = min(ans,cnt+k)
            else:
                continue

print(str(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)
cnt=10**5
for i in range(1<<d):
    tmp=0
    ans=0
    for j in range(d):
        if i&(1<<j):
            tmp+=c[j]+p[j]*100*(j+1)
            ans+=p[j]
    for j in range(d-1,-1,-1):
        if tmp>=g:
            break
        if i&(1<<j):
            continue
        for k in range(p[j]-1):
            tmp+=100*(j+1)
            ans+=1
            if tmp>=g:
                break
    if tmp>=g: #最後も確認
        cnt=min(ans,cnt)
print(cnt)

Submission status: Accepted

Solution code:
#104_C
D,G=map(int,input().split())
Pb=[]
for _ in range(D):
    p,c=map(int,input().split())
    Pb.append((p,c))

Ans=10**4+1

for i in range(2**D):
    score=0
    cnt=0
    max_flg=-1
    for j in range(D):
        p,c=Pb[j]
        if (i>>j)&1:
            score+=p*(j+1)*100+c
            cnt+=p
        else:
            max_flg=j
    
    if score<G:
        if max_flg==-1:
            continue
        if -(-(G-score)//((max_flg+1)*100))>=Pb[max_flg][0]:
             continue
        else:
            cnt+=-(-(G-score)//((max_flg+1)*100))
    
    Ans=min(Ans,cnt)
    #print(Ans)

print(Ans)

Submission status: Accepted

Solution code:
from itertools import product
from math import ceil

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

min_count = 10 ** 10
for use in product(range(2), repeat=d):
    count = 0
    total = 0
    for i in range(d):
        if use[i]:
            total += (i + 1) * 100 * PC[i][0] + PC[i][1]
            count += PC[i][0]
    if total >= g:
        if count < min_count:
            min_count = count
    else:
        for i in range(d):
            if use[i]:
                continue
            if total + (i + 1) * 100 * (PC[i][0] - 1) >= g:
                tmp_count = count + ceil((g - total) // 100 / (i + 1))
                if tmp_count < min_count:
                    min_count = tmp_count

print(min_count)

Submission status: Accepted

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

p, c = [], []
for _ in range(d):
     tp, tc = map(int, input().split())
     p.append(tp)
     c.append(tc)

ans = float("inf")
for bit in range(2 ** d):
    s_temp = 0
    p_temp = 0
    m_temp = -1
    for dd in range(d):
        if (bit >> dd) & 1:
            s_temp += p[dd] * (dd+1) * 100 + c[dd]
            p_temp += p[dd]
        else:
            m_temp = dd
            
    diff = g - s_temp
    
    if diff <= 0:
        ans = min(ans, p_temp)
    elif m_temp != -1:
        from math import ceil
        tt = ceil(diff / (m_temp+1) / 100)
        if tt <= p[m_temp]:
            ans = min(ans, p_temp + tt)

print(ans)

Submission status: Accepted

Solution code:
D, G = map(int, input().split())
p_list = []
c_list = []
for i in range(D):
    list_for = list(map(int, input().split()))
    p_list.append(list_for[:][0])
    c_list.append(list_for[:][1])

memo = 0
count_list=[]
for i in range(1<<D):
    sum = 0
    count = 0
    lcount = 1
    del memo
    for j in range(D):
        if (i>>j)&1:
            sum += 100*(j+1)*p_list[j]+c_list[j]
            count += p_list[j]
        else:
            memo = j


    while G-sum > 0 and lcount<p_list[memo]:
        sum += 100*(memo+1)
        lcount += 1
        count += 1
    if sum >= G:
        count_list.append(count)

print(min(count_list))
#print(count_list)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
f = lambda:map(int,input().split())
d,g = f()
g//=100
ll = []
for i in range(d):
  p,c = f()
  ll.append([i+1,p,c//100])
ll = ll[::-1]
import itertools as it
ans = 10**9
for t in it.product(range(2),repeat=d):
  cnt = 0
  tot = 0
  flg = 1
  lg = [1,0]
  for i,b in enumerate(t):
    u,p,c = ll[i]
    if b:
      cnt += p
      tot += u*p+c
    elif flg:
      lg = [u,p]
      flg = 0
  if g <= tot+lg[0]*lg[1]:
    ans=min(ans,cnt+max(g-tot,0)//lg[0])
print(max(ans,1))

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
f = lambda:map(int,input().split())
d,g = f()
g//=100
ll = []
for i in range(d):
  p,c = f()
  ll.append([i+1,p,c//100])
ll = ll[::-1]
import itertools as it
ans = 10**9
for t in it.product(range(2),repeat=d):
  cnt = 0
  tot = 0
  flg = 1
  lg = [1,0]
  for i,b in enumerate(t):
    u,p,c = ll[i]
    if b:
      cnt += p
      tot += u*p+c
    elif flg:
      lg = [u,p]
      flg = 0
  if g <= tot+lg[0]*lg[1]:
    ans=min(ans,cnt+max(g-tot,0)//lg[0])
print(max(1,ans))

Submission status: Accepted

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

kosumin=10000
for i in range(1<<d):
    score=0
    kosu=0
    jmax=0
    siyouzumi=[]
    for j in range(d):
        if ((i>>j)&1)==1:
            score+=gokei[j]
            kosu+=pc[j][0]
            siyouzumi.append(j)

    if score>=g:
        if kosumin>kosu:
            kosumin=kosu
    if score<g:
        a=d-1
        while True:
            if a==-1:
                break
            if not a in siyouzumi:
                saidai=a
                break
            a-=1
        if a==-1:
            continue

        for k in range(pc[saidai][0]):
            score+=(saidai+1)*100
            kosu+=1
            if k==pc[saidai][0]-1:
                score+=pc[saidai][1]
            if score>=g:
                break
        if score>=g and kosumin>kosu:
            kosumin=kosu
print(kosumin)

Submission status: Accepted

Solution code:
D,G=map(int, input().split())
G //= 100
dp = [ [ 0 for i in range(1105) ] for i in range(12) ]
for i in range(1,D+1):
  p, c = map(int, input().split())
  c //= 100
  for j in range(1005):
    for k in range(p):
      dp[i][j+k] = max( dp[i][j+k], dp[i-1][j] + k*i)
    dp[i][j+p] = max( dp[i][j+p], dp[i-1][j] + p*i + c)

for i in range(1001):
  if dp[D][i] >= G:
    print(i)
    break

#for j in range(23):
#  print(j,dp[0][j],dp[1][j],dp[2][j])

Submission status: Accepted

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

for i in range(2 ** d):
    cnt = 0
    point = 0
    for j in range(d):
        if (i >> j) & 1:
            point += 100 * (j + 1) * scores[j][0]
            point += scores[j][1]
            cnt += scores[j][0]
    if point >= g:
        pod.append(cnt)
        continue
    else:
        for p in range(d - 1, -1, -1):
            if not (i >> p) & 1:
                for q in range(scores[p][0]):
                    if point < g:
                        point += (p + 1) * 100
                        cnt += 1
                    else:
                        continue
    pod.append(cnt)

print(min(pod))

Submission status: Accepted

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

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

p = [pc[i][0] for i in range(n)]
c = [pc[i][0]*(i+1)*100+pc[i][1] for i in range(n)]


ans = 1e18
for i in range(1<<n):
    sm = cnt = idx = 0
    for j in range(n):
        if (i>>j)&1:
            sm += c[j]
            cnt += p[j]
        else:
            idx = j+1
    if g-sm>0:
        tmp = (g-sm+idx*100-1)//(idx*100)
        if 0<=tmp<=p[idx-1]: ans = min(ans, cnt+tmp)
    else: ans = min(ans, cnt)
print(ans)

Submission status: Accepted

Solution code:
'''
最小となる問題数のケースは2通り。
1. 得点の大きい問題から順に解いていく
2. コンプリートボーナスの大きい問題から解いていく
どちらのケースでも解いた問題の組み合わせは以下となる
(a)コンプリートボーナスを獲得した問題 * n + (b)一部だけ解いている問題
'''

D, G = map(int, input().split())

# (Pi, Pi個の問題を説いた場合のボーナスポイント込の得点, 1問あたりの得点)
PC = [0] * D
for i in range(D):
    P, C = map(int, input().split())
    PC[i] = [P, 100 * (i + 1) * P + C, 100 * (i + 1)]

# print(PC)

# 各問題で全問解くか解かないかをbit全探索
ans = 10 * 100
for i in range(2 ** D):
    bit = format(i, '0' + str(D) + 'b') # 完答有無
    score = 0 # 得点
    solve = 0

    # print("==========bit: " + bit + " =============")

    # 完答分の得点
    for j in range(D):
        if bit[j] == "1":
            score += PC[j][1]
            solve += PC[j][0]
            # print(j, score, solve)

    # 完答分の得点で足りない場合、解かれていない問題の得点(1つのみ選び、完答しない)で足りるか
    if score < G:
        for k in range(D):
            # print("-(k+1): " + str(-(k+1)), "bit[-(k+1)]: " + str(bit[-(k+1)]))
            if bit[-(k+1)] == "0":
                sol = min((G - score) // PC[-(k+1)][2], PC[-(k+1)][0] - 1) # 解いた数
                if sol == 0:
                    sol = 1
                score += PC[-(k+1)][2] * sol
                solve += sol
                # print(sol, score, solve)
                break

    # 総合スコアがG以上となる場合、問題数が最小であれば答えを更新する
    if score >= G:
        ans = min(ans, solve)
    # print(bit, score, solve, ans)

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)
cnt = 10 ** 5
for i in range(2**d):
    tmp = 0
    ans = 0
    for j in range(d):
        if i >> j & 1:
            tmp += p[j]
            ans += c[j] + p[j] * 100 * (j + 1)
    for j in range(d-1, -1, -1):
        if ans >= g:
            break
        if i >> j & 1:
            continue
        for k in range(p[j] - 1):
            ans += 100 * (j + 1)
            tmp += 1
            if ans >= g:
                break
    if ans >= g:
        cnt = min (tmp, cnt)
print(cnt)

Submission status: Accepted

Solution code:
d,g=map(int,input().split())
pc=[list(map(int,input().split())) for _ in range(d)]
ans=0
for i in range(1<<d):
  p=0
  cnt=0
  for j in range(d):
    if (i>>j)&1:
      p+=100*(j+1)*pc[j][0]+pc[j][1]
      cnt+=pc[j][0]
  if g>p:
    for k in range(d)[::-1]:
      if (i>>k)&1==0:
        if g-p<=100*(k+1)*(pc[k][0]-1):
          cnt+=-(-(g-p)//(100*(k+1)))
          break
        else:
          cnt=10**5
          break
  if ans==0 or ans>cnt:
    ans=cnt
print(ans)

Submission status: Accepted

Solution code:
# 入力の受け取り
D, G = [int(i) for i in input().split()]
p = []
c = []
num_solves = []
for i in range(D):
    p_i, c_i = [int(i) for i in input().split()]
    p.append(p_i)
    c.append(c_i)

# 完答時のスコアを算出しておく
cs = []
for i in range(D):
    cs.append(100 * (i + 1) * p[i] + c[i])

# 完答する問題を全探索する
for i in range(2 ** D):
    score = 0
    num_solve = 0
    not_complete = []
    for j in range(D):
        # 完答する場合は完答時のスコアと問題数を加算する。
        if i >> j & 1:
            score += cs[j]
            num_solve += p[j]
        else:
            not_complete.append(j)
    # 目標を超えているか判定する。
    if score >= G:
        num_solves.append(num_solve)
    else:
        # 目標を超えていなければ、点数の高い順にスコアを加算していく。ただし完答はしないので解く問題数は最大p_i -1 
        for np in reversed(not_complete):
            for n in range(p[np]-1):
                score += 100 * (np + 1)
                num_solve += 1
                if score >= G:
                    num_solves.append(num_solve)
                    break
            if score >= G:
                break
# 解いた問題数の最小値を出力する
print(min(num_solves))

Submission status: Accepted

Solution code:
D, G = [int(x) for x in input().split()]
lst = [[int(x) for x in input().split()] for i in range(D)]
bit = 0
min_n = float('inf')
while bit < (1 << D):
    # print('=====')
    # print(bit)
    # print('=====')
    score = 0
    n = 0
    for i in range(D):
        if bit & (1 << i):
            score += 100 * (i + 1) * lst[i][0] + lst[i][1]
            n += lst[i][0]
    #print('素点 = ', score)
    if score < G:
        #print('~つまみぐい~')
        max_i = -1
        for i in reversed(range(D)):
            if not bit & (1 << i):
                max_i = i
                break
        #print('max_i = ', max_i)
        if max_i >= 0:
            for j in range(lst[max_i][0]):
                score += 100 * (max_i + 1)
                if score >= G:
                    n += j + 1
                    break
            if score < G:
                bit += 1
                continue
    if min_n > n:
        min_n = n
    bit += 1
print(min_n)

Submission status: Accepted

Solution code:
import numpy as np

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

p=[0]*(d+1)
c=[0]*(d+1)

for i in range(1,d+1):
    pp,cc=[int(c) for c in input().split(" ")]
    p[i]=pp
    c[i]=cc

def rec(i,g,flag):
    if i==d+1:
        cnt=0
        if g<=0:
            return 0

        for j in range(d,0,-1):
            bit=flag%2
            flag//=2

            if bit==0:
                ptsperprob=j*100
                psolved=min(p[j]-1,int(np.ceil(g/ptsperprob)))

                g-=psolved*ptsperprob
                cnt+=psolved

                if g<=0:
                    return cnt
        
        return 10000

    return min(p[i]+rec(i+1,g-c[i]-p[i]*100*i,2*flag+1),rec(i+1,g,2*flag))

print(rec(1,g,0))

Submission status: Accepted

Solution code:
D,G = map(int,input().split())
l = list(list(map(int, input().split())) for _ in range(D))

#得点の大きい順に並び替えておく
l = l[::-1]

ans = float("inf")
for i in range(2**D):
    total = 0
    cnt = 0
    for j in range(D):
        if (i>>j)&1:
            total += 100*(D-j)*l[j][0] + l[j][1]
            cnt += l[j][0]
    if total >= G:
        ans = min(ans,cnt)
        continue
    for j in range(D):
        if (i>>j)&1 == False:
            for k in range(l[j][0]):
                total += 100*(D-j)
                cnt+=1
                if total >= G:
                    ans = min(ans,cnt)
                    break
            break

print(ans)

Submission status: Accepted

Solution code:
D,G = map(int,input().split())
l = list(list(map(int, input().split())) for _ in range(D))

#得点の大きい順に並び替えておく
l = l[::-1]

ans = float("inf")
for i in range(2**D):
    total = 0
    cnt = 0
    for j in range(D):
        if (i>>j)&1:
            total += 100*(D-j)*l[j][0] + l[j][1]
            cnt += l[j][0]
    if total >= G:
        ans = min(ans,cnt)
        continue
    for j in range(D):
        if (i>>j)&1 == False:
            for k in range(l[j][0]):
                total += 100*(D-j)
                cnt+=1
                if total >= G:
                    ans = min(ans,cnt)
                    break
            else:
                continue
            break

print(ans)

Submission status: Accepted

Solution code:
import itertools
from collections import deque,defaultdict,Counter
from itertools import accumulate
import bisect
from heapq import heappop,heappush
from fractions import gcd
from copy import deepcopy
import math
import queue
#import numpy as np
#import sympy as syp(素因数分解とか)
Mod = 1000000007
import sys

sys.setrecursionlimit(100000) 
  
def sieve_of_eratosthenes(n):
    if not isinstance(n,int):
        raise TypeError("n is not int")
    if n<2:
        raise ValueError("n is not effective")
    prime = [1]*(n+1)
    for i in range(2,int(math.sqrt(n))+1):
        if prime[i] == 1:
            for j in range(2*i,n+1):
                if j%i == 0:
                    prime[j] = 0
    res = []
    for i in range(2,n+1):
        if prime[i] == 1:
            res.append(i)
    return res

def factorial(i):
    if i == 1:
        return 1
    else:
        return i*factorial(i-1)
 
class UnionFind:
    def __init__(self,n):
        self.parent = [i for i in range(n+1)]
        self.rank = [0 for i in range(n+1)]
    
    def findroot(self,x):
        if x == self.parent[x]:
            return x
        else:
            y = self.parent[x]
            y = self.findroot(self.parent[x])
            return y
    
    def union(self,x,y):
        px = self.findroot(x)
        py = self.findroot(y)
        if px < py:
            self.parent[py] = px
        else:
            self.parent[px] = py
 
    def same_group_or_no(self,x,y):
        return self.findroot(x) == self.findroot(y)


class Dijkstra:
 
    def __init__(self, rote_map, start_point, goal_point=None):
        self.rote_map = rote_map
        self.start_point = start_point
        self.goal_point = goal_point
 
    def execute(self):
        num_of_city = len(self.rote_map)
        dist = [float("inf") for _ in range(num_of_city)]
        prev = [float("inf") for _ in range(num_of_city)]
 
        dist[self.start_point] = 0
        heap_q = []
        heapq.heappush(heap_q, (0, self.start_point))
        route_count = [0 for _ in range(num_of_city)]
        route_count[self.start_point] = 1
        while len(heap_q) != 0:
            prev_cost, src = heapq.heappop(heap_q)
 
            if dist[src] < prev_cost:
                continue
 
            for dest, cost in self.rote_map[src].items():
                if cost != float("inf") and dist[dest] > dist[src] + cost:
                    dist[dest] = dist[src] + cost
                    heapq.heappush(heap_q, (dist[dest], dest))
                    prev[dest] = src
                if dist[dest] == dist[src] + cost:
                    route_count[dest] += route_count[src]
 
        if self.goal_point is not None:
            return self._get_path(self.goal_point, prev)
        else:
            return dist, route_count
 
    def _get_path(self, goal, prev):
        path = [goal]
        dest = goal
 
        while prev[dest] != float("inf"):
            path.append(prev[dest])
            dest = prev[dest]
 
        return list(reversed(path))

        
def main(): #startline--------------------------------------------
    d,g = map(int,input().split())
    pc = [list(map(int,input().split())) for i in range(d)]
    p = [pc[i][0] for i in range(d)]
    c = [pc[i][1] for i in range(d)]
    def dfs(cur,tar):
        if cur == 0:
            return 10**9
        cnt = min(tar//(cur*100),p[cur-1])
        tmp = 100*cur*cnt
        if cnt == p[cur-1]:
            tmp += c[cur-1]
        if tmp < tar:
            cnt += dfs(cur-1,tar-tmp)
        return min(cnt,dfs(cur-1,tar))

    print(dfs(d,g))
if __name__ == "__main__":
    main() #endline===============================================

Submission status: Accepted

Solution code:
import itertools
from collections import deque,defaultdict,Counter
from itertools import accumulate
import bisect
from heapq import heappop,heappush
from fractions import gcd
from copy import deepcopy
import math
import queue
#import numpy as np
#import sympy as syp(素因数分解とか)
Mod = 1000000007
import sys

sys.setrecursionlimit(100000) 
  
def sieve_of_eratosthenes(n):
    if not isinstance(n,int):
        raise TypeError("n is not int")
    if n<2:
        raise ValueError("n is not effective")
    prime = [1]*(n+1)
    for i in range(2,int(math.sqrt(n))+1):
        if prime[i] == 1:
            for j in range(2*i,n+1):
                if j%i == 0:
                    prime[j] = 0
    res = []
    for i in range(2,n+1):
        if prime[i] == 1:
            res.append(i)
    return res

def factorial(i):
    if i == 1:
        return 1
    else:
        return i*factorial(i-1)
 
class UnionFind:
    def __init__(self,n):
        self.parent = [i for i in range(n+1)]
        self.rank = [0 for i in range(n+1)]
    
    def findroot(self,x):
        if x == self.parent[x]:
            return x
        else:
            y = self.parent[x]
            y = self.findroot(self.parent[x])
            return y
    
    def union(self,x,y):
        px = self.findroot(x)
        py = self.findroot(y)
        if px < py:
            self.parent[py] = px
        else:
            self.parent[px] = py
 
    def same_group_or_no(self,x,y):
        return self.findroot(x) == self.findroot(y)


class Dijkstra:
 
    def __init__(self, rote_map, start_point, goal_point=None):
        self.rote_map = rote_map
        self.start_point = start_point
        self.goal_point = goal_point
 
    def execute(self):
        num_of_city = len(self.rote_map)
        dist = [float("inf") for _ in range(num_of_city)]
        prev = [float("inf") for _ in range(num_of_city)]
 
        dist[self.start_point] = 0
        heap_q = []
        heapq.heappush(heap_q, (0, self.start_point))
        route_count = [0 for _ in range(num_of_city)]
        route_count[self.start_point] = 1
        while len(heap_q) != 0:
            prev_cost, src = heapq.heappop(heap_q)
 
            if dist[src] < prev_cost:
                continue
 
            for dest, cost in self.rote_map[src].items():
                if cost != float("inf") and dist[dest] > dist[src] + cost:
                    dist[dest] = dist[src] + cost
                    heapq.heappush(heap_q, (dist[dest], dest))
                    prev[dest] = src
                if dist[dest] == dist[src] + cost:
                    route_count[dest] += route_count[src]
 
        if self.goal_point is not None:
            return self._get_path(self.goal_point, prev)
        else:
            return dist, route_count
 
    def _get_path(self, goal, prev):
        path = [goal]
        dest = goal
 
        while prev[dest] != float("inf"):
            path.append(prev[dest])
            dest = prev[dest]
 
        return list(reversed(path))

        
def main(): #startline--------------------------------------------
    d,g = map(int,input().split())
    pc = [list(map(int,input().split())) for i in range(d)]
    p = [pc[i][0] for i in range(d)]
    c = [pc[i][1] for i in range(d)]
    ans = 10**9
    def dfs(cur,tar):
        if cur == 0:
            return 10**9
        cnt = min(tar//(cur*100),p[cur-1])
        tmp = 100*cur*cnt
        if cnt == p[cur-1]:
            tmp += c[cur-1]
        if tmp < tar:
            cnt += dfs(cur-1,tar-tmp)
        return min(cnt,dfs(cur-1,tar))
    print(dfs(d,g))
if __name__ == "__main__":
    main() #endline===============================================

Submission status: Accepted

Solution code:
#coding:utf-8
D,G=map(int,input().split(" "))
Comp={}
for i in range(D):
  p,c=map(int,input().split(" "))
  Comp[i]=[p,c]
Min=1000000000
for i in range(2**(D)):
  answer=0
  score=0
  Clear=[]
  for j in range(D):
    if ((i>>j)&1):
      score+=(j+1)*100*Comp[j][0]
      score+=Comp[j][1]
      answer+=Comp[j][0]
      Clear.append(j+1)
  No=D
  Count=0
  while score<G and No>=1:
    if No in Clear or Count==Comp[No-1][0]:
      Count=0
      No-=1
    score+=100*No
    Count+=1
    answer+=1
  Min=min(Min,answer)
print(Min)

Submission status: Accepted

Solution code:
#coding:utf-8
D,G=map(int,input().split(" "))
Comp={}
for i in range(D):
  p,c=map(int,input().split(" "))
  Comp[i]=[p,c]
Min=1000000000
for i in range(2**(D)):
  answer=0
  score=0
  Clear=[]
  for j in range(D):
    if ((i>>j)&1):
      score+=(j+1)*100*Comp[j][0]
      score+=Comp[j][1]
      answer+=Comp[j][0]
      Clear.append(j+1)
  No=D
  Count=0
  while score<G and No>=1:
    if No in Clear or Count==Comp[No-1][0]:
      Count=0
      No-=1
    score+=100*No
    Count+=1
    answer+=1
  if score>=G:
    Min=min(Min,answer)
print(Min)