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())
PC = [tuple(map(int, input().split())) for _ in range(D)]

# コンプリートしたときの点数
comp = [100*(i+1)*PC[i][0] + PC[i][1] for i in range(D)]

# bit全探索
# 配点が高い位置からコンプリートする問題を決め打ち
ans = sum([PC[i][0] for i in range(D)])
for bit in range(1<<D):
    
    
    point = 0
    prob = 0
    
    for j in range(D-1, -1, -1):
        if bit & (1<<j):
            point += comp[j]
            prob += PC[j][0]

    # コンプだけでG以上になったなら次へ
    if point >= G:
        ans = min(ans,prob)
        continue
    
    # そうでないなら高い位置から貪欲
    else:
        for j in range(D-1, -1, -1):
            if bit & (1<<j):
                continue
            else:
                if point + 100*(j+1)*(PC[j][0]-1) < G:
                    point += 100*(j+1)*(PC[j][0]-1)
                    prob += (PC[j][0]-1)
                else:
                    temp = (G-point)//(100*(j+1)) + bool((G-point)%(100*(j+1)))
                    point += 100*(j+1)*temp
                    prob += temp
        
            if point >= G:
                ans = min(ans,prob)
                break
            

print(ans)

Submission status: Accepted

Solution code:
from itertools import product
from math import ceil

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())

ans=1e9
for x in product([0,1],repeat=D):
  cnt = 0
  pnt = 0
  i = 0
  maxi = 0 # 中途半端に解くiを決める。
  incompflg = False
  for y in x:
    if y == 1:
      # 完全回答するパターン
      cnt += p[i]
      pnt += (i+1)*100*p[i] + c[i]
    else:
      # 完全回答しないパターン
      maxi = i
      incompflg = True
    i += 1
  
  if pnt >= G:
    ans = min(ans, cnt)
  elif incompflg and pnt + (p[maxi]-1) * (maxi+1) * 100 >= G:
    ans = min(ans, cnt+ ceil( (G-pnt) / ( (maxi+1) * 100 ) ))
  #print(x, cnt, pnt, ans)
  
print(ans)

Submission status: Accepted

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

import itertools

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))

# パターン全網羅と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:
D,G=map(int,input().split())
p=[]
c=[]
compScore=[]
checkBits=[]
for i in range(D):
    x,y =map(int,input().split())
    p.append(x)
    c.append(y)
    compScore.append(x*(i+1)*100+y)
    checkBits.append(2**i)
    
ans = sum(p)
for bit in range(2**D):
    score = 0
    ansCand = 0
    notCompleted=set(range(D))
    for i in range(D):
        checkBit = checkBits[i]
        if (bit & checkBit) == checkBit:
            score += compScore[i]
            ansCand += p[i]
            notCompleted.remove(i)
    if score >= G:
        ans = min(ans,ansCand)
        #print(bit,"complete",ansCand)
    else:
        if notCompleted:
            halfFilled = max(notCompleted)
            #print(30,score,(p[halfFilled]-1)*(halfFilled+1)*100,(G-score)//((halfFilled+1)*100))
            if score + (p[halfFilled]-1)*(halfFilled+1)*100 >= G:
                ansCand += (G-score)//((halfFilled+1)*100)
                if (G-score)%((halfFilled+1)*100)!=0:
                    ansCand += 1
                ans = min(ans,ansCand)
            #print(36,bit,halfFilled,ansCand)
#for i in range(D):
#    print(compScore[i])

print(ans)

Submission status: Accepted

Solution code:
import math
D,G = map(int,input().split())
p=[]
c=[]
for i in range(D):
    p_tmp,c_tmp = map(int,input().split())
    p.append(p_tmp)
    c.append(c_tmp)

ans = sum(p)
for i in range(2**D):
    score_tmp = 0
    ans_tmp = 0
    for j in range(D):
        if (i>>j)%2 == 1:
            score_tmp += p[j]*(j+1)*100+c[j]
            ans_tmp += p[j]

    if ans_tmp >= ans:
        continue
    elif score_tmp >= G:
        ans = ans_tmp
        continue
    else:
        for j in range(D):
            if (i>>(D-1-j))%2 == 1:
                continue
            elif score_tmp + p[D-1-j]*(D-j)*100 < G:
                break
            else:
                ans_tmp += math.ceil((G - score_tmp)/((D-j)*100))
                ans = min(ans,ans_tmp)
                break

