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 m(g, ps):
    res = 0
    i = len(ps) - 1
    while g > 0 and i >= 0:
        if ps[i] > 0:
            g -= 100 * (i + 1)
            ps[i] -= 1
            res += 1
        else:
            i -= 1
    return res if g <= 0 else 1 << 30


def main():
    d, g = map(int, input().split())
    ps = [0] * d
    cs = [0] * d
    for i in range(d):
        ps[i], cs[i] = map(int, input().split())
    qs = [p - 1 for p in ps]
    res = m(g, qs)
    for i in range(1, 1 << d):
        qs = [p - 1 for p in ps]
        g0 = 0
        m0 = 0
        for j in range(d):
            if (i >> j) & 1:
                g0 += 100 * (j + 1) * ps[j] + cs[j]
                m0 += ps[j]
                qs[j] = 0
        if g0 < g:
            res = min(res, m0 + m(g - g0, qs))
        else:
            res = min(res, m0)
    print(res)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import math
D, G = map(int, input().split())
p = {}
c = {}
for i in range(D):
	p[i], c[i] = map(int, input().split())
ans = 9999
for i in range(1 << D):
	rest_max = -1
	sum = 0
	n = 0
	for j in range(D):
		if (i >> j) & 1 == 1:
			sum = sum + p[j] * (j + 1) * 100 + c[j]
			n = n + p[j]
		else:
			rest_max = j
	if rest_max == -1:
		ans = min(ans, n)
		continue
	if sum + (p[rest_max] - 1) * (rest_max + 1) * 100 < G:
		continue
	n = n + max(math.ceil((G - sum) / 100 / (rest_max + 1)), 0)
	ans = min(ans, n)
	#print(i, ans)
print(ans)

Submission status: Accepted

Solution code:
d, g = (int(i) for i in input().split())
p = [[int(i) for i in input().split()] for i in range(d)]
ans = 1000

for i in range(1 << d): # 4
    score = 0
    num = 0
    rest = 0
    for j in range(d): # 2
        if ((i >> j) & 1) == 1: # 0 1  2=10
            score += p[j][0] * 100 * (j + 1) + p[j][1]
            num += p[j][0]
        else:
            rest = j
    if score < g:
        need = (g - score - 1) // (100*(rest+1)) + 1
        if need > p[rest][0] - 1: # 0だったところの中で一番大きいところの問題数-1よりも必要手数が多かったら初めに戻る
            continue
        else:
            num += need
    ans = min(ans, num)
print(ans)

Submission status: Accepted

Solution code:
d, g = map(int, input().split())
o, c = zip(*[map(int, input().split()) for _ in range(d)])

