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

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


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


import itertools
bitlist=list(itertools.product((0,1),repeat=D))

def xx(a):
    XX=[0 for i in range(D)]
    for i in range(len(a)):
        if a[i]==1:
            XX[i]=score[i][0]
    return XX


def scoresolve(X):
    ANS=0
    for i in range(len(X)):
            ANS+=X[i]*(i+1)*100
            if X[i]==score[i][0]:
                ANS+=score[i][1]

    return ANS





ANS=100000
for bit in bitlist:
    ii=xx(bit)
    if scoresolve(ii)>=G:
        ANS=min(ANS,sum(ii))
    else:
        j=D-ii[::-1].index(0)-1
        if G-scoresolve(ii)<=(j+1)*100*score[j][0]:
            ANS=min(ANS,sum(ii)+math.ceil((G-scoresolve(ii))/(j+1)/100))

print(ANS)

Submission status: Accepted

Solution code:
def i1():
 return int(input())
def i2():
 return [int(i) for i in input().split()]
[d,g]=i2()
e=[0 for i in range(1001)]

for i in range(1,d+1):
 [p,c]=i2()
 ee=e[:]
 for j in range(p-1):
   for k in range(1000)[::-1]:
    if e[k]>0 or k==0:
      e[k+1]=max(e[k+1],e[k]+100*i)
 
 for k in range(1001-p)[::-1]:
      if(ee[k]>0 or k==0):
        ee[k+p]=max(ee[k+p],ee[k]+100*i*p+c)
        e[k+p]=max(e[k+p],ee[k+p])
 
 
for i in range(1001):
 if e[i]>=g:
    print(i)
    break

Submission status: Accepted

Solution code:
def can(d,g,p,c, maxPick):
	# n問解いてg点獲得できるか？

	# パーフェクトを狙う問題の組み合わせを生成
	for i in range(0, 2**(d-1)):

		# このパーフェクトのとり方で条件が達成できるか？
		point = 0
		picked = 0
		for j in range(0, d-1):
			if i & (2**j) != 0:
				point += (j+1) * 100 * p[j] + c[j]
				picked += p[j]

		if picked > maxPick:
			#print (i, " is un")
			continue
		#print ("i", i , "picked", picked, "point", point)

		# 残り個数分だけ、点数の高い問題をとる
		t = d-1
		while(picked < maxPick):
			if i & (2**t) != 0:
				t -= 1
				continue
			pick = min(p[t], (maxPick - picked))
			picked += pick
			point += (t+1)*100 * pick
			if pick == p[t]:
				point += c[t]
			#print ("t", t, "pick", pick, "picked", picked, "point", point)
			t -= 1

		if point >= g:
			return True
		else:
			pass
			#print (point)
	return False


def bin(d,g,p,c):
	left = 1
	right = sum(p)
	while left != right:
		cen = (left + right) // 2
		#print ("left", left, "cen", cen, "right", right)
		if(can(d,g,p,c,cen)):
			right = cen
		else:
			left = cen + 1
	return right


s = input().split(" ")
d = int(s[0])
g = int(s[1])

p = []
c = []

for i in range(0, d):
	s = input().split(" ")
	p.append(int(s[0]))
	c.append(int(s[1]))

print(bin(d,g,p,c))

Submission status: Accepted

Solution code:
from collections import deque
D,G = [int(i) for i in input().split()]
P = [0]*D
n = 0
for i in range(D):
    p,c = [int(j) for j in input().split()]
    P[i] = [int(k) * 100 * (i+1) for k in range(p+1)]
    P[i][-1] += c
    n += p
deq = deque()
ans = n
deq.append((0,0,0))
dic = {}

while(len(deq)>0):
    tmp = deq.pop()
    if tmp[0]+1 > len(P):
        break
    for i,j in enumerate(P[tmp[0]]):
        cand = (tmp[0]+1, tmp[1]+i, tmp[2]+j)
        if cand[1] < ans:
            if cand[2] < G:
                if cand[1] not in dic:
                    dic[cand[1]] = cand[2]
                    deq.appendleft(cand)
                elif dic[cand[1]] <= cand[2]:
                    dic[cand[1]] = cand[2]
                    deq.appendleft(cand)
            else:
                ans = cand[1]
