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 itertools

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

num = D #生成するビット数
bit_list = list(itertools.product([0, 1], repeat=num))
tmp = 10 ** 6

for bit in bit_list:
    count = 0
    num = 0
    for i in range(D):
        if bit[i] == 1:
            count += L[i][0] *(i+1) * 100 + L[i][1]
            num += L[i][0]
            
    if count >= G:
        tmp = min(num, tmp)
        
    else:
        for i in range(1, D+1):
            if bit[D-i] == 0:
                for j in range(L[D-i][0]):
                    count += (D-i+1) * 100
                    num += 1
                    if count >= G:
                        break
                break
                
        if count >= G:
            tmp = min(num, tmp)
            
print(tmp)

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 bit in range(1 << d):
    count = 0
    sum = 0
    nokori = set(range(1, d + 1))
    for i in range(d):
        if bit & (1 << i):
            sum += pc[i][0] * (i + 1) * 100 + pc[i][1]
            count += pc[i][0]
            nokori.discard(i + 1)
    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)
print(ans)

Submission status: Accepted

Solution code:
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)
        return 0
    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})

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

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

Submission status: Accepted

Solution code:
d,g = map(int,input().split())
l = [list(map(int,input().split())) for i in range(d)]
# t番目の問題でスコアsをとるための最小値
def f(t,s):
    if t==-1:
        return float('inf')
    num = min(l[t][0],s//((t+1)*100))
    k = num*(t+1)*100
    if num==l[t][0]:
        k += l[t][1]
    if k<s:
        num += f(t-1,s-k)
    return min(num,f(t-1,s))

print(f(d-1,g))

Submission status: Accepted

Solution code:
d,g = map(int, input().split())
P = []
C = []
PC = []
for i in range(d):
    p,c = map(int, input().split())
    P.append(p)
    C.append(c)
    PC.append((p,c))
    
P_sum = sum(P)
dp = [0 for i in range(P_sum + 1)]
for i,j in enumerate(PC):
    for k in range(P_sum,  -1, -1):
        for l in range(1,j[0]+1):
            if l + k <= P_sum:
                if l == j[0]:
                    cc = 100 * (i + 1)* l + j[1]
                else:
                    cc = 100 * (i + 1) * l
                dp[l + k] = max(dp[l + k ], dp[k] + cc)
                
for i,j in enumerate(dp):
    if j >= g:
        print(i)
        break

Submission status: Accepted

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

res = 1e10
for i in range(1 << d):
    total = 0
    num = 0
    rest_max = -1
    for j in range(d):
        if (i >> j) & 1 == 1:
            total += (j+1)*100*pc[j][0] + pc[j][1]
            num += pc[j][0]
        else:
            rest_max = j
    if total < g:
        rest = (g - total + (rest_max+1)*100 - 1) // ((rest_max+1)*100)
        if pc[rest_max][0] < rest:
            continue
        num += rest
    res = min(res, num)
print(res)

Submission status: Accepted

Solution code:
import sys

def f(g, d, P, C):
  if d <= 0:
    return float('inf')
  
  n = min(g//(100*d), P[d-1])
  s = 100*d*n

  if n == P[d-1]:
    s += C[d-1]
  
  if g > s:
    n += f(g-s, d-1, P, C)
  
  return min(n, f(g, d-1, P, C))
  

def main():
  input = sys.stdin.readline
  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 = f(G, D, P, C)
  print(ans)


if __name__ == '__main__':
  main()

Submission status: Accepted

Solution code:
import math
D, G = map(int, input().split())
PCS = [ list(map(int, input().split())) + [(i+1)*100] for i in range(D)]

def main():
    ans = float('inf')
    for i in range(1<<D): # pattern i
        g = G
        cnt = 0
        for d in range(D):
            if i & (1<<d): # Solve d
                g -= PCS[d][0]*PCS[d][2] + PCS[d][1]
                cnt += PCS[d][0]
        if g<=0:
            ans = min(ans, cnt)
            continue

        # Not done
        for d in range(D-1, -1, -1):
            if i & (1<<d):
                continue # Solved
            # Not yet
            n = math.ceil(g/PCS[d][2])
            if n>=PCS[d][0]:
                break
            g -= n*PCS[d][2]
            cnt += n
            break
        if g<=0:
            ans = min(ans, cnt)

            
    return ans

print(main())

Submission status: Accepted

Solution code:
a,b=map(int,input().split())
c=[0]+[list(map(int,input().split()))for i in range(a)]
def f(t,s):
    if t==0:
        return 10**9
    l=min(s//(t*100),c[t][0])
    k=100*t*l
    if l==c[t][0]:
        k+=c[t][1]
    if k<s:
        l+=f(t-1,s-k)
    return min(l,f(t-1,s))
print(f(a,b))

Submission status: Accepted

Solution code:
d,g = map(int, input().split())
p = []
c = []
for i in range(d):
    a,b = map(int, input().split())
    p.append(a)
    c.append(b)
    
dp = [0 for i in range(sum(p) + 2)] 
for i in range(1,d+1):
    count_max = p[i-1]
    bonus = c[i-1]
    for j in range(sum(p)+1,0,-1):
        for k in range(1,count_max+1):
            if k < count_max:
                cc = 100 * i * k
            if k == count_max:
                cc = 100 * i * k + bonus
                
            if j - k >= 0:
                dp[j] = max(dp[j],dp[j-k] + cc)
                
for i,j in enumerate(dp):
    if g <= j:
        print(i)
        break

Submission status: Accepted

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

lst1 = list()
for k, pair in enumerate(lst):
    lst1.append([pair[0], pair[1], (k+1)*100, (k+1)*100*pair[0]+pair[1]])
lst = lst1

string = '0' + str(d) + 'b'
str_lst = []
for i in range(0, 2**d):
    str_lst.append(format(i, string))
    
min_count = 10 ** 100
for str1 in str_lst:
    count = 0
    pt = 0
    remain = list()
    for k, qua in enumerate(lst):
        if str1[k] == '1':
            count += qua[0]
            pt += qua[3]
        else:
            remain.append(qua)
    if pt < g:
        qua = remain[-1]
        for i in range(qua[0]-1):
            count += 1
            pt += qua[2]
            if pt >= g:
                break
    if pt >= g:
        if min_count > count:
            min_count = count
            
print(min_count)

Submission status: Accepted

Solution code:
I=lambda:map(int,input().split())
D,G=I()
P={};C={};S={}
R=range(D)
for i in R:P[i],C[i]=I();S[i]=-~i*100*P[i]+C[i]
r=1e9+7
for k in range(1<<D):
 h=str(bin(k))[2:].rjust(D,'0');p=0;s=0
 for i in R:
  if h[i]=='1':p+=P[i];s+=S[i]
 if s>=G:r=min(r,p);continue
 for i in R[::-1]:
  j=-~i*100
  if h[i]=='0'and G-s<j*P[i]:r=min(r,p+(G-s+j-1)//j);break
print(r)

Submission status: Accepted

Solution code:
I=lambda:map(int,input().split())
divup=lambda x,y:(x+y-1)//y
D,G=I()
P={};C={};Score={}
for i in range(D):P[i],C[i]=I();Score[i]=-~i*100*P[i]+C[i]
r=1e9+7
for k in range(1<<D):
    str_branch=str(bin(k))[2:].rjust(D,'0')
    probs=0;score=0
    for i,b in enumerate(str_branch):
        if b=='1':probs+=P[i];score+=Score[i]
    if score>=G:r=min(r,probs);continue
    for i in range(D)[::-1]:
        pi=-~i*100
        if str_branch[i]=='0' and G-score<pi*P[i]:
            r=min(r,probs+divup(G-score,pi));break
print(r)

Submission status: Accepted

Solution code:
D, G = map(int,input().split())
L = []
ans = []
def ceil(i):
    if int(i) == i:
        return int(i)
    else:
        return int(i)+1


for _ in range(D):
    l = list(map(int,input().split())) +[0]
    L.append(l)
for k in range(2**D):
    value = 0
    b = format(k,'b').zfill(D)
    l = list(map(int,list(b)))
    cnt = 0
    for i in range(D):
        if l[i]:
            L[i][2] = 1
            value += L[i][1]
            value += L[i][0]*((i+1)*100)
            cnt += L[i][0]
        else:
            L[i][2] = 0
    remain = list(filter(lambda x:x[2]==0,L))[::-1]
    j = len(remain)
#    print(value,cnt,remain)
    if G - value > 0:
        while True:
            if remain==[]:
                cnt = 10**100
                break
            tmp = remain.pop(0)
            if G - value <= (j*100)*(tmp[0] - 1):
 #               print(G-value,j*100)
                cnt += ceil((G-value)/(j*100))
                break
            else:
                cnt += tmp[0]-1
                value += (j*100)*(tmp[0]-1)
                j -= 1
    ans.append(cnt)

print(min(ans))

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 i in range(1<<D):
    score = 0
    cnt = 0
    for j in range(D):
        if i&(1<<j):
            score += pc[j][0]*(j+1)*100+pc[j][1]
            cnt += pc[j][0]
    if score>=G:
        ans = min(ans,cnt)
    else:
        for j in range(D)[::-1]:
            if i&(1<<j):
                continue
            for k in range(pc[j][0]):
                score += 100*(j+1)
                cnt += 1
                if score>=G:
                    break
            if score>=G:
                break
        ans = min(ans,cnt)
print(ans)

Submission status: Accepted

Solution code:
D, G=list(map(int, input().split()))
#L[i][0]:i番目の問題数、L[i][0]:i番目のボーナス得点
L=[0]+[list(map(int, input().split())) for i in range(D)]
 
#f:i番目まで考えるときの最小問題数  
def f(G, i):
    if i==0:
	    return 10000
    #n:i番目を絶対に解くときの問題数  
    n=min(G//(i*100), L[i][0])
    #s:i番目を絶対に解くときのスコア  
    s=n*i*100
    #全部解くとき、ボーナスもスコアに加える
    if n==L[i][0]:
        s+=L[i][1]
	#スコアに届かない時、届かない分はG-s点をi-1番目までで埋める
    if s<G:
        n+=f(G-s, i-1)
    #i-1番目までの方が少ない時はそっちを返す
    return min(n, f(G,i-1))
print(f(G, D))

Submission status: Accepted

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

ans = 10**9+7
#for i in range(2**D):
for i in range(1 << D):
  point = 0
  count = 0
  tmp = []
  #for ind, b in enumerate(format(i, 'b').zfill(D)):
    ##print(ind,b,i)
    #if(b == '1'):
  for j in range(D):
    if(((i >> j) & 1) == 1):
      point += pc[j][0] * 100 * (j + 1) + pc[j][1]
      count += pc[j][0]
    else:
      tmp.append(j)
  if(point < G):
    R = G - point
    k = tmp[-1]
    if((pc[k][0] - 1) * (k + 1) * 100 < R):
      continue
    count += -(-R // (100 * (k + 1)))
  ans = min(ans, count)
print(ans)

Submission status: Accepted

Solution code:
d,g=map(int,input().split())
data=[]
for i in range(d):
    p,c=map(int,input().split())
    data.append((p,c))
n=0
mn=99999999
while n<2**d:
    point=0
    count=0
    for i in range(d):
        if n&(1<<i):
            point+=data[i][0]*100*(i+1)+data[i][1]
            count+=data[i][0]
    if point<g:
        for i in range(d):
            i=d-1-i
            if not n&(1<<i):
                for j in range(data[i][0]-1):
                    point+=(i+1)*100
                    count+=1
                    if point>=g:
                        mn=min(mn,count)
                        break
                else:
                    break
                break
    else:
        mn=min(mn,count)
    n+=1
print(mn)

Submission status: Accepted

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

def function(G, i):
    # print("i:",i)
    if i==0:
	    return 1001
    n=min(G//(i*100), PC[i][0])
    # print("n:",n)
    s=n*i*100
    # print("s:",s)
    if n==PC[i][0]:
        s+=PC[i][1]
        # print("s:",s)
    if s<G:
        n+=function(G-s, i-1)
        # print("n:",n)
    return min(n, function(G,i-1))
print(function(G, D))

Submission status: Accepted

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

def dfs(g, i):
    if i == 0:
        return 10 ** 12
    
    cnt = min(g // (100 * i), PC[i][0])
    score = cnt * 100 * i
    
    if cnt == PC[i][0]:
        score += PC[i][1]
        
    if g > score:
        cnt += dfs(g - score, i - 1)
    
    return min(cnt, dfs(g, i - 1))

print(dfs(g, d))

Submission status: Accepted

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

def dfs(g, i):
    if i == 0:
        return 10 ** 12
    
    n = min(g // (100 * i), PC[i][0])
    score = n * 100 * i
    
    if n == PC[i][0]:
        score += PC[i][1]
        
    if g > score:
        n += dfs(g - score, i - 1)
        
    return min(n, dfs(g, i - 1))

print(dfs(g, d))

Submission status: Accepted

Solution code:
#!/mnt/c/Users/moiki/bash/env/bin/python
D,G = map(int, input().split())
points = [ [int(j) for j in input().split()] for _ in range(D)]
points = [ [x[0], x[1], 100*e*x[0]] for e,x in enumerate(points, 1)]

ans = float("inf")
for i in range(1<<D): # for complete bonus bit set 
    lg = G
    cnt = 0
    for d in range(D):
        if i & (1<<d) != 0:
            lg -= points[d][1] # complete bonus
            # lg -= (100*(d+1))*points[d][0] # normal points
            lg -= points[d][2] # normal points
            cnt += points[d][0]
            if lg <= 0:
                break
    if lg <= 0:
        ans = min(ans, cnt)
        continue
    
    # other points
    for d in range(D-1, -1, -1):
        if i & (1<<d) != 0: continue

        if lg <= points[d][2]:
            quot = (lg+(100*(d+1)-1)) // (100*(d+1)) # carryUp
            lg -= 100*(d+1)*quot
            cnt += quot;  break
        else:
            cnt += points[d][0]
            lg -= points[d][2]
    if lg <= 0:
        ans = min(ans, cnt)
        continue
print(ans)

Submission status: Accepted

Solution code:
#!/mnt/c/Users/moiki/bash/env/bin/python
D,G = map(int, input().split())
points = [ [int(j) for j in input().split()] for _ in range(D)]
points = [ [x[0], x[1], 100*e*x[0]] for e,x in enumerate(points, 1)]


ans = float("inf")
for i in range(1<<D): # for complete bonus bit set 
    lg = G
    cnt = 0
    for d in range(D):
        if i & (1<<d) != 0:
            lg -= points[d][1] # complete bonus
            lg -= (100*(d+1))*points[d][0] # normal points
            cnt += points[d][0]
            if lg <= 0:
                break
    if lg <= 0:
        ans = min(ans, cnt)
        continue
    
    # other points
    for d in range(D-1, -1, -1):
        if i & (1<<d) != 0: continue

        if lg <= points[d][2]:
            quot = (lg+(100*(d+1)-1)) // (100*(d+1))
            lg -= 100*(d+1)*quot
            cnt += quot;  break
        else:
            cnt += points[d][0]
            lg -= 100*(d+1)*points[d][0]
            cnt += points[d][0]
    if lg <= 0:
        ans = min(ans, cnt)
        continue
print(ans)

Submission status: Accepted

Solution code:
def solve(D, G, PCs):
    # print(D, ",", G, ",", PCs)
    ans = 10000
    for d in range(0, 2 ** D):
        b = "{:011b}".format(d)[::-1][:D]
        k = 0
        point = 0
        for i, c in enumerate(b):
            if c == "1":
                k += PCs[i][0]
                point += PCs[i][1] + ((i + 1) * 100 * PCs[i][0])
        if point >= G:
            ans = min(ans, k)
            continue

        for i, (p, c) in enumerate(PCs[::-1]):
            if b[D - (i + 1)] == "1":
                continue
            for _ in range(p):
                point += (D - i) * 100
                k += 1
                if point >= G:
                    break
            if point >= G:
                break
        ans = min(ans, k)
    return ans

if __name__ == "__main__":
    D, G = tuple(map(int, input().split(" ")))
    PCs = [tuple(map(int, input().split(" "))) for _ in range(D)]
    print(solve(D, G, PCs))

Submission status: Accepted

Solution code:
import itertools, math
d, g = map(int, input().split())
pc = [list(map(int, input().split())) for _ in range(d)]
ans = float('inf')
comb = list(itertools.product([0, 1], repeat=d))
for i in range(len(comb)):
    s = 0
    c = 0
    for j in range(d):
        if comb[i][j] == 1:
            s += pc[j][0] * (j + 1) * 100 + pc[j][1]
            c += pc[j][0]
    div = g - s
    if div <= 0:
        ans = min(ans, c)
        continue
    for j in range(d):
        tmpdiv = div
        tmpc = c
        if comb[i][j] == 0:
            cut = min(tmpdiv // math.ceil((j + 1) * 100), pc[j][0] - 1)
            tmpc += cut
            tmpdiv -= cut * (j + 1) * 100
            if tmpdiv <= 0:
                ans = min(ans, tmpc)
print(ans)

Submission status: Accepted

Solution code:
#2-1-1 #ABC104C
d,g = map(int,input().split())
q={}
comp={}
p={}
minsolve=0
for i in range(d):
    a,b=map(int,input().split())
    q[i]=a
    p[i]=100*(i+1)
    comp[i]=100*(i+1)*a+b
    minsolve+=a
    
solve=[0 for _ in range(d)]
def roop(s,check,point,solved,minsolve):
    solve=s.copy()
    solve2=s.copy()
    if check==d:
        if 0 in solve:
            solverev=solve.copy()
            solverev.reverse()
            idx=d-solverev.index(0)-1
            shold=max(0,1+(g-point-1)//p[idx])
            if q[idx]>shold and shold>=0:
                solved+=shold
                minsolve=min(minsolve,solved)
        return minsolve

    minsolve=roop(solve,check+1,point,solved,minsolve)
    solve2[check]+=1
    minsolve=roop(solve2,check+1,point+comp[check],solved+q[check],minsolve)
    return minsolve

print(roop(solve,0,0,0,minsolve))

Submission status: Accepted

Solution code:
d,g = map(int,input().split())
q={}
comp={}
p={}
minsolve=0
for i in range(d):
    a,b=map(int,input().split())
    q[i]=a
    p[i]=100*(i+1)
    comp[i]=100*(i+1)*a+b
    minsolve+=a
    
solve=[0 for _ in range(d)]
def roop(s,check,point,solved,minsolve):
    solve=s.copy()
    solve2=s.copy()
    if check==d:
        if point>g:
            minsolve=min(minsolve,solved)
            return minsolve
        if 0 in solve:
            solverev=solve.copy()
            solverev.reverse()
            idx=d-solverev.index(0)-1
            shold=1+(g-point-1)//p[idx]
            if q[idx]>shold and shold>=0:
                solved+=shold
                minsolve=min(minsolve,solved)
        return minsolve

    minsolve=roop(solve,check+1,point,solved,minsolve)
    solve2[check]+=1
    minsolve=roop(solve2,check+1,point+comp[check],solved+q[check],minsolve)
    return minsolve

print(roop(solve,0,0,0,minsolve))

Submission status: Accepted

Solution code:
import numpy as np
d, g = map(int ,input().split())
points = [list(map(int,input().split())) for _ in range(d)]

def min_q(comp_flg, target_score): # comp_flag[i]=True以外の問題iについて、compポイントを無視してtarget_scoreを超えるには最低いくつの問題数が必要かを返す
    score = 0
    q_num = 0
    for i in range(d-1,-1,-1):
        if comp_flg[i]:
            continue
        if target_score>score+points[i][0]*(i+1)*100:
            score += points[i][0]*(i+1)*100
            q_num += points[i][0] 
        else:
            q_num += np.ceil((target_score-score)/(100*(i+1)))
            break
    return q_num


mn = float('inf')
for i in range(1<<d):
    complete_flg = [False]*d
    tmp_q_num = 0
    tmp_point = 0
    for j in range(d):
        if i&(2**j) != 0:
            tmp_point += points[j][0] * 100*(j+1) + points[j][1]
            complete_flg[j] = True
            tmp_q_num += points[j][0]
    if tmp_point < g:
        tmp_q_num += min_q(complete_flg, g-tmp_point)
    if mn>tmp_q_num:
        mn = tmp_q_num

print(int(mn))

Submission status: Accepted

Solution code:
import math

D,G = map(int, input().split())
l=[list(map(int,input().split())) for i in range(D)]
lst=[[(i+1)*100]*(l[i][0]-1) + [(i+1)*100 + l[i][1]] for i in range(len(l))]
ans = 100*D
dis = 100000*D
for i in range(1<<D):
    point,num,maxp=0,0,0
    for j in range(D):
        if (i>>j)&1:
            num+=len(lst[j])
            point+=sum(lst[j])
        else:
            maxp=j
    if point + (maxp+1)*100*(len(lst[maxp])-1) >= G:
        mq = max(0,math.ceil((G-point)/((maxp+1)*100)))
        ans = min(ans, num+mq)
print(int(ans))

Submission status: Accepted

Solution code:
D,G=map(int,input().split())
p=[0]*D
c=[0]*D
ans=1000000000
for i in range(D):
    p[i],c[i]=map(int,input().split())
for i in range(1<<D):
    s=0
    cnt=0
    P=[0]*D
    for j in range(D):
        if ((i>>j)&1)==1:
            s+=c[j]+(j+1)*p[j]*100
            cnt+=p[j]
            P[j]=1
    m=-1
    for k in range(D):
        if m<0:
            if P[D-k-1]==0:
                m=D-k
        else:
            break
    if m>=0:
        for l in range(p[m-1]-1):
            if s<G:
                s+=m*100
                cnt+=1
    if s>=G and cnt<ans:
        ans=cnt
print(ans)

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(200000)


def input():
    return sys.stdin.readline()[:-1]


def ii(t: type = int):
    return t(input())


def il(t: type = int):
    return list(map(t, input().split()))


def imi(N: int, t: type = int):
    return [ii(t) for _ in range(N)]


def iml(N: int, t: type = int):
    return [il(t) for _ in range(N)]


def solve():
    D, G = il()
    PC = iml(D)
    ans = 999999999

    for i in range(1 << D):
        count = 0
        score = 0
        for j in range(D):
            if i >> j & 1:
                score += PC[j][1]
                score += PC[j][0] * (j + 1) * 100
                count += PC[j][0]

        for j in range(D - 1, -1, -1):
            if i >> j & 1:
                continue
            if score >= G:
                break
            g = (j + 1) * 100
            gg = (G - score + g - 1) // g
            score += min(gg, PC[j][0]) * g
            count += min(gg, PC[j][0])
        ans = min(ans, count)
    return ans


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

Submission status: Accepted

Solution code:
import math
d,g=map(int,input().split())
p=[]
p_=[]
c=[]
ans=float('inf')
for i in range(d):
    pi,ci=map(int,input().split())
    p.append(pi)
    p_.append(pi)
    c.append(ci)
for i in range(2**d):
    s_bit=[int(x) for x in list(format(i,'b'))]
    point=0
    number=0
    for j in range(len(s_bit)):
        point+=s_bit[len(s_bit)-1-j]*100*(j+1)*p[j]+s_bit[len(s_bit)-1-j]*c[j]
        number+=s_bit[len(s_bit)-1-j]*p[j]
        p_[j]=p[j]-p[j]*s_bit[len(s_bit)-1-j]
    if point>=g:
        ans=min(ans,number)
    else:
        remain=g-point
        for j in range(d):
            if 100*(j+1)*p_[j]>=remain:
                k=math.ceil(remain/(100*(j+1)))
                ans=min(ans,number+k)
print(ans)

Submission status: Accepted

Solution code:
d, g = list(map(int, input().split()))
spc = []
for s in range(100, d * 100 + 1, 100):
    p, c = list(map(int, input().split()))
    spc.append([s, p, c + s * p])

from itertools import product
ans = float('inf')
for comps in product(range(2), repeat=d):
    cnt = sum(p * x for (s, p, c), x in zip(spc, comps))
    scr = sum(c * x for (s, p, c), x in zip(spc, comps))
    if scr >= g:
        if cnt < ans:
            ans = cnt
        continue
    for (s, p, c), x in zip(spc, comps):
        if x or s * (p - 1) + scr < g:
            continue
        cnt += -((scr - g) // s)
        if cnt < ans:
            ans = cnt

print(ans)

Submission status: Accepted

Solution code:
d,g=map(int,input().split())
l=[list(map(int,input().split()))for _ in range(d)]
for i in range(d):
    s=l[i][0]*100*-~i
    l[i].append(s+l[i][1])
    l[i].append(s)
a=10**18
for i in range(1<<d):
    s=t=k=0
    for j in range(d):
        if (i>>j)&1:
            s+=l[j][2]
            t+=l[j][0]
        else:
            k=j
    if s+l[k][3]<g:continue
    if s<g:
        t+=-(-(g-s)//(100*-~k))
    a=min(a,t)
print(a)

Submission status: Accepted

Solution code:
# coding: utf-8

import sys
import math

import array
import bisect
import collections
from collections import Counter, defaultdict
import fractions
import heapq
import re

sys.setrecursionlimit(1000000)


def array2d(dim1, dim2, init=None):
    return [[init for _ in range(dim2)] for _ in range(dim1)]

def argsort(l, reverse=False):
    return sorted(range(len(l)), key=lambda i: l[i], reverse=reverse)

def argmin(l):
    return l.index(min(l))

def YESNO(ans, yes="YES", no="NO"):
    print([no, yes][ans])

II = lambda: int(input())
MI = lambda: map(int, input().split())
MIL = lambda: list(MI())
MIS = lambda: input().split()


def calc(bits, P, C, G):
    total = 0
    cnt = 0
    p = P[:]
    i = 0
    while bits > 0:
        if bits % 2:
            total += p[i] * (i + 1) * 100 + C[i]
            cnt += p[i]
            p[i] = 0
        bits >>= 1
        i += 1
    if total >= G:
        return cnt

    for i in range(len(p)-1, -1, -1):
        if p[i] != 0: break
    need = math.ceil((G - total) / ((i + 1) * 100))
    if need <= p[i]:
        return cnt + need
    return float("inf")



def main():
    D, G = MI()
    P = [None] * D
    C = [None] * D
    for i in range(D):
        P[i], C[i] = MI()

    ans = sum(P)
    for bits in range(2 << (D-1)):
        ans = min(ans, calc(bits, P, C, G))
    return ans



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

Submission status: Accepted

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

import itertools
import math

D, G = map(int, input().split())
ps, cs = [], []
for _ in range(D):
    p, c = map(int, input().split())
    ps.append(p)
    cs.append(c)

cps = list(itertools.product([True, False], repeat=D))
cps.pop(0) # Remove True all

ans = sum(ps)
for cp in cps:
    point, qs, maxp = 0, 0, 0
    for i in range(D):
        if cp[i]:
            point += (i + 1) * 100 * ps[i] + cs[i]
            qs += ps[i]
        else:
            maxp = i
    if point + (maxp + 1) * 100 * (ps[maxp] - 1) >= G:
        mq = max(0, math.ceil((G - point) / ((maxp + 1) * 100)))
        ans = min(ans, qs + mq)

print(ans)

Submission status: Accepted

Solution code:
D,G = list(map(int,input().split()))
P = []
C = []

for i in range(D):
    p,c = list(map(int,input().split()))
    P.append(p)
    C.append(c)

ans = 10000

for c in range(2**D):
    score = 0
    solved = 0
    remain = []
    for i,b in enumerate(format(c,'b').zfill(D)):
        if b == '1':
            score += P[i]*100*(i+1) + C[i]
            solved += P[i]
        else:
            remain.append(i)
    if score < G:
        R = G - score
        j = remain[-1]
        if (P[j]-1)*(j+1)*100 < R:
            continue
        solved += -(-R//(100*(j+1)))
    ans = min(solved, ans)

print(ans)

Submission status: Accepted

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


def f(d, g):
    if 0 > d:
        return 100 ** 10
    n = min(g // (100 * (d + 1)), PC[d][0])
    s = n * 100 * (d + 1)
    if n == PC[d][0]:
        s += PC[d][1]
    if g > s:
        n += f(d - 1, g - s)
    return min(n, f(d - 1, g))


def main():
    print(f(D - 1, G))


main()