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:
d,g = map(int,input().split(" "))

pros = []

for i in range(d):
    pros.append(list(map(int,input().split(" "))))
    pros[i].append(100*(i+1)*pros[i][0]+pros[i][1])

min_p = 1000
for i in range(2**d):
    sum_i,pro_num = 0,0
    i_2 = str(bin(i)[2:])
    for k,j in enumerate(i_2[::-1]):
        if sum_i > g or min_p <=pro_num:
            break
        if j == "1":
            sum_i += pros[k][2]
            pro_num += pros[k][0]
    else:
        if sum_i >= g:
            min_p = min(pro_num,min_p)
        else:
            if pro_num < min_p:
                remain = g - sum_i
                i_3 = i_2.zfill(d)
                for k,j in enumerate(i_3):
                    if j == "0":
                        add = 0
                        while remain > 0 and add < pros[d-1-k][0]:
                            remain -= 100*(d-k)
                            add += 1
                            if remain <= 0:
                                pro_num += add
                                min_p = min(pro_num,min_p)
                                break
                        break
print(min_p)

Submission status: Accepted

Solution code:
import itertools
from collections import Counter
D, G = map(int, input().split())
P = [list(map(int, input().split())) for i in range(D)]
min_num = 10**8

judge_list = list(itertools.product([0, 1, 2], repeat=D)) #0:中途半端に解く 1:一問も解かない 2: 全部解く


for judge in judge_list:
    score = 0
    num = 0
    d = Counter() #インスタンスを生成
    d.update(judge)
    if (d[0] <= 1):
        for i in range(1, len(judge) + 1):
            if score >= G:
                break

            if judge[-i] == 1:
                pass

            if judge[-i] == 2:
                score += P[-i][0] * (D - i + 1) * 100 + P[-i][1]
                num += P[-i][0]

            if (judge[-i] == 0):
                for j in range(P[-i][0]):
                    if score >= G:
                        break
                    score += 100 * (D - i + 1)
                    num += 1
                        
        if score >= G:
            min_num = min(num, min_num)

print(min_num)

Submission status: Accepted

Solution code:
import itertools
import numpy as np

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

level = np.arange(1, D + 1)
P = np.ndarray(D, dtype=int)
C = np.ndarray(D, dtype=int)
for i in range(D):
    P[i], C[i] = [int(x) for x in input().split()]

complete_scores = level * 100 * P + C

min_problems = P.sum()
for bits in itertools.product([0, 1], repeat=D):
    bits = np.array(bits)
    score_rest = G - (bits * complete_scores).sum()
    if score_rest <= 0:
        min_problems = min(min_problems, (bits * P).sum())
    else:
        for i in reversed(range(D)):
            n_problems = (score_rest + (level[i] * 100) - 1) // (level[i] * 100)
            if bits[i] == 0 and n_problems < P[i]:
                min_problems = min(min_problems, (bits * P).sum() + n_problems)
                break

print(min_problems)

Submission status: Accepted