print(ans)

Submission status: Accepted

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

import math

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

p = []
c = []
done = [False for _ in range(d)]
avg = {}

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


res = 100000000

for i in range(1<<(d)):
    cnt = 0
    val = 0
    enabled = []
    for j in range(d):
        if i & (1 << (j)) > 0:
            enabled.append(j)
    enabled.reverse()

    for j in enabled:
        if val >= g:
            break
        cnt += p[j]
        val += (j + 1) * 100 * p[j] + c[j]
    
    for j in range(d):
        if val >= g:
            break
        idx = d - 1 - j
        if idx in enabled: continue
        if val + (idx + 1) * 100 * p[idx] < g:
            continue
        tmp = math.ceil((g - val) // ((idx + 1) * 100))
        cnt += tmp
        val += tmp * (idx + 1) * 100

    if val < g:
        cnt = 100000000
    if cnt < res:
        res = cnt

print(res)

Submission status: Accepted

Solution code:
d, g = [int(i) for i in input().split()]
p = [[0 for j in range(3)] for i in range(d)]
for i in range(d):
    p[i][1], p[i][2] = [int(i) for i in input().split()]
    p[i][0] = 100*(i+1)
p = sorted(p)
min_num = 10000000
bit = [0 for i in range(d)]
flag = 0
for i in range(2 ** d):
    flag = 0
    sum = 0
    num = 0
    tmp = i
    for j in range(d):
        bit[j] = tmp % 2
        tmp = int(tmp/2)
    for j in range(d):
        if bit[j] == 1:
            num += p[j][1]
            sum += p[j][1]*p[j][0] + p[j][2]
    #print("sum:{} num:{} bit:{}".format(sum,num,bit))
    if sum >= g:
        if num < min_num:
            min_num = num
            #print(num)
            continue
    else:
        res = g - sum
        for j in range(d):
            if bit[j] == 0:
                if res < p[j][0]*p[j][1]:
                    for k in range(p[j][1]-1):
                        #print("sum:{} num:{} bit:{}".format(sum, num, bit))
                        num += 1
                        sum += p[j][0]
                        res -= p[j][0]
                        if res <= 0:
                            if num < min_num:
                                min_num = num
                            break
print(min_num)

Submission status: Accepted

Solution code:
from itertools import product
D,G = map(int,input().split())
p,c = [0]*D,[0]*D
for i in range(D):
  p[i],c[i] = list(map(int,input().split()))
m = 10*100*10
for a in product([True,False], repeat=D):
  g,n = G,0
  for i in range(D):
    if a[i]:
      n += p[i]
      g -= (c[i]+(i+1)*100*p[i])
  if g <= 0 and n <= m:
    m = n
    continue
  elif m < n:
    continue
  for i in range(D):
    if a[i]:
      continue
    if g > (i+1)*100*(p[i]-1):
      continue
    n += (g+(i+1)*100-1) // ((i+1)*100)
    if n < m:
      m = n
print(m)

Submission status: Accepted

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

p = [0 for i in range(10)]
c = [0 for i in range(10)]


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

# print(D, G, p, c)

S = [0 for i in range(10)]
for i in range(D):
    S[i] = 100 * (i + 1) * p[i] + c[i]

a = [0 for i in range(10)]
minno = float('inf')
for a[0] in range(2):
    for a[1] in range(2):
        for a[2] in range(2):
            for a[3] in range(2):
                for a[4] in range(2):
                    for a[5] in range(2):
                        for a[6] in range(2):
                            for a[7] in range(2):
                                for a[8] in range(2):
                                    for a[9] in range(2):
                                        sums = 0
                                        min_tmp = 0
                                        for i in range(D):
                                            sums = sums + a[i] * S[i]
                                            min_tmp = min_tmp + a[i] * p[i]
                                        if sums >= G:
                                            minno = min(minno, min_tmp)
                                        else:
                                            rest = G - sums
                                            for j in range(10):
                                                if (p[9 - j] != 0) and (a[9 - j] == 0):
#                                                    print(p[9 - j], a[9 - j])
                                                    for k in range(p[9 - j] - 1):
                                                        rest = rest - 100 * (10 - j)
                                                        min_tmp = min_tmp + 1
#                                                        print(rest, min_tmp)
                                                        if rest <= 0:
                                                            minno = min(minno, min_tmp)
#                                        print(min_tmp)

print(minno)

Submission status: Accepted

Solution code:
from itertools import product

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

p = []
c = []
for _ in range(d):
    p_, c_ = map(int, input().split())
    p.append(p_)
    c.append(c_ // 100)

tmp_prbs = [0] * (2 ** d)
tmp_pts = [0] * (2 ** d)
for i, comp in enumerate(product([False, True], repeat=d)):
    tmp_pts[i] = sum((i+1)*p[i] + c[i] for i in range(d) if comp[i])
    tmp_prbs[i] = sum(p[i] for i in range(d) if comp[i])
    
    for j in reversed(range(d)):
        if tmp_pts[i] >= g:
            break
        if comp[j]:
            continue
        tmp_prbs[i] += min(p[j]-1, -((tmp_pts[i] - g) // (j+1)))
        tmp_pts[i] += min(p[j]-1, -((tmp_pts[i] - g) // (j+1))) * (j+1)
    
print(min(tmp_prb for tmp_pts, tmp_prb in zip(tmp_pts, tmp_prbs) if tmp_pts>=g))

Submission status: Accepted

Solution code:
D, G= map(int, input().split())
P = [[int(x) for x in input().split()] for d in range(D)]
Score = [[] for d in range(D)]
for d in range(D):
  for i in range(P[d][0] + 1):
    Score[d].append(100 * (d + 1) * i)
  Score[d][-1] += P[d][1]
DP = [[] for d in range(D)]
DP[0] = [x for x in Score[0]]
p_all = P[0][0]
for d in range(1, D):
  p_all += P[d][0]
  DP[d] = [0 for i in range(p_all + 1)]
  for p in range(p_all + 1):
    for s in range(min(P[d][0], p) + 1):
      if p - s < p_all - P[d][0] + 1:
        DP[d][p] = max(Score[d][s] + DP[d - 1][p - s], DP[d][p])
for i, s in enumerate(DP[D - 1]):
  if s >= G:
    print(i)
    break

Submission status: Accepted

Solution code:
D,G = map(int,input().split())
P = []
num_p = 0
for i in range(1,D+1):
    p,c = map(int,input().split())
    num_p += p
    for j in range(1,p+1):
        P += [(j,i*100*j+c*(j==p))]
dp = [0]*(num_p+1)
for k,pt in P:
    if k==1:
        t_dp = dp[:]
    for cur in range(1,num_p+1):
        if cur>=k:
            dp[cur] = max(dp[cur], t_dp[cur-k]+pt)
for i in range(num_p+1):
    if dp[i]>=G:
        print(i)
        break

Submission status: Accepted

Solution code:
from itertools import combinations
D, G = map(int, input().split())
pc = [[i] + list(map(int, input().split())) for i in range(1,D+1)]
pc2 = [i[1] for i in pc]
res = float("inf")
for n in range(0,D+1):
    for _ in combinations(pc,n):
        memo = pc2[::]
        tmp = 0
        count = 0
        for i,p,c in _:
            tmp += p*100*i + c
            count += p
            memo[i-1] = 0
        if tmp>=G:
            res = min(res,count)
        else:
            for k in range(D-1,-1,-1):
                if (G - (tmp + (k+1)*100*memo[k])) < 0:
                    count += (G-tmp)// ((k+1)*100) 
                    count += 1 if (G-tmp)% ((k+1)*100) !=0 else 0
                    res = min(res,count)
                else:
                    tmp += (k+1)*100*memo[k]
                    count += memo[k]

print(res)

Submission status: Accepted

Solution code:
INF = float('inf')

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

sumP = sum([p for p, c in pcs])

def max2(a, b):
    return a if a >= b else b


# 【配るDP】
# dp[i+1][j]: pcs[i]まで考慮したとき、j問で達成できるスコアの最大値
dp = [[-INF] * (sumP + 1) for i in range(D + 1)]
dp[0][0] = 0
for i, (p, c) in enumerate(pcs):
    for j in range(sumP + 1):
        if dp[i][j] != -INF:
            for k in range(p):
                dp[i + 1][j + k] = max2(dp[i + 1][j + k], dp[i][j] + 100 * (i + 1) * k)
            dp[i + 1][j + p] = max2(dp[i + 1][j + p], dp[i][j] + 100 * (i + 1) * p + c)

for j in range(sumP + 1):
    if dp[D][j] >= G:
        print(j)
        break

Submission status: Accepted

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

ans = float('inf')
for i in range(2 ** N):
  point = 0
  num = 0
  # コンプボーナスを取る取らない
  digit = 1
  for d in range(N):
    if (digit << d) & i:
      num += S[d][0]
      point += S[d][0] * (d+1) * 100 + S[d][1]
  # 大きい方から、ばらで問題を解く
  for d in range(N)[::-1]:
    if not ((digit << d) & i):
      delta = max(0, G - point)
      n = min(math.ceil(delta / ((d+1) * 100)), S[d][0])
      num += n
      point += n * (d+1) * 100
  ans = min(ans, num)
print(ans)

Submission status: Accepted

Solution code:
from itertools import permutations
from math import ceil, floor

D, G = [int(elem) for elem in input().split(' ')]
point_info_list = [[int(elem) for elem in input().split()] for _ in range(D)]
assert len(point_info_list) == D
assert len(point_info_list[0]) == 2

min_num = float('inf')
for perm in permutations(range(D)):
    current_point = 0
    current_num = 0
    for point in perm:
        if (G - current_point) - (point + 1) * 100 * point_info_list[point][0] <= 0:
            current_num += ceil((G - current_point) / ((point + 1) * 100))
            break
        elif (G - current_point) - (point + 1) * 100 * point_info_list[point][0] - point_info_list[point][1] <= 0:
            current_num += point_info_list[point][0]
            break
        else:
            current_point += (point + 1) * 100 * point_info_list[point][0] + point_info_list[point][1]
            current_num += point_info_list[point][0]
    min_num = min(current_num, min_num)

print(min_num)

Submission status: Accepted

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

ss = []
ps = []
cs = []

for i in range(d):
    p, c = list(map(int, input().split()))
    ps.append(p)
    cs.append(c)
    ss.append(100 * (i + 1))

# d, g = 2, 2000
# ps = [3, 5]
# ss = [100, 200]
# cs = [500, 800]


complete_scores = []
for i in range(d):
    complete_scores.append(ps[i] * ss[i] + cs[i])

# print(ps)
# print(ss)
# print(cs)
# print(complete_scores)

min_answers = sum(ps)
for i in range(2 ** d):
    current_score = 0
    current_answers = 0
    indexes = list(range(d))
    num = i
    for j in range(d):
        if num % 2:
            current_score += complete_scores[j]
            indexes.remove(j)
            current_answers += ps[j]
        num = num // 2

    if current_score >= g:
        min_answers = min(min_answers, current_answers)
        continue

    # print("indexes", indexes)

    for j in reversed(indexes):
        if current_score + ps[j] * ss[j] >= g:
            temp_ans = (g - current_score) // ss[j]
            if current_score + temp_ans * ss[j] >= g:
                current_answers += temp_ans
            else:
                current_answers += temp_ans + 1
            min_answers = min(min_answers, current_answers)
            break
        else:
            current_score += ss[j]
            current_answers += ps[j]

print(min_answers)

Submission status: Accepted

Solution code:
import math

MAX_INT = 1001
(d, g) = list(map(int, input().split()))
g = g // 100
arr = [[0, 0] for i in range(d+1)]
for i in range(1, d+1):
    tmp = list(map(int, input().split()))
    arr[i][0] = tmp[0]
    arr[i][1] = tmp[1] // 100

res = MAX_INT
dp = [[MAX_INT for i in range(g+1)] for k in range(d+1)]
for diff in range(1, d+1):
    e = arr[diff]
    for score in range(1, g+1):
        if score / diff <= e[0]:
            dp[diff][score] = math.ceil(score/diff)
        elif score <= diff * e[0] + e[1]:
            dp[diff][score] = e[0]
        else:
            dp[diff][score] = dp[diff-1][score - (diff * e[0] + e[1])] + e[0]
        dp[diff][score] = min(dp[diff][score], dp[diff-1][score])
# for diff in range(1, d+1):
#     print(*dp[diff])

print(dp[d][g])

Submission status: Accepted

Solution code:
d, g = [int(x) for x in raw_input().split()]
p, c = zip(*[[int(x) for x in raw_input().split()] for i in range(d)])

from itertools import product

ans = 100000000000000000000

for ss in product([False, True], repeat=d):
    m = 0
    s = 0
    for i in range(d):
        if ss[i]:
            s += (i + 1) * 100 * p[i] + c[i]
            m += p[i]

    for i in reversed(range(d)):
        if s >= g:
            break
        if ss[i] is False:
            t = min(p[i] - 1, -(-(g - s) // ((i + 1) * 100)))
            s += (i + 1) * 100 * t
            m += t

    if s < g:
        continue

    ans = min(ans, m)

print ans

Submission status: Accepted

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

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

Submission status: Accepted

Solution code:
# coding: utf-8
# Your code here!
d,g = list(map(int,input().split()))	
g=g//100
p=[]
c=[]
for i in range(d):
    P,C=list(map(int,input().split()))
    p.append(P)
    c.append(C//100)


ans = 2000
for i in range(1<<d):
    score = 0
    problem = 0
    for j in range(d):
        jbit=((i>>j) & 1)
#        print(jbit)
        score += jbit*((j+1)*p[j] + c[j])
        problem += jbit*p[j]
#    print(score,problem,"TOTYUU")
    if score >= g:
        ans = min(ans,problem)
        continue
    else:
        nokori = g - score
#        print(nokori,problem,i)
        for j in range(d-1,-1,-1):
            jbit=((i>>j) & 1)
            if jbit == 1:
                continue
            else:
                mon = (nokori+j) // (j+1)
#                print(mon,j,"kezuri")
                if mon <= p[j]-1:
                    nokori=0
                    problem += mon
                    ans = min(ans,problem)
                else:
                    nokori -= (j+1)*(p[j]-1)
                    problem += p[j]-1

print(ans)

Submission status: Accepted

Solution code:

from collections import defaultdict
import sys,heapq,bisect,math,itertools,string,queue,datetime
sys.setrecursionlimit(10**8)
INF = float('inf')
mod = 10**9+7
eps = 10**-7
AtoZ = [chr(i) for i in range(65,65+26)]
atoz = [chr(i) for i in range(97,97+26)]

def inpl(): return list(map(int, input().split()))
def inpl_str(): return list(input().split())

D,G = inpl()

flags = []
for i in range(2**D):
	t = format(i,'010b')
	flags.append(list(t[10-D:10]))

pp = [0]
cc = [0]
Comp = [0]
for i in range(1,D+1):
	p,c = inpl()
	pp.append(p)
	cc.append(c)
	Comp.append(p*i*100+c)

ans = INF
for flag in flags:
	SUM  = num = 0
	for i,fl in enumerate(flag):
		if fl == '1':
			SUM += Comp[i+1]
			num += pp[i+1]

	if SUM >= G:
		ans = min(ans,num)
	else:
		nn = -1
		delta = G - SUM
		for i in reversed(range(D)):
			if flag[i] == '1':
				continue
			else:
				nn = i+1
				break
		if nn != -1:
			if nn*100*pp[nn] >= delta:
				num += (delta-1)//(nn*100) + 1
				ans = min(ans,num)

print(ans)

Submission status: Accepted

Solution code:
D, G = (int(i) for i in input().split())
G = G // 100
P= [0] * D
C= [0] * D

for i in range(D):
    P[i], C[i] = (int(i) for i in input().split())
    C[i] = C[i] // 100

INF = int(1e9)
mem = [[0] * 1010 for _ in range(D+1)] #solve数での最大のスコア
used = [[0] * 1010 for _ in range(D+1)]

def dfs(idx, num):
    if num == 0:
        return 0
    
    if num < 0:
        return -INF

    if idx == D:
        return -INF

    if used[idx][num]:
        return mem[idx][num]
    
    used[idx][num] = 1
    p = P[idx]
    c = C[idx]
    res = -INF
    for i in range(p+1):
        score = (idx + 1) * i;
        if (i == p):
            score = score + c
        nnum = num - i
        res = max(res, score + dfs(idx+1, nnum))
    mem[idx][num] = res;
    return res

ans = INF
for i in range(1001):
    if dfs(0, i) >= G:
        ans = i
        break

print (ans)

Submission status: Accepted

Solution code:
D, G = map(int, input().split())
P, C = [], []
for i in range(D):
    pi, ci = map(int, input().split())
    P.append(pi)
    C.append(ci)

ans = float('inf')
for i in range(2**D):
    A = []
    X_solve, X_score = 0, 0
    bit = bin(2**D + i)[3:]

    for j in range(D):
        if bit[j] == "1":
            X_solve += P[j]
            X_score += 100 * (j+1) * P[j] + C[j]
        else:
            A += [100*(j+1)] * P[j]

    if X_score >= G:
        ans = min(ans, X_solve)
        continue

    A = A[::-1]
    for k in range(len(A)):
        X_score += A[k]
        if X_score >= G:
            ans = min(ans, X_solve + k + 1)
            break

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)

b = 1 << D
ans = float("inf")
for i in range(b):
    score = 0
    cnt = 0
    for j in range(D):
        b2 = 1<<j
        if i & b2:
            score += C[j] + P[j] * (j+1) * 100
            cnt += P[j]
    if score >= G:
        ans = min(ans, cnt)
        continue
    for j in range(D-1, -1, -1):
        b2 = 1<<j
        if i & b2 == 0:
            for k in range(P[j]-1):
                score += (j+1)*100
                cnt += 1
                if score >= G:
                    break
            if score >= G:
                break
    if score >= G:
        ans = min(ans, cnt)
print(ans)

Submission status: Accepted

Solution code:
d,g=map(int,input().split())
data=[]
cp=[]
for  i in range(1,d+1):
    p,c=map(int,input().split())
    data.append(p)
    cp.append(c)
a=99999999
for i in range(1024):
    ct=0
    ans=0
    tmp=data[:]
    for j in range(d):
        if i&(1<<j):
            ct+=100*(j+1)*data[j]+cp[j]
            ans+=data[j]
            tmp[j]=0
            
    p=len(tmp)-1
    while ct<g :
        if tmp[p]>1:
            ct+=100*(p+1)
            tmp[p]-=1
            ans+=1
        else:
            p-=1
        if p<0:
            ans=99999999
            break
    a=min(a,ans)
print(a)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
def inpl(): return list(map(int, input().split()))

D, G = inpl()
P = []
C = []
for _ in range(D):
    p, c = inpl()
    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())
s = 0
Q = []
for i in range(D):
    p, c = map(int, input().split())
    s += p
    Q.append((i+1, p, c))
dp = [-10**18]*(s+1)

dp[0] = 0
for i, p, c in Q:
    for j in range(s, -1, -1):
        for k in range(1, p+1):
            if k == p:
                cc = 100*i*k + c
            else:
                cc = 100*i*k
            if j - k >= 0:
                dp[j] = max(dp[j], dp[j - k] + cc)
for i in range(1+s):
    if dp[i] >= G:
        print(i)
        break

Submission status: Accepted

Solution code:
import sys

stdin = sys.stdin

ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline()

D, G = na()
p = []
c = []
for i in range(D):
    x, y = na()
    p.append(x)
    c.append(y)

ans = 99999999
for i in range(1<<D):
    ct = 0
    score = 0
    for j in range(D):
        if i>>j&1:
            score += c[j]
            score += p[j] * (j+1) * 100
            ct += p[j]
    for j in range(D-1, -1, -1):
        if i>>j&1: continue
        if score >= G: break
        g = (j+1)*100
        got = (G-score+g-1)//g
        score += min(got, p[j]) * g
        ct += min(got, p[j])
    ans = min(ans, ct)
print(ans)

Submission status: Accepted

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

ans = sum(p)
for b in range(1<<D):
  s = 0
  a = 0
  for i in range(D):
    if b>>i&1:
      s += p[i]*(i+1)*100 + c[i]
      a += p[i]
  for i in range(D)[::-1]:
    if not b>>i&1:
      if s>=G:
        break
      t = min(p[i], (G-s+(i+1)*100-1)/((i+1)*100))
      s += t*(i+1)*100
      a += t
  ans = min(ans, a)
print ans

Submission status: Accepted

Solution code:
def main():
    d, g = map(int, input().split())
    probs = []
    ans = 0
    for i in range(d):
        p, c = map(int, input().split())
        probs.append(((i + 1) * 100, p, c))
        ans += p

    for mask in range(1 << d):
        solved = 0
        my_score = 0
        for i in range(d):
            score, occ, bonus = probs[i]
            if (mask & (1 << i)) > 0:
                solved += occ
                my_score += score * occ + bonus

        for x in range(d - 1, -1, -1):
            if my_score >= g:
                break
            if (mask & (1 << x)) > 0:
                continue
            score, occ, bonus = probs[x]
            for _ in range(occ):
                solved += 1
                my_score += score
                if my_score >= g:
                    break
        if my_score >= g:
            ans = min(ans, solved)

    print(ans)

main()

Submission status: Runtime Error

Solution code:
rom math import ceil

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):
    cnt = 0
    sum = 0
    remain = set(range(1,D+1))

    for i in range(D):
        if bit & (1 << i):
            cnt += pc[i][0]
            sum += pc[i][0]*(i+1)*100 + pc[i][1]
            remain.discard(i+1)

    if sum < G:
        use = max(remain)
        n = min(pc[use-1][0], ceil((G-sum)/(use*100)))
        """
        if use == 0:
            n = 0
        elif (G - sum)%(use%100) == 0:
            n = min(pc[use-1][0], (G - sum)//(use*100))
        else:
            n = min(pc[use-1][0], (G - sum)//(use*100)+1)
        """
        cnt += n
        sum += n*use*100

    if sum >= G:
        ans = min(ans,cnt)

print(ans)

Submission status: Runtime Error

Solution code:
import queue

R,C = map(int, input().split())
sy,sx = map(int, input().split())
gy,gx = map(int, input().split())
dydx = ((-1,0),(0,-1),(1,0),(0,1))

maze = [input() for _ in range(R)]
visited = [[0]*C for _ in range(R)]

q = queue.Queue()
q.put((sy-1,sx-1,0))

while not q.empty():
    y,x,d = q.get()
    
    if y == gy-1 and x == gx-1:
        print(d)
        break
    if visited[y][x] == 1:
        continue
    else:
        visited[y][x] == 1
        for dy,dx in dydx:
            if (0 <= y+dy < R) and (0 <= x+dx < C) and visited[y+dy][x+dx]==0 and maze[y+dy][x+dx] == '.':
                q.put((y+dy,x+dx,d+1))

Submission status: Runtime Error

Solution code:
ans = float("inf")
for i in range(1<<d):
    count = 0
    sum = 0
    nokori = set(range(1, d+1))
    
    # ボーナスをもらえる解答のみでスコアを計算
    for j in range(d):
        if j & 1<<i:
            sum += pc[i][0]*(i+1)*100+pc[i][1]
            count += pc[i][0]
            nokori.discard(i+1)
            
    # スコアがG点に届かない場合
    if sum < g:
        use = max(nokori)
        n = min(pc[use-1][0], (g-sum)//(use*100))
        count += n
        sum += n*use*100
        
    # スコアがG点に届いた場合
    if sum >= g:
        ans = min(ans, count)
print(ans)

Submission status: Runtime Error

Solution code:
import copy
import heapq

from typing import List, Tuple


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

    print(ag(v, g))


def ag(v: List[Tuple[int, int]], g: int) -> int:
    rs = []
    # ex. [(3, 500), (5, 800)] -> [(1, 3, 500), (2, 5, 800)]
    v = [(i, p, c) for i, (p, c) in enumerate(v, 1)]

    for j in range(len(v) ** 2):
        cb = []
        for k in range(len(v)):
            if ((j >> k) & 1):
                cb.append(v[k])

        sc = 0
        cnt = 0
        # calc bonus score
        for (i, p, c) in cb:
            sc += i * 100 * p + c
            cnt += p

        vv = [x for x in copy.copy(v) if not x in cb]
        while sc < g:
            if not vv:
                break
            i, p, _ = vv.pop()
            for _ in range(p - 1):
                if sc >= g:
                    break
                sc += i * 100
                cnt += 1

        if sc >= g:
            heapq.heappush(rs, cnt)

    return heapq.heappop(rs)


if __name__ == '__main__':
    main()