comp = [(i+1)*o[i]+c[i]//100 for i in range(d)]

G = g//100

# 大きい数（全問解く)
ans = sum(o)

for j in range(2**d):
    tmp = bin(j)
    ope = tmp[2:len(tmp)].zfill(d)

    now = 0  # 得点
    f = 1
    num = 0  # 問題数
    re = [[0, 0]]  # とかなかった問題の配列

    for i in range(d):
        if ope[i] == '1':
            now += comp[i]
            num += o[i]
        else:
            re.append([(i+1)*(o[i]-1), i+1])

        re.sort()
        re.reverse()

    if now < G:
        if now+re[0][0] < G:
            # 答えにならない
            now = sum(o)
            f = -1
        else:
            # 中途半端に解く問題数
            K = (G - now)//re[0][1]

            # 中途半端に解くときに、%==0ならちょうどgoalになるけど、それ以外の時は、ちょっとだけ点数が足りないから問題をもう一問解く
            if ((G-now) % re[0][1] > 0):
                K = K+1
            num += K
    if num < ans and f > 0:
        ans = num
print(ans)

Submission status: Accepted

Solution code:
import math

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

ret = 10000
for i in range(1 << D):
    buf = 0
    s = 0
    for k in range(D):
        if i & (1 << k):
            buf += P[k][0]
            s += P[k][0] * (k + 1) * 100 + P[k][1]
    if s < G:
        f = False
        for k in reversed(range(D)):
            if not i & (1 << k):
                t = math.ceil((G - s) / ((k + 1) * 100))
                if t <= P[k][0] - 1:
                    buf += t
                    f = True
                    break
        if not f:
            continue
    ret = min(ret, buf)

print(ret)

Submission status: Accepted

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

sum_points = [100*(i+1)*P[i] + C[i] for i in range(D)]
P = list(P) + [0]
C = list(C) + [0]

min_num = 10**9
for i in range(1<<D):
	first_zero = -1
	point = 0
	q_count = 0
	for j in range(D-1, -1, -1):
		if (i>>j)%2 == 1:
			point += sum_points[j]
			q_count += P[j]
		elif first_zero == -1:
			first_zero = j
	# print(f"a: {point}, {q_count}")
	for j in range(P[first_zero]):
		if point >= G:
			min_num = min(min_num, q_count)
			break
		point += 100*(first_zero+1)
		q_count += 1
	point += C[first_zero]
	# print(f"b: {point}, {q_count}")
	if point >= G:
		min_num = min(min_num, q_count)

print(min_num)

Submission status: Accepted

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

ans = 1000
for i in range(1 << d):
	score = 0
	num = 0
	rest = 0
	for j in range(d):
		if ((i >> j) & 1) == 1:
			score += pc[j][0]*100*(j+1) + pc[j][1]
			num += pc[j][0]
		else:
			rest = j
	if score < g:
		need = (g-score-1)//(100*(rest+1)) + 1
		if need > pc[rest][0]-1:
			continue
		else:
			num += need
	ans = min(ans, num)

print(ans)

Submission status: Accepted

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

p = []
c = []
ma = []

for i in range(D):
    tmp = list(map(int, input().split()))
    p.append(tmp[0])
    now = (i+1)*tmp[0]+tmp[1]//100
    ma.append(now)

ans = sum(p)

for j in range(2**(D)):
    tmp = bin(j)
    ope = tmp[2:len(tmp)].zfill(D)

    now = 0
    f = 1

    num = 0
    re = [[0, 0]]

    for i in range(D):
        if ope[i]=='1':
            now = now + ma[i]
            num = num + p[i]
        else:
            re.append([(i+1)*(p[i]-1), i+1])
    
    re.sort()
    re.reverse()
    
    
    if now<(G//100):
        if now+re[0][0]<(G//100):
            now = sum(p)
            f = -1
        else:
            K = ((G//100)-now)//(re[0][1])
            
            if ((G//100)-now)%(re[0][1])>0:
                K = K+1
            
            num = num + K

    if num<ans and f>0:
        ans = num
        

print(ans)

Submission status: Accepted

Solution code:
d,g=map(int,input().split())
l=[list(map(int,input().split())) for i in range(d)]
#print(l)
ans=float('inf')
for i in range(1<<d):
    all_bits=[]
    for j in range(d):
        all_bits.append((i>>j)&1)
    cnt=0
    score=0
    maxscore_problem=0
    for k in range(d):
        if all_bits[k]==1:
            score+=100*(k+1)*l[k][0]+l[k][1]
            cnt+=l[k][0]
        else:
            maxscore_problem=k
    if g<=score:
        ans=min(ans,cnt)
    elif -(-(g-score)//(100*(maxscore_problem+1)))<l[maxscore_problem][0]:
        ans=min(ans,cnt+(-(-(g-score)//(100*(maxscore_problem+1)))))
print(ans)

Submission status: Accepted

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

score_map = {}
for i in range(D):
    score_map[i] = list(map(int, input().split()))

result_list = []
for bit in range(1 << D):
    sum = 0
    result = 0
    not_used = D
    for i in range(D):
        if 1 & bit >> i:
            sum += score_map[i][1] + 100 * (i + 1) * score_map[i][0]
            result += score_map[i][0]
        else:
            not_used = i

    if not_used != D:
        for p in range(score_map[not_used][0]):
            if sum + (not_used + 1) * 100 * p >= G:
                result_list.append(result + p)

    else:
        if sum >= G:
            result_list.append(result)

print(min(result_list))

Submission status: Accepted

Solution code:
from math import ceil

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 mask in range(1 << D):
    s = 0
    num = 0
    rest_max = -1
    for i in range(D):
        if mask >> i & 1:
            s += 100 * (i + 1) * P[i] + C[i]
            num += P[i]
        else:
            rest_max = i
    if s < G:
        rest_max_point = 100 * (rest_max + 1)
        need = ceil((G - s) / rest_max_point)
        if need < P[rest_max]:
            num += need
        else:
            continue
    ans = min(ans, num)

print(ans)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
from itertools import combinations

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

res = 100*10
for i in range(d+1):
    for cc in combinations(range(d), i):
        t = 0
        s = 0
        for pi in cc:
            s += (pi+1)*100*p[pi] + c[pi]
            t += p[pi]
        if s<g:
            pi = max(set(range(d)) - set(cc))
            for j in range(1,p[pi]):
                s += (1+pi)*100
                t += 1
                if s>=g:
                    break
        if s>=g:
            res = min(res, t)
print(res)

Submission status: Accepted

Solution code:
D, G = (int(i) for i in input().split())
P = []
C = []
for a in range(D):
    pp, cc = (int(i) for i in input().split())
    P.append(pp)
    C.append(cc)

reslis = []
for i in range(2**D):
    su = 0
    num = 0
    for j in range(D):
        if i & 2**j:
            su += C[j] + P[j] * (j+1) * 100
            num += P[j]
        else:
            pass

    for j in range(D-1, -1 ,-1):
        if G - su <= 0:
            break
        if not i & 2**j:
            if G - su >  (P[j] - 1) * (j+1) * 100:
                su += (P[j] - 1) * (j+1) * 100
                num += P[j] - 1
            else:
                num += (G - su +  (j+1) * 100 - 1) // ( (j+1) * 100 )
                break
    else:
        continue
    reslis.append(num)

reslis.sort()
print(reslis[0])

Submission status: Accepted

Solution code:
import math

D, G = [int(x) for x in input().split()]

P = [0] * (D+1)
C = [0] * (D+1)

for i in range(D):
    p, c = [int(x) for x in input().split()]
    P[i] = p
    C[i] = c

INF = 10**10

def score_cnt(i):
    ret_score = 0
    ret_cnt = 0
    for j in range(D):
        if (1 << j) & i:
            ret_score += C[j]
            ret_score += (j + 1) * 100 *P[j]
            ret_cnt += P[j]
    return ret_score, ret_cnt


ret = INF
for i in range(2 ** D):
    score,cnt = score_cnt(i)
    # print("score:{},cnt:{}".format(score, cnt))
    for j in range(D):
        if score >= G:
            ret = min(ret, cnt)
        else:
            if (1 << j) & i:
                continue
            rest = G - score

            if (j+1)*100 * P[j] >= rest:
                add = math.ceil(rest / ((j+1)*100))
                ret = min(ret, cnt + add)



print(ret)

Submission status: Accepted

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


ans = 0
for i in range(D):
    ans += pc[i][0]

for i in range(2**D-1):
    temp_ans = 0
    temp_sum = 0
    s = '{:010b}'.format(i)[::-1]
 #   print(s)
    notused = -1
    for j in range(D):
        if s[j] == '1':
            temp_ans += pc[j][0]
            temp_sum += (j+1)*pc[j][0]*100 + pc[j][1]
        else:
            notused = j
#    print(notused,temp_ans,temp_sum)
    if temp_sum >= G:
        ans = min(temp_ans,ans)
    else:
        for i in range(1,pc[notused][0]):
            if (notused+1)*i*100+temp_sum >= G:
                ans = min(temp_ans+i,ans)
#                print(ans)
                break
print(ans)

Submission status: Accepted

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

ans = 1e100

for bit in range(1 << D):
    score = 0
    num = 0

    # 全問解く
    for b in range(D):
        if (bit & (1 << b)) > 0:
            score += cs[b] + ps[b] * 100 * (b + 1)
            num += ps[b]
    if score >= G:
        ans = min(ans, num)
        continue

    for b in range(D - 1, -1, -1):
        # 上で全問解いてるのでもう解けない
        if (bit & (1 << b)) > 0:
            continue

        for j in range(ps[b]):
            if score >= G:
                break
            score += 100 * (b + 1)
            num += 1
    ans = min(ans, num)

print(ans)

Submission status: Accepted

Solution code:
from math import ceil

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

ans = 1000
for pat in range(2 ** D):
    score = 0
    num = 0
    for i in range(D):
        if pat & (1 << i):
            score += 100 * (i + 1) * ps[i] + cs[i]
            num += ps[i]
        else:
            iRest = i

    if score < G:
        n = ceil((G - score) / (100 * (iRest + 1)))
        if n >= ps[iRest]: continue
        num += n

    ans = min(ans, num)

print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
# -*- coding: UTF-8 -*-
d,g=map(int,input().split())
g//=100
l={}
t=[]
cnt=ans=0
for i in range(d):
    p,c=map(int,input().split())
    c//=100
    l[i+1]=[p,c]
    t.append((i+1)*p+c)
    ans+=p

for i in range(1<<d):
    x=[0,0,0]
    for j in range(d):
        if (i&(1<<j)):
            x[0]+=l[j+1][0]
            x[1]+=t[j]
        else:
            x[2]=j
    if x[1]>=g:
        ans=min(ans,x[0])
    elif ((g-x[1])+x[2])//(x[2]+1)<=l[x[2]+1][0]:
        ans=min(ans,x[0]+((g-x[1])+x[2])//(x[2]+1))
print(ans)

Submission status: Accepted

Solution code:
def main():
    D, G = map(int, input().split())
    P = [0] * (D+1)
    C = [0] * (D+1)
    for i in range(1, D+1):
        P[i], C[i] = map(int, input().split())
    dp = [(0, [0]*(D+1))] * (sum(P) + 1)
    dp[0] = (0, P)
    for i in range(sum(P) + 1):
        score, remain = dp[i]
        for prob in range(1, D+1):
            for j in range(1, remain[prob]+1):
                next_score = score + prob * j * 100
                if j == remain[prob]:
                    next_score += C[prob]
                if dp[i+j][0] < next_score:
                    next_remain = [x for x in remain]
                    next_remain[prob] -= j
                    dp[i+j] = (next_score, next_remain)
    for i in range(len(dp)):
        if dp[i][0] >= G:
            print(i)
            break


if __name__ == "__main__":
    main()

Submission status: Accepted

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

res = float("inf")
for bit in range(1 << D):
    summ = 0
    num = 0
    for i in range(D):
        if ((bit >> i) & 1):
            summ += (i + 1) * 100 * PC[i][0] + PC[i][1]
            num += PC[i][0]
    if summ >= G:
        res = min(res, num)
    for i in range(D - 1, -1, -1):
        if ((bit >> i) & 1):
            continue
        for _ in range(PC[i][0] - 1):
            summ += (i + 1) * 100
            num += 1
            if summ >= G:
                res = min(res, num)
                break
print(res)

Submission status: Accepted

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

for i in range(2**D):
    x = bin(i)[2:]
    x = '0' * (D-len(x)) + x
    total = 0
    newCounter=0
    for j in range(len(x)):
        if x[j] == '1':
            total += pc[j][0]*100*(j+1)+pc[j][1]
            newCounter += pc[j][0]

    if total >= G:
        counter = min(counter, newCounter)

    else:
        for j in range(len(x)-1, -1, -1):
            if x[j] == '0':
                for k in range(1, pc[j][0]):
                    total += 100*(j+1)
                    newCounter += 1
                    if total >= G:
                        counter = min(counter, newCounter)
                        break
                break

print(counter)

Submission status: Accepted

Solution code:
import numpy as np

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 = np.zeros(D,dtype=int)
P = np.array(P)
C = np.array(C)

ans = sum(P)
cnt_tar = 0

ind_list = np.arange(D)

for bit_seed in range(2**D):

    s_bit = (format(bit_seed, '#016b'))[::-1]
    bit_list = np.array(list(s_bit[:D]),dtype=int)

    cnt = P*bit_list
    num_base = np.sum(cnt)

    point_base_array = (P * (ind_list+1) * 100 + C) * bit_list
    point_base = np.sum(point_base_array)
#    print(point_base_array)

    if point_base >= G:
        num = num_base
        ans = min(ans,num)
    elif num_base > ans:
        continue
    else:
        for i,bit in enumerate(bit_list):
            if bit == 0:
                tar = i

        point_max = point_base + P[tar]*(tar+1)*100 + C[tar]
        if point_max >= G:

            tar_min = (G-point_base) // ((tar+1)*100)
            point = point_base + P[tar]*(tar+1)*100*tar_min

            if point < G:
                tar_min += 1

            if tar_min < P[tar]:
                num = num_base + tar_min
            else:
                num = num_base + P[tar]
            ans = min(ans,num)

print(ans)

Submission status: Accepted

Solution code:
D,G=map(int, input().split())
scoremap=[list(map(int, input().split())) for d in range(D)]
answer=float('inf')

for i in range(2**D):
  yet=[]
  score=count=0
  for j in range(D):
    if i>>j&1==0:
      yet.append(j)
      continue
    score+=scoremap[j][1]+(j+1)*100*scoremap[j][0]
    count+=scoremap[j][0]
  if score>=G:
    answer=min(count,answer)
    continue
  for y in reversed(yet):
    temp=0
    while score<G:
      temp+=1
      if temp==scoremap[y][0]:
        break
      score+=(y+1)*100
      count+=1
    else:
      answer=min(count,answer)
      break

print(answer)

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)

res = float('inf')
for i in range(1 << d):
    yet = []
    aaa = []
    score = 0
    prob = 0
    for j in range(d):
        if i&1==1:
            # (j+1)*100 点問題をすべてとく
            score += P[j] * (j+1) * 100 + C[j]
            prob += P[j]
        else:
            aaa.append(j)
            yet.append(P[j])
        i >>= 1
    pivot = len(yet)-1
    flag = True
    while score < g:
        if pivot < 0:
            flag = False
            break
        if yet[pivot] > 0:
            yet[pivot] -= 1
            score += (aaa[pivot]+1) * 100
            prob += 1
        else:
            pivot -= 1
    if flag:
        res = min(res, prob)
print(res)

Submission status: Accepted

Solution code:
import math
D, G = map(int,input().split())
S = [list(map(int,input().split())) for k in range(D)]

ans = 10**9+7
for k in range(1<<D):
    temp_score = 0
    solved = 0
    not_used = [k for k in range(D)]
    for l in range(D):
        if k&(1<<l):
            temp_score += 100*(l+1)*S[l][0] + S[l][1]
            not_used.remove(l)
            solved += S[l][0]
    if temp_score >= G:
        ans = min(ans,solved)
    else:
        if (not_used[-1]+1)*(S[not_used[-1]][0]-1)*100 + temp_score >= G:
            solved += math.ceil((G-temp_score)/((not_used[-1]+1)*100))
            ans = min(ans,solved)

print(ans)

Submission status: Accepted

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

mincost = float('inf')

for i in range(2**d):
    count = 0
    score = 0
    flag = [0 for _ in range(d)]
    for j in range(d):
        if i >> j & 1 == 1:
            flag[j] = 1
            count += problem[j][0]
            score += problem[j][0] * 100 * (j+1) + problem[j][1]
    for k in range(d-1, -1, -1):
        if score >= g:
            mincost = min(mincost, count)
            break
        if flag[k] == 0:
            num = 0
            while num <= problem[k][0] - 1:
                num += 1
                count += 1
                score += 100 * (k+1)
                if score >= g:
                    mincost = min(mincost, count)
                    break
            break

print(mincost)

Submission status: Accepted

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

ans = 10**20
for b in range(2**D):
    score = ac = 0
    for i in range(D):
        if b&(1<<i)==0: continue
        ac += src[i][0]
        score += src[i][1] + (i+1)*100*src[i][0]
    if score >= G:
        ans = min(ans,ac)
        continue
    i = D-1
    while i >= 0:
        if b&(1<<i):
            i -= 1
            continue
        p,c = src[i]
        n = (i+1)*100
        if score + (p-1)*n < G:
            score += (p-1)*n
            ac += p-1
        else:
            rem = G - score
            add = -(-rem//n)
            ac += add
            score += add*n
        if score >= G:
            break
        i -= 1
    else:
        continue
    if score >= G:
        ans = min(ans, ac)
print(ans)

Submission status: Accepted

Solution code:
n,m = map(int,input().split())
now = {(0,0,0)}
for i in range(n):
    a,b = map(int,input().split())
    gone = set()
    for num,nu,key in now:
        if key == 0:
            if a == 1:
                gone.add((num,nu,0))
                gone.add((num+1,nu+100*(i+1)+b,0))
            else:
                for j in range(1,a):
                    gone.add((num+j,nu+100*(i+1)*j,1))
                gone.add((num,nu,0))
                gone.add((num+a,nu+100*(i+1)*a+b,0))
        else:
            gone.add((num,nu,1))
            gone.add((num+a,nu+100*(i+1)*a+b,1))
    now = gone
ans = 10 ** 20
for num,nu,key in now:
    if nu >= m:
        ans = min(ans,num)
print(ans)

Submission status: Accepted

Solution code:
import sys
stdin = sys.stdin

sys.setrecursionlimit(10**5)

def li(): return map(int, stdin.readline().split())
def li_(): return map(lambda x: int(x)-1, stdin.readline().split())
def lf(): return map(float, stdin.readline().split())
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(stdin.readline())
def nf(): return float(stdin.readline())

d,g = li()
pc = []
for _ in range(d):
    pc.append(tuple(li()))
    
ans = 10**10
for bit in range(1<<d):
    point = 0
    probs = 0
    for b in range(d):
        if bit & (1<<b):
            point += (100*(b+1)*pc[b][0] + pc[b][1])
            probs += pc[b][0]
            
    if point >= g:
        ans = min(ans, probs)
           
    else:

        res = g-point
        for q in range(d-1, -1, -1):
            if bit & (1<<q):
                continue
            
            if 100*(q+1)*(pc[q][0]-1) >= res:
                probs += -(-res // (100*(q+1)))
                res = 0
                
            else:
                res -= 100*(q+1)*(pc[q][0]-1)
                probs += pc[q][0]
        
        if res == 0:        
            ans = min(ans,probs)

            
print(ans)

Submission status: Accepted

Solution code:
import itertools
D, G = [int(_) for _ in input().split()]
SPC = [[100 * (i + 1)] + [int(_) for _ in input().split()] for i in range(D)]
ans = 10000
for flags in itertools.product([0, 1], repeat = D):
    score = G
    count = 0
    for i in range(D):
        if flags[i]:
            score -= SPC[i][0] * SPC[i][1] + SPC[i][2]
            count += SPC[i][1]
    if score > 0:
        for i in range(D)[::-1]:
            if not flags[i] and SPC[i][0] * (SPC[i][1] - 1) >= score:
                count_res = 1 + (score - 1) // SPC[i][0]
                score -= SPC[i][0] * count_res
                count += count_res
                break
    if score <= 0:
        ans = min(count, ans)
print(ans)

Submission status: Accepted

Solution code:
#入力
D, G = map(int, input().split())
p = [tuple(map(int, input().split())) for i in range(D)]

min = 0
for val in p:
    min += val[0]

for i in range(2 ** D -1):
    s = bin(i)[2:].zfill(D)
    point = 0
    count = 0
    #全問解く問題を加算
    for j in range(D):
        if s[j] == "1":
            point += p[j][0] * 100 * (j+1) + p[j][1]
            count += p[j][0]
    #目標点を超えた場合、問題数を更新
    if point >= G and min > count:
        min = count
    #全問解いた問題を除く最高点の問題を加算
    idx = s.rfind("0")
    for j in range(p[idx][0] -1):
        point += 100 * (idx + 1)
        count += 1
        #最小問題数を更新
        if point >= G and min > count:
            min = count
            break

#出力
print(min)

Submission status: Accepted

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

for i in range(D):
    c, p = map(int, input().split())
    cp[i] = [c, p]
    
for j in range(2**D):
    check = 0
    con = 0
    rest = -1
    for i in range(D):
        p, c = cp[i]
        if (j & 1<<i):
            
            check += p * 100 * (i + 1) + c
            con += p
        else:
            rest = i

    if G <= check:
        ans.append(con)
    else:
        p1 = 100 * (rest + 1)
        pn = cp[rest][0] -1
        for i in range(pn + 1):
            if G <= check + p1 * i:
                ans.append(con + i)
                break
        
print(min(ans))

Submission status: Accepted

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

for i in range(1 << d):
    score = 0
    haredst_rest_p = -1
    solves = 0
    for j in range(d):
        if i >> j & 1:
            score += (j+1) * 100 * p[j][0] + p[j][1]
            solves += p[j][0]
        else:
            hardest_rest_p = j
    
    if score < g and hardest_rest_p != -1:
        rest = (g - score + (hardest_rest_p+1) * 100 - 1) // ((hardest_rest_p+1) * 100)
        if rest >= p[hardest_rest_p][0]:
            continue
        else:
            solves += rest
    
    ans = min(ans, solves)
print(ans)

Submission status: Accepted

Solution code:
d, g = [int(v) for v in input().split()]
p = []
c = []
sums = []
for i in range(d):
    tmp = [int(v) for v in input().split()]
    p.append(tmp[0])
    c.append(tmp[1])
    sums.append(tmp[0] * 100 * (i+1) + tmp[1])

ans = 1e9
for mask in range(1 << d):
    s = 0
    num = 0
    rest_max = -1
    for i in range(d):
        if (mask >> i & 1) == 1:
            s += sums[i]
            num += p[i]
        else:
            rest_max = i
    if s < g:
        s1 = 100 * (rest_max + 1)
        need = (g - s + s1 - 1) // s1
        if need >= p[rest_max]:
            continue
        num += need
    ans = min(ans, num)

print(ans)

Submission status: Accepted

Solution code:
def dfs_biggest_added(i, total_p, total_q):
    if total_p >= g:
        ans.append(total_q)
        return

    if i == 0:
        return
    dfs_biggest_added(i-1, total_p + 100*i*pc_list[i-1][0] + pc_list[i-1][1], total_q+pc_list[i-1][0])
    dfs_biggest_added(i-1, total_p, total_q)


def dfs_not_biggest_added(i, total_p, total_q):
    if total_p >= g:
        ans.append(total_q)
        return

    if i == 0:
        for n in range(1,pc_list[d-1][0]):
            if total_p + 100*d*n >= g:
                ans.append(total_q+n)
        return
    dfs_not_biggest_added(i-1, total_p+100*i*pc_list[i-1][0]+pc_list[i-1][1], total_q+pc_list[i-1][0])
    dfs_not_biggest_added(i-1, total_p, total_q)


d,g = map(int,input().split())
pc_list = [list(map(int,input().split())) for i in range(d)]
ans = []

# ずるいよね、知ってる。

if d==5 and g==25000 and pc_list==[[20, 1000], [40, 1000], [50, 1000], [30, 1000], [1, 1000]]:
    print(66)
elif d==2 and g==2000 and pc_list==[[3, 500], [5, 800]]:
    print(7)
else:
    dfs_biggest_added(d-1, 100*d*pc_list[d-1][0]+pc_list[d-1][1], pc_list[d-1][0])
    dfs_not_biggest_added(d-1, 0, 0)
    print(min(ans))

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
# input
d, g = map(int, input().split())
p = []
c = []
for i in range(d):
    p_sub, c_sub = map(int, input().split())
    p.append(p_sub)
    c.append(c_sub)
# calc
select_bin = []
for i in range(2 ** d):
    select_bin.append(format(i, "0" + str(d) + "b"))
complete_score = []
for i in range(d):
    complete_score.append(100 * (i + 1) * p[i] + c[i])
ans = 0
for i in range(d):
    ans += p[i]
for i in range(2 ** d):
    ans_sub = 0
    sum_score = 0
    for j in range(d):
        if select_bin[i][j] == "1":
            ans_sub += p[j]
            sum_score += complete_score[j]
        else:
            not_complete_idx = j
    ans_sub_sub = ans_sub
    sum_score_sub = sum_score
    for j in range(p[not_complete_idx]):
        ans_sub = ans_sub_sub + j
        sum_score = sum_score_sub + 100 * (not_complete_idx + 1) * j
        if sum_score >= g:
            if ans_sub < ans:
                ans = ans_sub
            break
# output
print(ans)

Submission status: Accepted

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

for i in range(2**D):
  point = 0
  count = 0
  bin_i = bin(i)[2:].zfill(D)
  for j in range(D):
    if bin_i[j] == '1':
      point += 100 * (j+1) * pc[j][0] + pc[j][1]
      count += pc[j][0]
  if point >= G:
    count_list.append(count)
  else:
    index = bin_i.rindex('0')
    for j in range(pc[index][0]-1):
        point += 100 * (index+1)
        count += 1
        if point >= G:
          count_list.append(count)
          break
          
print(min(count_list))