Solution code:
d,g=map(int,input().split())
pc=[list(map(int, input().split())) for _ in range(d)]
t1=[bin(2**d+i)[3::] for i in range(2**d)]
a=[]
for t in t1:
    ta=0
    tb=0
    for i in range(d):
        if t[i]=='1':
            ta+=pc[i][0]
            tb+=100*pc[i][0]*(i+1)+pc[i][1]
    if tb>=g:
        a.append(ta)
    else:
        for i in range(d-1,-1,-1):
            if t[i]=='0':
                if 100*(i+1)*pc[i][0]>=g-tb:
                    if (g-tb)%(100*(i+1))==0:
                        ta+=(g-tb)//(100*(i+1))
                        tb+=100*(i+1)*((g-tb)//(100*(i+1)))
                    else:
                        ta+=(g-tb)//(100*(i+1))+1
                        tb+=100*(i+1)*((g-tb)//(100*(i+1))+1)
                break
        if tb>=g:
            a.append(ta)
print(min(a))

Submission status: Accepted

Solution code:
from itertools import product
from math import ceil

d ,g = map(int, input().split())
problem = [0]*d
bonus = [0]*d
compscore = [0]*d
for i in range(d):
    problem[i], bonus[i] = map(int, input().split())
    compscore[i] = 100*(i+1)*problem[i] + bonus[i]
ans = 1001

#product(range(2), repeat=d)の元は、d次元の元であって
#各成分が0or1となるもの(全部で2^d通り）
for c in product(range(2), repeat=d):
    score = 0
    solved = 0
    max_of_notcomp = -1

    for i in range(d):
        if c[i] == 1:
            score += compscore[i]
            solved += problem[i]
        else:
            max_of_notcomp = i
    
    if score < g and score + 100*(max_of_notcomp+1)*(problem[max_of_notcomp]-1) >= g:
        solved += ceil((g - score)/(100*(max_of_notcomp+1)))
        score += ceil((g - score)/(100*(max_of_notcomp+1)))*100*(max_of_notcomp+1)

    if score >= g:
        ans = min(ans, solved)
print(ans)

Submission status: Accepted

Solution code:
D, G = map(int, input().split())
p = []
c = []
for i in range(0, D):
    a, b = map(int, input().split())
    p.append(a)
    c.append(b)
    
minimum = 2**31   

for i in range(2**D):
    count = 0
    score = 0
    max_j = 0
    addcount = 0
    for j in range(D):
        if (i>>j & 1):
            score += 100 * (j+1) * p[j] + c[j]
            count += p[j]
        if (~i>>j & 1):
            max_j = j
    if score >= G:
        minimum = min(minimum, count)
    else:
        while score < G:
            score += 100 * (max_j + 1)
            addcount += 1
            count += 1
        if addcount <= p[max_j]:
            minimum = min(minimum, count)

print(minimum)

Submission status: Accepted

Solution code:
from itertools import product
from math import ceil
D,G = map(int,input().split(" "))
p,c = [0]*D,[0]*D

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

ans = float('inf')
for pat in range(1<<D):
    point,prob,maxv = 0,0,0
    for b in range(D):
        if (pat >> b) & 1:
            point += ((100*(b+1))*p[b] + c[b])
            prob += p[b]
        else:
            maxv = max(maxv,b+1)

    if point >= G:
        ans = min(ans,prob)

    elif maxv != 0:
        if G <= (point + (maxv*100)*p[maxv-1]):
            ans = min(ans,prob+ceil((G-point)/(maxv*100)))

print(ans)

Submission status: Accepted

Solution code:
# coding: utf-8
ranknum,goal = list(map(int,input().split()))
probnum = [0]*ranknum
bonus = [0]*ranknum
compscore = [0]*ranknum

for i in range(ranknum):
    probnum[i], bonus[i] = list(map(int,input().split()))
    #各ランクをコンプした場合に得られる得点をcompscoreに格納しておく。
    compscore[i] = 100*(i+1)*probnum[i] + bonus[i]

from itertools import product
from math import ceil

#得点Gを達成する最小の問題正解数minprobを初期化。前提により必ず1000以下になるので、1001で初期化しておく。
minprob = 1001

#各ランクの問題をコンプするか否かの2^ranknum通りをループ処理する。
for c in product(range(2),repeat=ranknum):
    score = 0
    solvedprob = 0
    notcompedindex = -1

    #コンプした問題について、得点をcompscoreに、正解数をsolvedprobnumに格納する。
    for i in range(ranknum):
        if c[i] == 1:
            score +=  compscore[i]
            solvedprob +=  probnum[i]
        #コンプされていないランクのインデックスのうち最大のものをnotcompedindexに格納しておく。
        else:
            notcompedindex = i

    #コンプした問題だけでgoalに達さず、かつ、コンプしていない最高ランクの問題をコンプ寸前まで解けばゴールに達する場合、
    #ゴールをぎりぎり達成するところまで正解した状態へと、scoreとsolvedprobを更新する。
    if score < goal and score+100*(notcompedindex+1)*(probnum[notcompedindex]-1) >= goal:
        solvedprob += ceil((goal - score)/(100*(notcompedindex+1)))
        score += ceil((goal - score)/(100*(notcompedindex+1)))*100*(notcompedindex+1)
    
    #最終的にゴールを達成している場合、正解数が暫定最小ならば、それをminprobに格納しておく。
    if score >= goal:
        minprob = min(minprob, solvedprob)  

print(minprob)

# print(ranknum)
# print(goal)
# print(problemnum)
# print(bonus)
# print(completescore)

Submission status: Accepted

Solution code:
D,G=map(int, input().split())
PC=[0]+[list(map(int, input().split())) for _ in range(D)]
def function(G,i):
    if i==0:
        return 1e9
    n=min(G//(i*100),PC[i][0]) #determin the number of "100i problem" to be solved
    s=n*i*100
    if n==PC[i][0]:
        s+=PC[i][1] #modify the point for "100i problem" with complete bonus
    if s<G:
        n+=function(G-s,i-1) #calculate until G-Sigma(s)=0
    return min(n,function(G,i-1))
print(function(G,D))

Submission status: Accepted

Solution code:
import itertools
d,c=map(int, input().split())
p=[list(map(int, input().split())) for i in range(d)]
al=list(itertools.product(range(2),repeat=d))
ans=1000
for i in al:
    count=0
    score=0
    if 0 not in i:continue
    last0=d-list(reversed(i)).index(0)-1
    for j in range(d):
        count+=i[j]*p[j][0]
        score+=i[j]*p[j][1]+i[j]*p[j][0]*(j+1)*100
    #print(count,score,last0,i)
    if score>=c:ans=min(ans,count)
    elif (c-score)/((last0+1)*100)<p[last0][0]:ans=min(ans,count+(c-score+last0*100)//((last0+1)*100))
if d==1:print(1)
else:print(ans)

Submission status: Accepted

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

arr = []

for i in range(d):
	arr.append(map(int,raw_input().split()))


ans = float("inf")
for i in range(2**d-1,-1,-1):
	b = bin(i)[2:].zfill(d)
	count = 0
	point = 0
	for j in range(d-1,-1,-1):
		if b[j] == "1":
			count += arr[j][0]
			point += (j+1) * 100 * arr[j][0] + arr[j][1]
	if point < g:

		for j in range(d-1,-1,-1):

			if b[j] == "0":
				t = 0
				while point < g and arr[j][0]-t > 1:
					point += (j+1) * 100
					t += 1
					count += 1

	if point < g:
		continue
	ans = min(ans, count)

print ans

Submission status: Accepted

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

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

pi = []
ci = []
score_i_c = []
score_i_h = []
for i in range(D):
    p_t, c_t = map(int, input().split())
    pi.append(p_t)
    ci.append(c_t)
    tmp = p_t * 100 * (i + 1) + c_t
    score_i_c.append((i,tmp,p_t))
    tmp = (p_t - 1) * 100 * (i + 1)
    score_i_h.append((i,tmp,p_t))

# 完全に解かなくても行ける場合
step1_list = []
for i,score,num in score_i_h:
    if score >= G:
        step1_list.append((i,score,num))

ans_list = []
if len(step1_list) > 0:
    min_i , _, _ = step1_list[-1]
    for i , score, num in step1_list:
        tmp_score = 0
        tmp_num = 0
        for i in range(pi[min_i]):
            if tmp_score >= G:
                break
            else:
                tmp_score += (min_i+1) * 100
                tmp_num  += 1
        ans_list.append(tmp_num)

#完全に解くケース
step1_list = []
for i in range(D):
    tmp = itertools.combinations(score_i_c, i+1)
    step1_list.extend(list(tmp))

# 合計がGを超える組み合わせを抽出
sum_list = []
for l in step1_list:
    numbers = []
    sum_score = 0
    sum_num = 0
    for i,score,num in l:
        numbers.append(i)
        sum_score += score
        sum_num += num

    if sum_score >= G:
        sum_list.append((numbers,sum_score,sum_num))
#
# print(step1_list)
# print(sum_list)

# min_numbers = []
# min_score = 0
# min_num = 10000
# for i,score,num in sum_list:
#     if num < min_num:
#         min_numbers = i
#         min_score = score
#         min_num = num

# print(min_numbers,min_score,min_num)

# min_i = min_numbers[-1]
for min_numbers,min_score,min_num in sum_list:
    for min_i in min_numbers:
        tmp_score = min_score - score_i_c[min_i][1]
        tmp_num = min_num - score_i_c[min_i][2]

        for i in range(pi[min_i]):
            if tmp_score >= G:
                break
            tmp_score += (min_i+1) * 100
            tmp_num  += 1

        ans_list.append(tmp_num)

# print(ans_list)

print(min(ans_list))

Submission status: Accepted

Solution code:
# encoding: utf-8
D_MAX = 10
P_MAX = 100

num_and_pnt = lambda x: [int(x[0]), int(x[1]) // 100]
D, G = num_and_pnt(input().split())
# [pi, ci]
pc = [num_and_pnt(input().split()) for i in range(D)]

G_list = [(i + 1) * x[0] + x[1] for i, x in enumerate(pc)]
cnt_list = [x[0] for i, x in enumerate(pc)]
idx = [map(int, format(i, "b")) for i in range(2 ** D)]

# i, G_comp, cnt_comp
table = [ (i, sum([((i // (2 ** j)) % 2) * G_list[j] for j in range(D)]), sum([((i // (2 ** j)) % 2) * cnt_list[j] for j in range(D)])) for i in range(2 ** D)] # very long
# print(table)
mincnt = D_MAX * P_MAX
for i, (G_last, cnt_last) in enumerate(zip(G_list, cnt_list)):
    for j, G_comp, cnt_comp in filter(lambda x: (((x[0] // (2 ** i)) % 2 == 0) and (x[1] <= G < x[1] + G_last) and (x[2] < mincnt)), table):
        # print(i, (G_last, cnt_last), j, G_comp, cnt_comp)
        cnt_last_tmp = min((-((G_comp - G) // (i + 1)), cnt_last))
        if cnt_comp + cnt_last_tmp < mincnt: mincnt = cnt_comp + cnt_last_tmp

print(mincnt)

Submission status: Accepted

Solution code:
import math

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)
compl = [100 * (i+1) * p[i] + c[i] for i in range(d)]

ans = 1e9
for i in range(2 ** d):
    score = num = 0
    for j in range(d):
        if (i >> j) & 1:
            score += compl[j] 
            num += p[j] 
        else:
            # index of highest rest valuable p.
            rest_idx = j
    if score < g:
        need = math.ceil((g - score) / (100 * (rest_idx + 1)))
        if need >= p[rest_idx]:
            continue
        num += need
    ans = min(ans, num)
print(ans)

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):
	if i==0:
		return 1e9
	n=min(G//(i*100), PC[i][0])
	s=n*i*100
	if n==PC[i][0]:
		s+=PC[i][1]
	if s<G:
		n+=function(G-s, i-1)
	return min(n, function(G,i-1))
print(function(G, D))

Submission status: Accepted

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

def solve(g, i):
    if i <= 0:
        return 1e9
    n = min(int(g / (100 * i)), p[i - 1])
    s = 100 * i * n
    if n == p[i - 1]:
        s += c[i - 1]
    if g > s:
        n += solve(g - s, i - 1)
    return min(n, solve(g, i - 1))

print(solve(g, d))

Submission status: Accepted

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

""" ビット全検索をちゃんと使ってみる版3 """

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

# 各点数問題毎の、全問解いた場合の回答数と得点を保持
class ScoreSet:
    def __init__(self, times, score):
        self.times = times
        self.score = score

# 各パターン毎の、合計回答数と合計得点と、どの点数問題を全問解いたのかを保持
class ScoreSetSum:
    def __init__(self, times, score, bool_list):
        self.times = times
        self.score = score
        self.bool_list = bool_list

# 入力内容から、ScoreSetのリストを作成
scoreSetList = [0] * D
for i in range(D):
    p, c = map(int, input().split())
    scoreSetList[i] = ScoreSet(p, p*100*(i+1) + c)

# ビット全検索のループとScoreSetのリストから、ScoreSetSumのリストを作成
scoreSetSumList = [0] * (1<<D)
for i in range(1<<D):
    times_tmp = 0
    score_tmp = 0
    bool_list = [False] * D
    for j in range(D):
        if 1 & i>>j == 1:
            times_tmp += scoreSetList[j].times
            score_tmp += scoreSetList[j].score
            bool_list[j] = True
    scoreSetSumList[i] = ScoreSetSum(times_tmp, score_tmp, bool_list)

# ScoreSetSumのリストを元に、適切なパターンを探していく
ans = float("inf")
for scoreSetSum in scoreSetSumList:
    tmp = float("inf")
    # 得点が既にG以上であれば、そのままその回答数が候補
    if scoreSetSum.score >= G:
        tmp = scoreSetSum.times
    else:
        # 足りなかったら、全問解いていない点数問題から最も高いもの選ぶ
        for i in range(D-1, -1, -1):
            if scoreSetSum.bool_list[i] == False:
                score = scoreSetSum.score
                times = scoreSetSum.times
                # 選んだ点数問題を1問ずつ解いていく
                for j in range(scoreSetList[i].times):
                    score += 100*(i+1)
                    times += 1
                    # G以上に達した時点で、その時の回答数が候補
                    if score >= G:
                        tmp = times
                        break
                    # 最後まで解いてもG以上にならなければ、このパターンは候補外
                break
    # 今までの最小と今回の候補を比較
    ans = min(ans, tmp)

print(ans)

Submission status: Accepted

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

""" ビット全検索をちゃんと使ってみる版2 """

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

# 各点数問題毎の、全問解いた場合の回答数と得点を保持
class ScoreSet:
    def __init__(self, times, score):
        self.times = times
        self.score = score

# 各パターン毎の、合計回答数と合計得点と、どの点数問題を全問解いたのかを保持
class ScoreSetSum:
    def __init__(self, times, score, bool_list):
        self.times = times
        self.score = score
        self.bool_list = bool_list

# 入力内容から、ScoreSetのリストを作成
scoreSetList = []
for i in range(D):
    p, c = map(int, input().split())
    scoreSetList.append(ScoreSet(p, p*100*(i+1) + c))

# ビット全検索のループとScoreSetのリストから、ScoreSetSumのリストを作成
scoreSetSumList = []
for i in range(1<<D):
    times_tmp = 0
    score_tmp = 0
    bool_list = []
    for j in range(D):
        if 1 & i>>j == 1:
            times_tmp += scoreSetList[j].times
            score_tmp += scoreSetList[j].score
            bool_list.append(True)
        else:
            bool_list.append(False)
    scoreSetSumList.append(ScoreSetSum(times_tmp, score_tmp, bool_list))

# ScoreSetSumのリストを元に、適切なパターンを探していく
ans = float("inf")
for scoreSetSum in scoreSetSumList:
    tmp = float("inf")
    # 得点が既にG以上であれば、そのままその回答数が候補
    if scoreSetSum.score >= G:
        tmp = scoreSetSum.times
    else:
        # 足りなかったら、全問解いていない点数問題から最も高いもの選ぶ
        for i in range(D-1, -1, -1):
            if scoreSetSum.bool_list[i] == False:
                score = scoreSetSum.score
                times = scoreSetSum.times
                # 選んだ点数問題を1問ずつ解いていく
                for j in range(scoreSetList[i].times):
                    score += 100*(i+1)
                    times += 1
                    # G以上に達した時点で、その時の回答数が候補
                    if score >= G:
                        tmp = times
                        break
                    # 最後まで解いてもG以上にならなければ、このパターンは候補外
                break
    # 今までの最小と今回の候補を比較
    ans = min(ans, tmp)

print(ans)

Submission status: Accepted

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

""" ビット全検索をちゃんと使ってみる版 """

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

# 各点数問題毎の、全問解いた場合の回答数と得点を保持
class ScoreSet:
    def __init__(self, times, score):
        self.times = times
        self.score = score

# 各パターン毎の、合計回答数と合計得点と、どの点数問題を全問解いたのかを保持
class ScoreSetSum:
    def __init__(self, times, score, bool_list):
        self.times = times
        self.score = score
        self.bool_list = bool_list

# 入力内容から、ScoreSetのリストを作成
scoreSetList = []
for i in range(D):
    p, c = map(int, input().split())
    scoreSetList.append(ScoreSet(p, p*100*(i+1) + c))

# どの点数問題を全問解いたのかの各パターンの全網羅
# bool_lists = list(itertools.product([True, False], repeat=D))

# ビット数に応じた全パターン数のループ
bool_lists = []
for i in range(1<<D):
    # あるパターンでの各ビットの0or1を見ていくループ
    bool_lists.append([])
    for j in range(D):
        # 右ビットシフトした時の1桁目が1か0かで処理を分ける
        if 1 & i>>j == 1:
            bool_lists[i].append(True)
        else:
            bool_lists[i].append(False)

# パターン全網羅とScoreSetのリストから、ScoreSetSumのリストを作成
scoreSetSumList = []
for bool_list in bool_lists:
    times_tmp = 0
    score_tmp = 0
    for i in range(len(bool_list)):
        if bool_list[i]:
            times_tmp += scoreSetList[i].times
            score_tmp += scoreSetList[i].score
    scoreSetSumList.append(ScoreSetSum(times_tmp, score_tmp, bool_list))

# ScoreSetSumのリストを元に、適切なパターンを探していく
ans = float("inf")
for scoreSetSum in scoreSetSumList:
    tmp = float("inf")
    # 得点が既にG以上であれば、そのままその回答数が候補
    if scoreSetSum.score >= G:
        tmp = scoreSetSum.times
    else:
        # 足りなかったら、全問解いていない点数問題から最も高いもの選ぶ
        for i in range(D-1, -1, -1):
            if scoreSetSum.bool_list[i] == False:
                score = scoreSetSum.score
                times = scoreSetSum.times
                # 選んだ点数問題を1問ずつ解いていく
                for j in range(scoreSetList[i].times):
                    score += 100*(i+1)
                    times += 1
                    # G以上に達した時点で、その時の回答数が候補
                    if score >= G:
                        tmp = times
                        break
                    # 最後まで解いてもG以上にならなければ、このパターンは候補外
                break
    # 今までの最小と今回の候補を比較
    ans = min(ans, tmp)

print(ans)

Submission status: Accepted

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

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

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

ret = 10000
for sel in range(0,d+1):
    for s in combinations(range(d),sel):
        score = 0
        num = 0
        for si in s:
            score += (si+1)*100*p[si] + c[si]
            num += p[si]
        if score>=g:
            if num<ret:
                ret = num
            continue

        r = set(range(d)) - set(s)
        if len(r)==0:
            continue

        si = max(r)
        for pi in range(p[si]):
            score += (si+1)*100
            num += 1
            if score>=g and num<ret:
                ret = num

print(ret)

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)
    
sum=[]
for i in range(d):
    sum.append((i+1)*100*p[i]+c[i])


def ans(g,t):
    if t<=0:
        return 100000000000
    n=min(int(g/(100*t)),p[t-1])
    s=100*t*n
    
    if n==p[t-1]:
        s=sum[t-1]
    if g>s:
        n+=ans(g-s,t-1)
    
    return min(n,ans(g,t-1))

print(ans(g,d))

Submission status: Accepted

Solution code:
D, G = map(int, input().split())
S = [[0] for i in range(D + 1)]
B = [[0] for i in range(D + 1)]
sumP = 0
for i in range(D):
  p, c = map(int, input().split())
  S[i + 1] += [0] * (len(S[i]) + p - 1)
  B[i + 1] += [100 * (i + 1) * (x + 1) for x in range(p)]
  B[i + 1][-1] += c
for i in range(1, D + 1):
  for j in range(1, len(S[i])):
    for k in range(max(j - len(S[i - 1]) + 1, 0), min(len(B[i]), j + 1)):
      S[i][j] = max(B[i][k] + S[i - 1][j - k], S[i][j])
for i, s in enumerate(S[D]):
  if s >= G:
    print(i)
    break

Submission status: Accepted

Solution code:
from math import ceil


def main():
    d, g = [int(x) for x in input().split()]
    pcs = [[int(x) for x in input().split()] for _ in range(d)]
 
    def rec(g, i):
        nonlocal pcs
        if i <= 0:
            return float('inf')

        p, c = pcs[i-1]
        s = 100 * i
        n = min(ceil(g/s), p)
        score = s * n + c if n == p else s * n

        if score >= g:
            m = n
        else:
            m = n + rec(g-score, i-1)

        r = min(m, rec(g, i-1))
        #print(g, i, r)
        return r


    print(rec(g, d))

main()

Submission status: Accepted

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

for i in range(D):
    p,c = pc[i]
    full_score[i] = 100 * (i+1) * p + c

ans = 10**10
from itertools import product
for case in product([0, 1], repeat=D):
    count, score = 0, 0
    for i in range(D):
        p, c = pc[i]
        count += p * case[i]
        score += full_score[i] * case[i]
    if 0 in case:
        i = D - 1 - case[::-1].index(0)
        p, c = pc[i]
        for j in range(p):
            if score >= G:
                break
            score += 100 * (i+1)
            count += 1
    if score >= G:
        ans = min(ans, count)

print(ans)

Submission status: Accepted

Solution code:
fn = lambda: map(int, input().split())
D, G = fn()
p, c = [0] * D, [0] * D
complete_scores = [0] * D
for i in range(D):
    p[i], c[i] = fn()
    complete_scores[i] = 100 * (i + 1) * p[i] + c[i]

def calc(x):
    value = 0
    count = 0
    i_unused = None
    for i, xi in enumerate(x):
        if xi == '1':
            value += complete_scores[i]
            count += p[i]
        else:
            i_unused = i
    if i_unused is not None:
        for _ in range(p[i_unused]):
            if value >= G:
                break
            else:
                value += (i_unused + 1) * 100
                count += 1
    if value < G:
        return float('inf')
    else:
        return count

fmt = '0{}b'.format(D)
x = format(0, fmt)
best_count = float('inf')
while len(x) <= D:
    best_count = min(calc(x), best_count)
    x = format(int(x, 2) + 1, fmt)

print(best_count)

Submission status: Accepted

Solution code:
import itertools
import math
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())
r = sum(p)
for a in itertools.product([True, False], repeat=D):
  s = 0
  b = 0
  for i in range(D):
    if a[i]:
      s += p[i]
      pi = p[i]
      ci = c[i]
      b += (100*(i+1)*pi)+ci
  for i in range(D-1,-1,-1):
    if b>=G:
      break
    if not a[i]:
      d = min(p[i]-1, int(math.ceil(1.0*(G-b)/(100*(i+1)))))
      s += d
      b += 100*(i+1)*d
  if b>=G:
    r = min(r, s)
print r

Submission status: Accepted

Solution code:
from itertools import product

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

C = [0] * D
for i in range(D):
    p, c = pc[i]
    C[i] = 100 * (i + 1) * p + c

ans = float('inf')
for ptn in product([0, 1], repeat=D):
    point, cnt = 0, 0
    for i in range(D):
        p, c = pc[i]
        cnt += p * ptn[i]
        point += C[i] * ptn[i]

    if 0 in ptn:
        index = D - 1 - ptn[::-1].index(0)
        p, _ = pc[index]
        for i in range(p):
            if point >= G:
                break            
            point += 100 * (index + 1)
            cnt += 1

    if point >= G:
        ans = min(ans, cnt)
print(ans)

Submission status: Accepted

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


def solve(G, i):
    """100i点以下の問題だけでGを達成する最小問題数"""
    if i <= 0:
        return 1e9
    n = min(int(G/(100*i)), p[i-1])
    s = 100 * i * n
    if n == p[i-1]:
        s += c[i-1]
    if G > s:
        n += solve(G-s, i-1)
    return min(n, solve(G, i-1))

print(solve(G, D))

Submission status: Accepted

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
mod = 10**9+7
dd = [(-1,0),(0,1),(1,0),(0,-1)]
ddn = [(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)


def main():
    d,g = LI()
    p = []
    c = []
    for _ in range(d):
        t = LI()
        p.append(t[0])
        c.append(t[1])

    r = inf
    for i in range(2**d):
        tg = 0
        tr = 0
        for j in range(d):
            if 2**j & i:
                tg += c[j]
                tg += (j+1) * p[j] * 100
                tr += p[j]
        for j in range(d-1,-1,-1):
            if tg >= g:
                break
            if 2**j & i:
                continue
            ng = g - tg
            k = ng // ((j+1) * 100)
            if ng % ((j+1) * 100) > 0:
                k += 1
            if p[j] >= k:
                tr += k
                break
            tr += p[j]
            tg += p[j] * (j+1) * 100
        if r > tr:
            r = tr
    return r


print(main())

Submission status: Accepted

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

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