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 = [list(map(int, input().split())) for i in range(d)]
ans = float("inf")
# 解いていない問題の配点をrestとして保持しておく。
# iは解いた問題の種類(配点/100)
# countは解いた問題の数
def dfs(i,sum,count,rest):
    # global変数としてansを引継ぎ
    global ans
    if i == d:
        # 合計がgoalを超えていなければrestに残っている問題の中で最大の得点の問題を解いていく。
        if sum < g:
            use = max(rest)
            n = min(pc[use-1][0], -(-(g-sum)//(use*100)))
            count += n
            sum += n*use * 100
            
        # 合計値が与えられた得点を超えていたら，最小の問題数を答える。
        if sum >= g:
            ans = min(ans, count)
            
    else:
        # 総合スコア，解いた問題数，まだ解いていない問題を更新する。
        # i得点の問題を解かないで次に進める場合
        dfs(i + 1, sum, count, rest)
        # i得点の問題を解いて先に進める場合，得点と問題数を加え，restからその得点要素を消去
        dfs(i + 1, sum + pc[i][0] * (i+1) * 100 + pc[i][1], count + pc[i][0], rest - {i+1})


dfs(0,0,0,set(range(1,d + 1)))

# 関数内で定義したグローバル変数を出力する
print(ans)

Submission status: Accepted

Solution code:
inf = 10**18
mod = 10**9+7
n, k = map(int, input().split())
pc = [list(map(int, input().split())) for i in range(n)]
pc.reverse()
ans = inf
for i in range(2**n):
    acc=0
    accn=0
    for j in range(n):
        if ((i >> j) & 1):  # 1だったら(オンだったら)
            p,c = pc[j]
            acc+=((n-j)*100*p+c)
            accn+=p
            if acc>=k:
                ans=min(ans, accn)
    if k-acc >= 0:
        for j in range(n):
            if not ((i >> j) & 1):  # 0だったら(おふだったら)
                p, c = pc[j]
                if k - acc > ((n - j) *100* (p - 1)):
                    acc += ((n - j) *100* (p - 1))
                    accn += (p - 1)
                else:
                    tmp = (k-acc+(n-j)*100-1)//((n-j)*100)
                    acc += ((n - j) *100* tmp)
                    accn += tmp
                    ans = min(ans, accn)
                    break
print(ans)

Submission status: Accepted

Solution code:
# import sys

d, g = map(int, input().split())
A = []

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

ans = 10000

for i in range(2**d):
    score = 0
    num = [0 for _ in range(d)]
    cur = i
    for j in range(d):
        if cur % 2 == 1:
            num[j] = A[j][0]
            score += A[j][0] * 100 * (j+1) + A[j][1]
        cur //= 2
    if score < g:
        for j in range(d)[::-1]:
            if num[j] == 0:
                rest = g - score
                poi = 100 * (j+1)
                tmp = - (- rest // poi)
                if tmp < A[j][0]:
                    num[j] = tmp
                else:
                    num[j] = 10000
                break
    ans = min(ans, sum(num))

print(ans)

Submission status: Accepted

Solution code:
import itertools
import math
D, G = list(map(int, input().split(' ')))
p_list = list()
c_list = list()
for _ in range(D):
    p, c = list(map(int, input().split(' ')))
    p_list.append(p)
    c_list.append(c)
ans = sum(p_list)
pattern_list = itertools.product([0, 1], repeat=D)
for pattern in pattern_list:
    score = 0
    prob_num = 0
    # Solve all problems with bit `1`
    score += sum([bit * (100 * (index + 1) * p_list[index] + c_list[index]) for index, bit in enumerate(pattern)])
    prob_num += sum([bit * p_list[index] for index, bit in enumerate(pattern)])
    # Solve problems partially with bit `0'
    if score < G:
        for index in range(D - 1, -1, -1):
            if pattern[index] == 1:
                # skip because these cases are already counted
                continue
            required_num = math.ceil((G - score) / (100 * (index + 1)))
            sol_num = min([p_list[index] - 1, required_num])
            score += 100 * (index + 1) * sol_num
            prob_num += sol_num
            if score >= G:
                break
    # update answer
    if score >= G:
        ans = min([ans, prob_num])
print(ans)

Submission status: Accepted

Solution code:
"""解説から写経
D種類の配点の問題があり、それらを最低何問解けばG点以上取ることができるかを求める。
続くD行の入力から、配点iの問題数p[i]と追加点c[i]が与えられ、配点は100*(i+1)点となる。
追加点は配点i問題を全て解いたときに得られる追加点。

条件が成立する最小の問題数をansとし、とても大きな値で初期化しておく。
各配点の問題を全て解くか、解かないかを最初に決め、G点以上取れるかどうか、また、その時の解答数を確認していく。(bit全探索)
現在の点数、解答数、解かなかった問題の中で最も配点の高かったものをそれぞれ、s, num, rest_maxとする。
完全に解く問題を解き終えて、G点に満たなかった場合、配点[rest_max]をいくつか解くことでG点が取れるか確認していき、必要な解答数をneedとする。
この時、p[rest_max]-1より多く問題を解く必要があるなら、解答する問題の選択を間違えていると言えるので無視する。
num+needがansよりも少ない場合、ansの値を更新する。
"""
d, g = map(int, input().split())
pc = []
for _ in range(d):
    pc.append(tuple(map(int, input().split())))
ans = float('inf')
for bits in range(1 << d):
    s = 0
    num = 0
    rest_max = -1
    for i in range(d):
        p, c = pc[i]
        if bits >> i & 1:
            s += 100 * (i + 1) * p + c
            num += p
        else:
            rest_max = i
    if s < g:
        s1 = 100 * (rest_max + 1)
        need = (g - s + s1 - 1) // s1  # s1-1を足すのは切り上げ？
        if need >= pc[rest_max][0]:
            continue
        num += need
    ans = min(ans, num)
print(ans)

Submission status: Accepted

Solution code:
def main():
    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())
    S = [0]*D
    ans = sum(P)
    for i in range(D):
        S[i] = (i + 1) * 100 * P[i] + C[i]
    # print(D, G, P, C, S)
    for i in range(2**D):
        score = 0
        count = 0
        num_solved = 0
        solved = [0]*D

        while i > 0:
            if i % 2 == 1:
                score += S[count]
                num_solved += P[count]
                solved[count] = 1
            i //= 2
            count += 1
        if score >= G:
            ans = min(ans, num_solved)
        else:
            d = G - score
            # print('d={}'.format(d))
            for j in range(D):
                index = D - j - 1
                # print('index={}, solved={}'.format(index, solved))
                if solved[index] == 1:
                    continue
                required = (d + (index + 1) * 100 - 1) // ((index + 1) * 100)
                # print('required={}'.format(required))
                if required < P[index]:
                    num_solved += required
                    ans = min(ans, num_solved)
                break
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
D,G = map(int, input().split())
ps,cs = [],[]
for i in range(D):
    p,c = map(int, input().split())
    ps.append(p)
    cs.append(c)
    
limit=1<<D
ans = sum(ps)
for a in range(0,limit):
    s,p,i = 0,0,D-1
    b = 1<<(D-1)
    upperIndex = 0
    while (s<G and b>0):
        if (a&b!=0):
            s += ps[i]*100*(i+1)+cs[i]
            p += ps[i]
        else:
            upperIndex=max(upperIndex,i)
        b>>=1
        i-=1

    for j in range(ps[upperIndex]):
        if (s>=G):
            ans = min(ans,p)
            break
        s += 100*(upperIndex+1)
        p += 1
print(ans)

Submission status: Accepted

Solution code:
D, G = map(int, input().split())
G //= 100
P = [0] * D
S = [0] * D
for i in range(D):
    p, c = map(int, input().split())
    P[i] = p
    S[i] = (i + 1) * p + c // 100
ans = 10**9
for i in range(2**D):
    tmp = G
    res = 0
    idx = -1
    bi = bin(i)[2:].zfill(D)
    for j, b in enumerate(bi):
        if b == '1':
            tmp -= S[j]
            res += P[j]
        else:
            idx = j
    if tmp > 0 and tmp - (P[idx] - 1) * (idx + 1) <= 0:
        k = (tmp + idx) // (idx + 1)
        tmp -= (idx + 1) * k
        res += k
    if tmp <= 0:
        ans = min(ans, res)

print(ans)

Submission status: Accepted

Solution code:
d,g=map(int,input().split())
l=[list(map(int,input().split())) for i in range(d)]
ans=float("INF")
for i in range(2**d):
    allgreen={j for j in range(d) if (i>>j)%2}
    su=sum(l[k][0]*100*(k+1)+l[k][1] for k in allgreen)
    now=sum(l[k][0] for k in allgreen)
#    print(now)
    for k in range(d-1,-1,-1):
        if su>=g:break
        p,c=l[k]
        if k in allgreen:continue
        else:
            jk=min(-(-g+su)//((k+1)*100),p-1)
            now+=jk
            su+=jk*100*(k+1)
#            print(i,jk)
    if su>=g:ans=min(ans,now)
print(ans)

Submission status: Accepted

Solution code:
def dfs (i,sum,count,rem):
    global ans
    if i == D:
        if sum < G:
            k = max(rem)
            n = min(pc[k-1][0],-(-(G-sum)//(k*100)))
            count += n
            sum += n*100*k
        if sum >= G:
            ans = min(ans,count)
    else:
        dfs(i+1,sum,count,rem)
        dfs(i+1,sum+pc[i][0]*100*(i+1)+pc[i][1],count+pc[i][0],rem-{i+1})

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

ans = float("inf")

dfs(0,0,0,set(range(1,D+1)))
print(ans)

Submission status: Accepted

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

#print(pc)
ans = float("inf")

for i in range(2**D):
    sum = 0
    count = 0
    rem = set(range(1,D+1))
    for j in range(D):
        if (i >> j) & 1:
            sum += pc[j][0]*100*(j+1)+pc[j][1]
            count += pc[j][0]
            rem.discard(j+1)
    if sum < G:
        k = max(rem)-1
        n = min(pc[k][0],-(-(G-sum)//((k+1)*100)))
        count += n
        sum += n*100*(k+1)
    if sum >= G:
        ans = min(ans,count)

print(ans)

Submission status: Accepted

Solution code:
d,g = map(int,input().split())
P,C=[],[]
ans = 10**9
for i in range(d):
  p,c = map(int,input().split())
  P.append(p)
  C.append(c)

for i in range(2**d):
  score,solved_num,max_unsolve = 0,0,0
  for j in range(d):
    if i>>j&1:
      point = (j+1)*100
      simple_sum = point * P[j]
      add_bonus_sum = simple_sum + C[j]
      score += add_bonus_sum
      solved_num += P[j]
    else:
      max_unsolve = max(max_unsolve, j)
  if score >= g:
    ans = min(ans, solved_num)
  else:
    dif = abs(g-score)
    max_unsolve_point = (max_unsolve+1)*100
    nece_num = (dif+max_unsolve_point-1)//max_unsolve_point
    if nece_num<=P[max_unsolve]:
      ans = min(ans, solved_num+nece_num)
print(ans)

Submission status: Accepted

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

p = [0] * 10
c = [0] * 10

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

ans = float("inf")
for mask in range(1<<d):
    s = 0; num = 0; rest_max = -1
    for i in range(d):
        if mask >> i & 1:
            s += 100 * (i+1) * p[i] + c[i]
            num += p[i]
        else:
            rest_max = i

    if s < g:
        s1 = 100 * (rest_max + 1)
        need = (g - s +s1 - 1) // s1
        if need >= p[rest_max]:
            continue

        num += need

    ans = min(ans, num)
     
print(ans)

Submission status: Accepted

Solution code:
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): #d個左にシフトする。d=2なら100となって十進法なら4。
    count = 0
    sum = 0
    nokori = [i+1 for i in range(d)]

    for i in range(d): #与えられbitにおいてすべて足し算する。
        if bit & (1 << i):
            sum += pc[i][0] * (i + 1) * 100 + pc[i][1]
            count += pc[i][0]
            nokori.remove(i + 1)

    # G 点に満たなければ nokori のうち一番大きいものを解く
    if sum < g:
        use = max(nokori)
        n = min(pc[use - 1][0], -(-(g - sum) // (use * 100)))
        count += n
        sum += n * use * 100

    if sum >= g:
        ans = min(ans, count)

print(ans)

Submission status: Accepted

Solution code:
import itertools

def solve(D, G, problems):
    bit_list = list(itertools.product([0, 1], repeat=D))
    
    result_count = 10 ** 8
    for pattern in bit_list:
        score = 0 # スコアの合計
        count = 0  # 解いた問題数
        for i in range(D):
            if pattern[i] == 1: # ビット値が１の難易度の問題は全て解く
                score += problems[i][0] * (i+1) * 100 + problems[i][1]  # 問題のスコア + ボーナス点
                count += problems[i][0]
            
            else:
                max_score_problem = i
    
        # 合計スコアが足りない場合，もっともスコアの高い未着手の問題を必要な分だけ解く
        if score < G:
            for i in range(problems[max_score_problem][0]):
                count += 1
                score += (max_score_problem + 1) * 100
                if score >= G:
                    break
        
        if score >= G:
            result_count = min(result_count, count)
            
    print(result_count)
    

if __name__ == '__main__':
    D, G = map(int, input().split())
    problems = [list(map(int, input().split())) for _ in range(D)]
    solve(D, G, problems)

Submission status: Accepted

Solution code:
# solution

nim, mike = map(int, input().split())

P = []

C = []

ans = 10 ** 9

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

for i in range(2 ** nim):
    a = 0
    b = 0
    for j in range(nim):
        if (i >> j) & 1 :
            a += 100 * P[j] * (j + 1) + C[j]
            b += P[j]
    for k in range(nim - 1, -1, -1):
        if (i >> k) & 1:
            continue
        if a >= mike:
            break
        for l in range(P[k] + 1):
            a += 100 * (k + 1)
            b += 1
            if a >= mike:
                break
    ans = min(ans, b)

print(ans)

Submission status: Accepted

Solution code:
#from statistics import median
#import collections
#aa = collections.Counter(a) # list to list || .most_common(2)で最大の2個とりだせるお a[0][0]
#from itertools import combinations # (string,3) 3回
#from collections import deque
#import collections.defaultdict(list)
#import bisect
#
#    d = m - k[i] - k[j]
#    if kk[bisect.bisect_right(kk,d) - 1] == d:
#
#
#
# pythonで無理なときは、pypyでやると正解するかも！！
#
#

mod = 10**9 + 7

def readInts():
  return list(map(int,input().split()))
def main():
    d,g = readInts()
    P = []
    C = []
    for i in range(d):
        p,c = readInts()
        P.append(p)
        C.append(c)
    res = float('inf')
    for bit in range(1 << d):
        # とりあえず全部まとめて入れる場合を考える
        sum = 0
        num = 0
        for i in range(d):
            if bit & (1 << i):
                sum += C[i] + P[i] * 100 * (i + 1)
                num += P[i]
        if sum >= g:
            res = min(res,num)
        else:
            for i in range(d-1,-1,-1):
                if bit & (1 << i):
                    continue
                for j in range(P[i]):
                    if sum >= g:
                        break
                    sum += 100 * (1 + i)
                    num += 1
            res = min(res,num)
    print(res)
if __name__ == '__main__':
  main()

Submission status: Accepted

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

v=g//100+1
for i in range(2**d):
  c=m=s=0
  for j in range(d):
    if i & 2**j > 0:
      s += p[j][0]*(j+1)*100+p[j][1]
      c += p[j][0]
    else:
      m = j
    if s >= g:
      v=min(v,c)
    elif s+(p[m][0]-1)*(m+1)*100 >=g:
      v=min(v,c+(g-s+100*(m+1)-1)//(100*(m+1)))
print(v)

Submission status: Accepted

Solution code:
import sys
stdin = sys.stdin
inf = 1 << 60
mod = 1000000007
 
ni      = lambda: int(ns())
nin     = lambda y: [ni() for _ in range(y)]
na      = lambda: list(map(int, stdin.readline().split()))
nan     = lambda y: [na() for _ in range(y)]
nf      = lambda: float(ns())
nfn     = lambda y: [nf() for _ in range(y)]
nfa     = lambda: list(map(float, stdin.readline().split()))
nfan    = lambda y: [nfa() for _ in range(y)]
ns      = lambda: stdin.readline().rstrip()
nsn     = lambda y: [ns() for _ in range(y)]
ncl     = lambda y: [list(ns()) for _ in range(y)]
nas     = lambda: stdin.readline().split()

from math import ceil

d, g = na()
pc = nan(d)

ans = inf
for i in range(2 ** d):
    cur = g
    cnt = 0
    for j in range(d - 1, -1, -1):
        p, c = pc[j]
        if i >> j & 1:
            score = (j + 1) * 100 * p + c
            if score < cur:
                cur -= score
                cnt += p
            else:
                cnt += min(p, cur // ((j + 1) * 100))
                cur = 0
                break
    if cnt != 0 and cur == 0:
        ans = min(ans, cnt)

print(ans)

Submission status: Accepted

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

ans = float("INF")
for mask in range(1 << d):
  tmp = 0
  tmp1 = 0
  for j in range(d):
    if 1 << j & mask:
      tmp += pd[j][1]
      tmp += pd[j][0] * 100 * (j + 1)
      tmp1 += pd[j][0]
  if tmp >= g:
    ans = min(ans, tmp1)
    continue
  for j in range(d-1,-1,-1):
    if not(1 << j & mask):
      if tmp + pd[j][0] * 100 * (j + 1) >= g:
        tmp1 += (g - tmp - 1) // (100 * (j + 1)) + 1
        tmp = g
        break
      tmp1 += pd[j][0]
      tmp += pd[j][0] * 100 * (j + 1)
  if tmp >= g:
    ans = min(ans, tmp1)
print(ans)

Submission status: Accepted

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

p_num=[]
for p,c in pc:
    p_num.append(p)

ans = 10**9
def dfs(i,cnt,point,rem_ans):
    global ans
    if i == d:
        if point < g:
            use = max(rem_ans)
            n = min(pc[use-1][0], -(-(g-point)//(use*100)))
            cnt += n 
            point += n * use * 100

        if point >= g:
            ans = min(ans,cnt)

    else:
        dfs(i+1,cnt,point,rem_ans)
        dfs(i+1,cnt+pc[i][0],point+pc[i][0]*(i+1)*100 + pc[i][1],rem_ans - {i+1})

dfs(0,0,0,set(range(1,d+1)))    
print(ans)

Submission status: Accepted

Solution code:
D,G = map(int,input().split())
pc = [list(map(int,input().split())) for i in range(D)]
ans = 10**9
from math import ceil
for i in range(2**D):
    now = 0
    score = 0
    for j in range(D):
        if i>>j & 1:
            now += pc[j][0]
            score += pc[j][0]*100*(j+1) + pc[j][1]

    if score >= G:
        ans = min(ans,now)
    else:
        for j in reversed(range(D)):
            if i>>j & 1 == 0:
                if ceil((G-score)/(100*(j+1))) < pc[j][0]:
                    now += ceil((G-score)/(100*(j+1)))
                    break
        else:
            continue

        if now==0:
            continue
        ans = min(ans,now)

print(ans)

Submission status: Accepted

Solution code:
class P:
  def __init__(self, score, number, bonus):
    self.score = score
    self.number = number
    self.bonus = bonus
    
  def score_at(self, number):
    if number >= self.number:
      return self.score * self.number + self.bonus
    else:
      return self.score * number

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

problems = []

for i in range(D):
  p, c = map(int, input().split())
  problems.append(P((i + 1) * 100, p, c))

  
score_at = [[0] * 1001 for _ in range(D)]
  
# 1001 * 10種類の問題 * 小問100
for num_solved in range(1001):
  for i, p in enumerate(problems):
    for n in range(min(num_solved, p.number) + 1):
      if i == 0:
        score_at[0][n] = p.score_at(n)
      else:
        score_at[i][num_solved] = max(
          score_at[i][num_solved],
          score_at[i - 1][num_solved - n] + p.score_at(n)
        )
  if score_at[D - 1][num_solved] >= G:
    print(num_solved)
    break

Submission status: Accepted

Solution code:
from math import ceil
INF = 10 ** 10

D, G = map(int, input().split())
pairs = [map(int, input().split()) for _ in range(D)]
ps, cs = zip(*pairs)

minimumsolve = INF

for i in range(1 << D):
    solve = 0
    score = 0
    for j in range(D):
        if i & (1 << j):
            solve += ps[j]
            score += ps[j] * 100 * (j+1) + cs[j]
    if score < G:
        for j in range(D-1, -1, -1):
            if not i & (1 << j):
                neededsolve = ceil((G - score) / (100*(j+1)))
                if neededsolve >= ps[j]:
                    solve = INF
                    break
                else:
                    solve += neededsolve
                    break
    minimumsolve = min(minimumsolve, solve)

print(minimumsolve)

Submission status: Accepted

Solution code:
INF = 10 ** 9
import sys
sys.setrecursionlimit(100000000)
dy = (-1,0,1,0)
dx = (0,1,0,-1)
from  heapq import heappop,heapify,heappush
from bisect import bisect_left

def main():
    d,g = map(int,input().split())
    problems = [list(map(int,input().split())) for _ in range(d)]
    
    ans = INF
    for bit in range(1 << d):
        ret = 0
        tot = 0
        left = -1
        for i in range(d):
            if (bit>>i)&1:
                tot += (i + 1) * 100 * problems[i][0] + problems[i][1]
                ret += problems[i][0]
            else:
                left = i
        
        if tot >= g:
            ans = min(ans,ret)
            continue
        
        if tot + (left + 1) * 100 * (problems[left][0] - 1) >= g:
            tmp = (left + 1) * 100
            ret += (g - tot + tmp - 1)//tmp
            ans = min(ans,ret)

    print(ans)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
from collections import namedtuple

# 完答 + 最大1種類の問題が半端に解けている状態のとき最適
# 1. 完投する問題を全探索する 2^10
# 2. 残りの問題から配点が一番高い問題を目標に達するまで解く
# 3. 1,2の中で最も回答問題数が少ないケースが答え

Problem = namedtuple('Problem', 'score number bonus')                      

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

problems = []

for i in range(D):
  p, c = map(int, input().split())
  problems.append(
    Problem(
      score = (i + 1) * 100,
      number = p,
      bonus = c
    )
  )

min_num_solved = sys.maxsize
  
for m in range(1 << D):
  score = 0
  num_solved = 0
  partial = None  # 部分的に解く問題
  
  for i, p in enumerate(problems):
    if 1 << i & m:
      # 完答
      score += p.score * p.number + p.bonus
      num_solved += p.number
    else:
      partial = p

  # 中途半端に解かなくてもいいのなら次へ
  if score >= G:
    min_num_solved = min(min_num_solved, num_solved)
    continue
    
  if partial is None:
    raise Exception('全問題完答したのに目標に届かない')
         
  # 中途半端に解く
  extra_num_solved = 0
    
  while extra_num_solved <= partial.number:
    if score >= G:
      min_num_solved = min(
        min_num_solved,
        num_solved + extra_num_solved
      )
      break
    score += partial.score
    extra_num_solved += 1 
          
print(min_num_solved)

Submission status: Accepted

Solution code:
import sys

INF = sys.maxsize
D, G = map(int, input().split())

class P:
  def __init__(self, index, number, bonus):
    self.index = index
    self.number = number
    self.bonus = bonus
    
  @property
  def score(self):
    return (self.index + 1) * 100
   
  @property
  def complete_score(self):
    return self.score * self.number + self.bonus
  
  # score 獲得するのに必要な解答数
  def cost_of(self, score):
    if score > self.complete_score:
      return INF
    if score == 0:
      return 0
    if score < self.score:
      return 1
    return min(score // self.score, self.number)
  
problems = []
for i in range(D):
  p, c = map(int, input().split())
  problems.append(P(i, p, c))
  
min_number_of_solved = INF

for m in range(1 << D):
  total = 0
  number_of_solved = 0
  uncompleted = set()
  
  for i, p in enumerate(problems):
    if 1 << i & m:  # 完答
      total += p.complete_score
      number_of_solved += p.number
    else:
      uncompleted.add(p)

  # 他の問題を解かなくても条件を満たしている
  if total >= G:
    min_number_of_solved = min(
      min_number_of_solved, 
      number_of_solved
    )
  # 残りの必要点数を最小コストで獲得できる問題を中途半端に解く
  else:
    # 不足する点を最小コストで獲得できる問題を探す
    m = min(uncompleted, key=lambda x: x.cost_of(G - total))
        
    min_number_of_solved = min(
      min_number_of_solved, 
      number_of_solved + m.cost_of(G - total)
    )
                   
print(min_number_of_solved)

Submission status: Accepted

Solution code:
import math

d,g = map(int, input().split())
pc = [list(map(int, input().split())) for i in range(d)]
ans = 10 ** 18
for i in range(2 ** d):
  solve = []
  tmp = 0
  score = 0
  for j in range(d):
    solve.append((i >> j) & 1)
  for j in range(d):
    if not solve[j]:
       continue
    p,c = pc[j]
    tmp += p
    score += p * (j+1) * 100 + c
  if score >= g:
    ans = min(ans, tmp)
    continue
  res = g - score
  for j in range(d-1,-1,-1):
    if not solve[j]:
      point = (j+1) * 100
      p,c = pc[j]
      must = math.ceil(res / point)
      if must <= p:
        tmp += must
        ans = min(ans, tmp)
      break
print(ans)

Submission status: Accepted

Solution code:
import math

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

A = []
for i in range(D):
    A.append(100*(i+1)*d[i][0] + d[i][1])

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

for i in range(2**D):
    a = 0
    g = 0
    B = []
    for j in range(D):
        if (i >> j) & 1:
            a += A[j]
            g += d[j][0]
        else:
            B.append(j)
    b = 0
    for j in B:
        b = max(b,A[j])

    if G-b < a < G+b:
        c = max(B)
        e = math.ceil((G-a)/(100*(c+1)))
        if e <= 0:
            ans = min(ans,g)
        elif e > d[c][0]:
            continue
        else:
            ans = min(ans,g+e)

print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
D, G = [int(str) for str in input().strip().split()]
pc = [[int(str) for str in input().strip().split()] for _ in range(D)]

ans = float('Inf')
sums = [100 * (i + 1) * pc[i][0] + pc[i][1] for i in range(D)]
for bit in range(2 ** D):
    score = 0
    cnt = 0
    for i in range(D):
        if bit & (0x01 << i):
            score += sums[i]
            cnt += pc[i][0]

    i = D - 1
    while score < G and i >= 0:
        if not(bit & (0x01 << i)):
            cnt_now = min(-(-(G - score) // (100 * (i + 1))), pc[i][0])
            cnt += cnt_now
            score += cnt_now * 100 * (i + 1)
        i -= 1

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

print(ans)

Submission status: Accepted

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

# 全部解いたときの点数を前計算
scr = [((i+1)*100)*pc[i][0]+pc[i][1] for i in range(D)]

ans = 10**10
for i in range(2**D):
    a = 0
    c = 0
    for j in range(D):
        if i>>j&1:
            a += scr[j]
            c += pc[j][0]
    if a < G:
        continue
    ans = min(ans,c)
    for j in range(D):
        if i>>j&1:
            a -= scr[j]
            c -= pc[j][0]
            if a >= G:
                continue
            t = (j+1)*100
            if (G-a+t-1)//t < pc[j][0]:
                ans = min(ans,c+(G-a+t-1)//t)
            a += scr[j]
            c += pc[j][0]

print(ans)

Submission status: Accepted

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

scr = [((i+1)*100)*pc[i][0]+pc[i][1] for i in range(D)]

ans = 10**10
for i in range(2**D):
    a = 0
    c = 0
    for j in range(D):
        if i>>j&1:
            a += scr[j]
            c += pc[j][0]
    if a < G:
        continue
    ans = min(ans,c)
    for j in range(D):
        if i>>j&1:
            a -= scr[j]
            c -= pc[j][0]
            if a >= G:
                continue
            if (G-a+((j+1)*100)-1)//((j+1)*100) < pc[j][0]:
                ans = min(ans,c+(G-a+((j+1)*100)-1)//((j+1)*100))
            a += scr[j]
            c += pc[j][0]

print(ans)

Submission status: Accepted

Solution code:
def resolve():
	d, g = map(int, input().split())
	ps = []
	cs = []
	ans = 100**6
	for _ in range(d):
		p, c = map(int, input().split())
		ps.append(p)
		cs.append(c)
	for i in range(d-1, -1, -1):
		total = 0
		solved = 0
		for _ in range(ps[i]):
			if total >= g and ans > solved:
				ans = solved
			total += 100 * (i + 1)
			solved += 1
		total += cs[i]
		if total >= g and ans > solved:
			ans = solved
			break
		for j in range(1 << d):
			done = False
			t_solved = solved
			t_total = total
			for k in range(d-1, -1, -1):
				if (j >> k) & 1:
					if i == k:
						continue
					if done:
						break
					for _ in range(ps[k]):
						if done:
							break
						if t_total >= g and ans > t_solved:
							ans = t_solved
							done = True
							continue
						t_total += 100 * (k+1)
						t_solved += 1
					t_total += cs[k]
					if t_total >= g and ans > t_solved:
						ans = t_solved
	print(ans)
resolve()

Submission status: Accepted

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

#得点の大きい順に並び替えておく
l = l[::-1]

ans = float("inf")
for i in range(2**D):
    total = 0
    cnt = 0
    for j in range(D):
        if (i>>j)&1:
            total += 100*(D-j)*l[j][0] + l[j][1]
            cnt += l[j][0]
    if total >= G:
        ans = min(ans,cnt)
        continue
    for j in range(D):
        if (i>>j)&1 == False:
            for k in range(l[j][0]):
                total += 100*(D-j)
                cnt+=1
                if total >= G:
                    ans = min(ans,cnt)
                    break
            #break

print(ans)