print(ans)

Submission status: Accepted

Solution code:
n, g = map(int, input().split())
inps = []
for i in range(1, n + 1):
    inp = list(map(int, input().split()))
    inp.append(inp[0] * i * 100 + inp[1])
    inp.append(i)
    inps.append(inp)
def at(items, goal):
    if goal <= 0:
        return 0
    result = 0
    for t, c, a, i in reversed(items):
        tn = i * 100
        cnt = min(t - 1, (goal + tn - 1) // tn)
        result += cnt
        goal -= cnt * tn
        if goal <= 0:
            return result
    return float("inf")
result = []
for i in range(2 ** n):
    items = []
    other = []
    for item in inps:
        (items if i & 1 else other).append(item)
        i >>= 1
    tcnt = sum(map(lambda x: x[0], items))
    acnt = sum(map(lambda x: x[2], items))
    ncnt = at(other, g - acnt)
    result.append(tcnt + ncnt)
print(min(result))

Submission status: Accepted

Solution code:
if_debag = False

input_texts = """5 25000
20 1000
40 1000
50 1000
30 1000
1 1000"""

input_texts = input_texts.split('\n')
it = iter(input_texts)
#next(it)

def my_input():
    if if_debag:
        return next(it)
    else:
        return input()

d, g = map(int, my_input().split())
ps = list()
cs = list()
for i in range(d):
    p, c = map(int, my_input().split())
    ps.append(p)
    cs.append(c)

minv = 2000
for i in range(1 << d):
    toita_mondai = 0
    sougou_tensu = 0
    for j in range(d):
        if (i >> j) & 1:
            toita_mondai += ps[j]
            sougou_tensu += (j + 1) * 100 * ps[j] + cs[j]
    if sougou_tensu >= g:
        minv = min(minv, toita_mondai)
    else:
        nokori = g - sougou_tensu
        flag = False
        for j in range(d - 1, -1, -1):
            if (i >> j) & 1:
                continue
            for _ in range(ps[j]):
                nokori -= 100 * (j + 1)
                toita_mondai += 1
                if nokori <= 0:
                    minv = min(minv, toita_mondai)
                    flag = True
                    break
            if (flag): break        
print(minv)

Submission status: Accepted

Solution code:
import numpy as np
n, g = map(int, input().split())
inps = []
for i in range(1, n + 1):
    inp = list(map(int, input().split()))
    inp.append(inp[0] * i * 100 + inp[1])
    inp.append(i)
    inps.append(inp)

def at(items, goal):
    if goal <= 0:
        return 0

    # while goal > 0:
    result = 0
    for t, c, a, i in reversed(items):
        tn = i * 100
        cnt = min(t - 1, (goal + tn - 1) // tn)
        result += cnt
        goal -= cnt * tn
        if goal <= 0:
            return result
    return float("inf")

#%%
result = []
for i in range(2 ** n):
    items = []
    other = []
    for item in inps:
        (items if i & 1 else other).append(item)
        i >>= 1

    # ncnt
    tcnt = sum(map(lambda x: x[0], items))
    acnt = sum(map(lambda x: x[2], items))
    ncnt = at(other, g - acnt)
    result.append(tcnt + ncnt)
print(min(result))

Submission status: Accepted

Solution code:
d, g = map(int, input().split())
p = []
c = []
ans = 10 ** 100
for _ in range(d):
    a, b = map(int, input().split())
    p.append(a)
    c.append(b)

for bit in range(1 << d):
    point, cnt = 0, 0
    for i in range(d):
        if bit >> i & 1:
            point += (i+1) * 100 * p[i] + c[i]
            cnt += p[i]

    if g <= point:
        ans = min(ans, cnt)
    else:
        for i in reversed(range(d)):
            if not(bit >> i & 1):
                for j in range(p[i]):
                    if point >= g:
                        break
                    point += 100 * (i+1)
                    cnt += 1
        ans = min(ans, cnt)
print(ans)

Submission status: Accepted

Solution code:
d,g = map(int,input().split())
a = list(list(map(int, input().split())) for x in range(d))

minmin = 100000

for i in range(0,2**d):
    f = [True]
    min = 0
    sum = 0
    binary = format(i, 'b')
    binary = binary[::-1]
    # binary
    list2=[i for i, x in enumerate(binary) if x == '1']
    # print(list2)
    for i in range(len(list2)):
        sum+=a[list2[i]][0]*100*(list2[i]+1)+a[list2[i]][1]
        min += a[list2[i]][0]
    if (sum<g) and (len(list2)<d):
        # print("ぽうぽう")
        d2 = d-1
        while (1):
            # print("ぽうぽう1")
            if len(list2)==0:
                break
            if d2 in list2:
                d2 = d2-1
                continue
            else:
                break
        l = 0 
        while(sum<g):
            if l >= a[d2][0]:
                f[0]=False
                break
            # print("ぽうぽう2")
            min +=1
            sum += 100*(d2+1)
            l += 1
        if sum<g:
            f[0]=False
    if (f[0]==True)and(min < minmin):
        minmin = min
        # print(min,sum)
    


print(minmin)

Submission status: Accepted

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

A=[map(int,raw_input().split()) for i in range(D)]

N=1000
dp=[ [ float("-inf") for i in range(N+100)]  for j in range(D) ] 

p=A[0][0]
c=A[0][1]


for i in range(1,p+1):
	if i==p: dp[0][i]=i*100+c
	else: dp[0][i]=i*100

for i in range(D):
	dp[i][0]=0



for k in range(1,D):
	p=A[k][0]    # number of problems per line
	c=A[k][1]    # bonus

	for i in range(N):		         #dp[k][i]
		for j in range(1,p+1):    #number of problems per line
			dp[k][i+j]=max( dp[k][i+j], dp[k-1][i]+j*(k+1)*100, dp[k-1][i+j] )
		dp[k][i+j]=max( dp[k][i+j], dp[k-1][i]+j*(k+1)*100+c,dp[k-1][i+j] )



for idx,i in enumerate(dp[D-1]):
	if i>=G:
		print idx
		quit()

Submission status: Accepted

Solution code:
import math

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

answer = 1001
for i in range(2 ** d):
    sc = 0
    pr = 0
    for j in range(d, 0, -1):
        if i & (1 << (j - 1)) > 0:
            sc += j * 100 * p[j - 1] + c[j - 1]
            pr += p[j - 1]
    for j in range(d, 0, -1):
        if sc < g and i & (1 << (j - 1)) == 0:
            temp = min(math.ceil((g - sc) / (j * 100)), p[j - 1] - 1)
            sc += temp * (j * 100)
            pr += temp
    if sc >= g and pr < answer:
        answer = pr

print(answer)

Submission status: Accepted

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

S=list(itertools.product(range(2),repeat=D))
ans=sum(p)
for seq in S:
    score=0
    prove=0
    for i in range(D):
        if seq[i]==1:
            score+=(p[i]*100*(i+1)+c[i])
            prove+=p[i]
    if score>=G:
        if ans>prove:
            ans=prove
        continue
    j=-1
    for i in range(D):
        if seq[i]==0:
            j=i
    for k in range(p[j]):
        prove+=1
        score+=100*(j+1)
        if G<=score:
            break
    if G>score:
        continue
    if ans>prove:
        ans=prove
print(ans)

Submission status: Accepted

Solution code:
d, g = map(int, input().split())
a = [tuple(map(int, input().split())) for _ in range(d)]
r = float('inf')
for b in range(1<<d):
    x = n = 0
    j = -1
    for i in range(d):
        if b & 1<<i:
            p, c = a[i]
            x += p*(i+1)*100+c
            n += p
        else:
            j = i
    if j != -1:
        p, c = a[j]
        y = 100*(j+1)
        m = max(0,g-x+y-1)//y
        if m < p:
            x += m*y+c
            n += m
    if x >= g:
        r = min(r, n)
print(r)

Submission status: Accepted

Solution code:
import math
D,G = map(int,input().split())
p=[]
c=[]
for i in range(D):
    p_tmp,c_tmp = map(int,input().split())
    p.append(p_tmp)
    c.append(c_tmp)

ans = sum(p)
for i in range(2**D):
    score_tmp = 0
    ans_tmp = 0
    for j in range(D):
        if (i>>j)%2 == 1:
            score_tmp += p[j]*(j+1)*100+c[j]
            ans_tmp += p[j]

    if ans_tmp >= ans:
        continue
    elif score_tmp >= G:
        ans = min(ans,ans_tmp)
        continue
    else:
        for j in range(D):
            if (i>>(D-1-j))%2 == 1:
                continue
            elif score_tmp + p[D-1-j]*(D-j)*100 < G:
                break
            else:
                ans_tmp += math.ceil((G - score_tmp)/((D-j)*100))
                ans = min(ans,ans_tmp)
                break

print(ans)

Submission status: Accepted

Solution code:
D,G = map(int,input().split())
G = G/100
P = []; C = []
for i in range(D):
  p,c = map(int,input().split())
  P.append(p)
  C.append(c/100)
m = 10**3
for k in range(2**D):
  R = list(range(D))[::-1]
  point = G
  prob = 0
  for d in range(D):
    if k & 1<<d:
      p = P[d]; c = C[d]
      point -= (d+1)*p + c
      prob += p
      R.remove(d)
  for r in R:
    if point > 0:
      p = P[r]
      if point/(r+1) <= p:
        prob += -(-point//(r+1))
        point = 0
      else:
        point -= (r+1)*p + C[r]
        prob += p
  if m >= prob:
    m = prob
print(int(m))

Submission status: Accepted

Solution code:
from itertools import product
d,g = (int(i) for i in input().split())
p = [[int(i) for i in input().split()] for i in range(d)]
q,ans = [],1001
for i in range(d): q.append(p[i][0]*(i+1)*100+p[i][1]) 
for i in product(range(2), repeat=d):
	m,n,x = 0,0,[]
	for j in range(d):
		if i[j]==1: m,n = m+q[j],n+p[j][0]
		else: x.append(j)
	if m>=g: ans = min(ans,n)
	else:
		for k in x:
			num = (g-m+99)//((k+1)*100)
			if num<p[k][0]: ans = min(ans,n+num)
print(max(1,ans))

Submission status: Accepted

Solution code:
D, G = [int(_) for _ in input().split()]
PC = [tuple(int(_) for _ in input().split()) for i in range(D)]
P = [_[0] for _ in PC]
C = [_[1] for _ in PC]

from itertools import product
from math import ceil

INF = 10**20

def calc(pat):
    solved_promlems = 0
    total_score = 0
    left = None
    for e, score, problem_nums, complete_score in zip(pat, range(100, (D+1)*100, 100), P, C):
        if e:
            total_score += score * problem_nums + complete_score
            solved_promlems += problem_nums
        else:
            left = score, problem_nums
    if total_score >= G:
        return solved_promlems
    if left:
        score, problem_nums = left
        n = ceil((G - total_score) / score)
        if 1 <= n < problem_nums:
            return solved_promlems + n
    return INF

result = min(calc(pat) for pat in product((0, 1), repeat=D))

print(result)

Submission status: Accepted

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

from itertools import product

INF = 10**20

def calc(es):
    r = 0
    last_row = None
    result = 0
    for i, e, pc in zip(range(D), es, PC):
        d = (i+1) * 100
        if e:
            r += d * pc[0] + pc[1]
            result += pc[0]
        else:
            last_row = d, pc[0]
    if r >= G:
        return result
    if last_row:
        n = (G - r + last_row[0] - 1) // last_row[0]
        if 1 <= n < last_row[1]:
            return result + n
    return INF

result = min(calc(pat) for pat in product((0, 1), repeat=D))

print(result)

Submission status: Accepted

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

from itertools import product

def calc(D, G, PC, es):
    r = 0
    k = None
    result = 0
    for i, e, pc in zip(range(D), es, PC):
        if e:
            r += (i+1) * 100 * pc[0] + pc[1]
            result += pc[0]
        else:
            k = i
    if r >= G:
        return result, r
    if not k is None:
        d = (k+1)*100
        p = PC[k][0]
        if r + d * (p - 1) >= G:
            n = (G - r + d - 1) // d
            result += n
            r += n * d
            return result, r
    return None, None

result = 10**20

for es in product((0, 1), repeat=D):
    r, score = calc(D, G, PC, es)
    #print(D, G, PC, es, r, score)
    if not r is None:
        result = min(result, r)

print(result)

Submission status: Accepted

Solution code:
def main():
    """
    1 <=  D <= 100
    1 <= pi <= 100
    1 <=  i <= D
    100 <= G
    100 <= ci <= 10^6

    all: sum(p)
        max: 100 * 10 = 1000
    """
    D, G = map(int, input().split())
    P, C = zip(*(
        map(int, input().split())
        for _ in range(D)
    ))

    # ans = f(D, G, P, C)
    ans = editorial(D, G, P, C)
    print(ans)


def editorial(D, G, P, C):
    ans = float("inf")
    for i in range(2 ** D):
        c = 0
        score = 0
        clear = [False] * D
        for j in range(D):
            if i & (1 << j):
                c += P[j]
                score += 100 * (j + 1) * P[j] + C[j]
                clear[j] = True

        # print(i, clear, c, score)
        for j in range(D)[::-1]:
            if score >= G:
                break
            if clear[j]:
                continue

            rest = G - score
            base_score = 100 * (j + 1)
            add_c = (rest + base_score - 1) // base_score
            add_c = min(add_c, P[j] - 1)
            c += add_c
            score += base_score * add_c

            # print("\t", base_score, c, score)

        if score >= G:
            ans = min(ans, c)

    return ans


def f(D, G, P, C):
    """
    i, P から問題をすべて分割
    すべての解き方を列挙する
    sum_p ! = 1000 ! => TLE

    点数の高いものから解けばいいとは限らない

    dpっぽく前の解き方を利用してみる
    ans[0] = 0
    ans[1] = max_i * 100 or ボーナスあり
        ボーナスがあるので、前の答え＋点の良い問題とは限らない
        前の解き方のうち、１つ変えるとどうなるか？
            ボーナスがなくなってしまうかもしれない
            代わりにボーナスになる可能性もある
            前の解き方からｘ問変えるとどうなるか？
                同様
    ボーナスもらえるテーブルを作る？
        それとボーナス加味しないDPテーブルとの比較
        b_dp[5] = p1 全完了
        dp[2] = p2
            fix[]
    """
    from itertools import permutations
    from collections import defaultdict

    sum_p = sum(P)
    dp = [float("inf") for _ in range(sum_p + 1)]
    dp[0] = 0
    max_state = {}

    # 総スコアと効率、
    total = [(i + 1) * 100 * P[i] + C[i] for i in range(D)]
    ratio = [total[i] / P[i] for i in range(D)]
    bonus = [False for _ in range(D)]
    for i in range(1, sum_p + 1):
        score = 0
        rest = i
        for j in range(D):
            if bonus[j]:
                rest -= P[j]
                score += total[j]
            elif P[j] <= rest:
                bonus[j] = True
                rest -= P[j]
                score += total[j]

        if dp[i] >= G:
            return i


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
D, G = map(int, input().split())
problem = []
bonus = []
for i in range(D):
    pi, ci = map(int, input().split())
    problem.append(pi)
    bonus.append(ci)
ans = float('inf')
for S in range(1 << D):  # Sは2^Dの元
    score = sum([(problem[j] * 100 * (j + 1) + bonus[j]) * ((S >> j) & 1) for j in range(D)])
    count = sum([problem[j] * ((S >> j) & 1) for j in range(D)])
    if score >= G:
        ans = min(ans,count)
    else:
        for i in range(D):
            if (S >> i) & 1 == 0 and score + problem[i] * 100 * (i + 1) >= G: #Sにiが含まれないとき
                count_2 = count + (G - score + (100 * (i + 1)) - 1) // (100 * (i + 1))
                ans = min(ans, count_2)
print(ans)

Submission status: Accepted

Solution code:
import math

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

ans = float('inf')

for i in range(1 << D): # bit全探索
    solved = [a for a in range(D)] # 全て解く＝ボーナス点をもらう問題群
    count = 0
    point = 0
    for j in range(D): # 全て解く＝ボーナス点をもらう問題群の点数合計
        if i & (1 << j): # (j + 1) * 100 点の問題を全て解く場合
            count += Problems[j][0]
            point += Problems[j][0] * (j + 1) * 100 + Problems[j][1]
            solved.remove(j) # (j + 1) * 100 点の問題は全て解答済
    if point < G and len(solved) > 0:
        k = max(solved)
        if math.ceil((G - point) / ((k + 1) * 100)) > Problems[k][0] - 1:
            continue
        else:
            count += math.ceil((G - point) / ((k + 1) * 100))
            ans = min(ans, count)
    else:
        ans = min(ans, count)

print(ans)

Submission status: Accepted

Solution code:
from itertools import product
D, G = map( int, input().split())
P = []
C = []
SUM = []
for i in range(D):
    p, c = map( int, input().split())
    P.append(p)
    SUM.append(p*100*(i+1) + c)

ans = 1000
for X in product(range(2), repeat = D):
    cnt = 0
    com = 0
    K = []
    for i in range(D):
        if X[i] == 1:
            cnt += P[i]
            com += SUM[i]
        else:
            K.append(i)
    if com >= G:
        ans = min(ans, cnt)
    else:
        for k in K:
            need = min((G-com-1)//(100*(k+1))+1,P[k]-1)
            kcnt = cnt + need
            kcom = com + need*100*(k+1)
            if kcom >= G:
                ans = min(ans,kcnt)
print(ans)

Submission status: Accepted

Solution code:
D, G = map(int, input().split())
problem = []
bonus_score = []
for i in range(D):
    pi, ci = map(int, input().split())
    problem.append(pi)
    bonus_score.append(ci)
total_problem = sum(problem)
dp= [[0 for k in range(total_problem + 1)] for i in range(D+1)]

for i in range(D):
    for k in range(total_problem + 1):
        for j in range(min(problem[i], k) + 1):
            dp[i+1][k] = max(dp[i+1][k], dp[i][k - j] + (i + 1) * 100 * j + (j//problem[i]) * bonus_score[i])
ans = 0
while dp[D][ans] < G:
    ans += 1
print(ans)

Submission status: Accepted

Solution code:
D,G = list(map(int,input().split()))
L=[]
for i in range(D):
    L.append(list(map(int,input().split())))
for i in range(D):
    L[i].append(L[i][0]*(i+1)*100)
    L[i].append(L[i][2]+L[i][1])
answer = 10**4
for bits in range(1<<D):
    point_sum = 0
    n = 0
    j = -1
    for i in range(D):
        if bits & 1<<i:
            point_sum += L[i][3]
            n += L[i][0]
        else:
            j = max(j, i)
    if point_sum >= G:
        answer = min(answer, n)
    elif j >=0 and (point_sum+L[j][2])-(j+1)*100 >= G:
        a = G - point_sum
        b = (j+1)*100
        answer = min(answer, n+int((a+b-1)/b))
    else:
        pass
print(answer)

Submission status: Accepted

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

ans = float('inf')

for i in range(1 << D):
    number = 0
    score = 0
    chosen = []
    for j in range(D):
        if (1 & (i >> j)) == 1:
            chosen.append(j)
            score += P[j][0] * 100 * (j+1) + P[j][1]
            number += P[j][0]

    index = D-1
    while score < G:
        if index < 0:
            break
        if index in chosen:
            pass
        else:
            for _ in range(1, P[index][0]+1):
                score += 100 * (index + 1)
                number += 1

                if score >= G:
                    break

        index -= 1
    ans = min(ans, number)
            

print(ans)

Submission status: Accepted

Solution code:
D, G = map(int, input().split())
set, full = [],[]
for i in range(D):
    set.append(list(map(int, input().split())))
    full.append((i + 1)*100*set[i][0] + set[i][1])

minNum = 1001
for i in range(2 ** D):
    a = list(format(i, "b").zfill(D))
    total, num , largest= 0, 0, 0
    for j in range(D):
        if a[j] == "1":
            total += full[j]
            num += set[j][0]
        else:
            largest = j
    if total >= G:
        minNum = (num if num < minNum else minNum)
    else:
        for j in range(1, set[largest][0]):
            total += (largest + 1) * 100
            num += 1
            if total >= G:
                minNum = (num if num < minNum else minNum)

print(minNum)

Submission status: Accepted

Solution code:
I=input().split()
D=int(I[0])
G=int(I[1])
P=[]
C=[]
sumS=[]
ans=10**4
for i in range(0,D):
    T=input().split()
    P.append(int(T[0]))
    C.append(int(T[1]))
    sumS.append((i+1)*100*P[i]+C[i])
for i in range(0,2**D):
    t=i
    point=0
    cost=0
    used=[]
    for j in range(0,D):
        if(t%2==1):
            point+=sumS[j]
            cost+=P[j]
            used.append(True)
        else:
            used.append(False)
        t//=2
    if(point<G):
        t=i
        f=False
        for j in range(0,D)[::-1]:
            if(not used[j]):
                f=True
                for k in range(1,P[j]):
                    point+=(j+1)*100
                    cost+=1
                    if (point>=G):
                        break
            if f:
                break
    if(point>=G):
        if(ans>cost):
            ans=cost
print(ans)

Submission status: Accepted

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

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

bit_table = list(product([0, 1], repeat=D))
cnts = []
for bits in bit_table:
    g = sum([
        pc_table[i][1] + 100 * (i + 1) * pc_table[i][0]
        for i, bit in enumerate(bits) if bit
    ])
    cnt = sum([pc_table[i][0] for i, bit in enumerate(bits) if bit])

    max_p = 0 if sum(bits) == D else max(
        [i for i, bit in enumerate(bits) if not bit])
    for _ in range(pc_table[max_p][0]):

        if g >= G:
            cnts.append(cnt)
            break
        else:
            g += 100 * (max_p + 1)
            cnt += 1

print(min(cnts))

Submission status: Accepted

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

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

bit_table = list(product([0, 1], repeat=D))
cnts = []
for bits in bit_table:
    g = sum([
        pc_table[i][1] + 100 * (i + 1) * pc_table[i][0]
        for i, bit in enumerate(bits) if bit
    ])
    cnt = sum([pc_table[i][0] for i, bit in enumerate(bits) if bit])

    if g >= G:
        cnts.append(cnt)

    else:
        max_p = max([i for i, bit in enumerate(bits) if not bit])
        for _ in range(pc_table[max_p][0]):
            g += 100 * (max_p + 1)
            cnt += 1
            if g >= G:
                cnts.append(cnt)
                break

print(min(cnts))

Submission status: Accepted

Solution code:
import math
from itertools import chain, combinations



D, G = map(int, input().split())
p = []
c = []

for _ in range(D):
    p_in, c_in = map(int, input().split())
    p.append(p_in)
    c.append(c_in)

# ボーナスを使う

def powerset(itr):
    s = list(itr)
    return chain.from_iterable(combinations(s, r) for r in range(len(s)+1))


# フルコン時の点数
fullcon = []
for i in range(D):
    score = 100 * (i + 1) * p[i] + c[i]
    fullcon.append(score)


use_flag_itr = range(D)
use_flag_set = powerset(use_flag_itr)

mincount = 100 * 10

for use_flag in use_flag_set:
    fullscore = 0
    fullcount = 0
    for i in use_flag:
        fullcount += p[i]
        fullscore += fullcon[i]

    remain = G - fullscore

    if remain <= 0:
        if mincount > fullcount:
            mincount = fullcount 
        continue



    for i in reversed(range(D)):
        if i in use_flag:
            continue

        score = 100 * (i + 1) 
        if score * p[i] > remain:
            new_count = fullcount +  int(math.ceil(remain / score))
            if mincount > new_count:
                mincount = new_count
        break

print(mincount)