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:
# まだ解いてない配点を nokori として持つ
def dfs(i, sum, count, nokori):
    global ans
    if i == d:
        # 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)
    else:
        # 総合スコア、解いた問題数、まだ解いてない問題を更新
        dfs(i + 1, sum, count, nokori)
        dfs(i + 1, sum + pc[i][0] * (i + 1) * 100 + pc[i][1], count + pc[i][0], nokori - {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())
Q = []
for i in range(D):
    p, c = map(int, input().split())
    Q.append([p, c])

def solve(G, i):
    if i < 0:
        return 10**9
    
    n = min(G//(100*(i+1)), Q[i][0])
    
    p = 100 * (i+1) * n
    if n == Q[i][0]:
        p += Q[i][1]
    
    if p < G:
        ans = n + solve(G-p, i-1)
    else:
        ans = n
    return min(ans, solve(G, i-1))

print(solve(G, D-1))

Submission status: Accepted

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

for j in range(2**d):
    temp = 0
    score = 0
    bit = format(j,"0"+str(d)+"b")
    for i in range(d):
        if bit[i] == "1":
            score += PC[i][0]*(i+1)*100 + PC[i][1]
            temp += PC[i][0]
    if score >= g:
        if temp < cost:
            cost = temp
    else:
        for i in range(d-1,-1,-1):
            if bit[i] == "0":
                p,c = PC[i]
                point = 100*(i+1)
                for v in range(p):
                    score += point
                    temp += 1
                    if score >= g:
                        break
                break
        if score >= g and temp < cost:
            cost = temp
print(cost)

Submission status: Accepted

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

for i in range(2**D):
    point = 0
    num = 0
    leftOvers = []
    for j in range(D):
        if ((i>>j) & 1):
            num += PC[j][0]
            point += PC[j][1] + 100 * (j+1) * PC[j][0]
        else:
            leftOvers.extend([100*(j+1)]*PC[j][0])

    while point < G:
        if not leftOvers:
            break
        point += leftOvers.pop()
        num += 1
    minNum = min(num, minNum)
print(minNum)

Submission status: Accepted

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

ans=1000
for i in range(1<<D):
    # print(bin(i))
    score=0
    problem=0
    highest=0
    for j in range(D):
        if ((i>>j)&1)==1:
            score+=l[j][1]+(j+1)*l[j][0]*100    # 素点
            # print('complete:',l[j][1]+(j+1)*l[j][0]*100)
            problem+=l[j][0]
            # print('s:',score,'P:',problem)
        else:
            highest=max(highest,j)
    if score<G and i!=(1<<D)-1:
        for k in range(l[highest][0]+1):
            score+=(highest+1)*100
            problem+=1
            # print('s:',score,'P:',problem)
            if score>=G:
                # print('ANS1')
                # print('s:',score,'P:',problem)
                ans=min(ans,problem)
    elif score>=G:
        ans=min(ans,problem)
        # print('G:',G)
        # print('ANS2')
        # print('s:',score,'P:',problem)

print(ans)

Submission status: Accepted

Solution code:
D, G = map(int, input().split())
P = []
C = []
score = 0
number = 1000

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

for i in range(2**D):
  ts = 0
  mp = 0
  memo = [i+1 for i in range(D)]
  
  for j in range(D):
    if ((i >> j) & 1):
      ts += P[j] * 100 * (j+1) + C[j]
      mp += P[j]
      memo[j] = 0
  m = max(memo)
  p = P[m-1]
  
  if ts >= G:
    number = min(number, mp)
  elif m >= 1 and ts + (p-1) * 100 * m >= G:
    for i in range(p):
      if ts + i * 100 * m >= G:
        number = min(number, mp+i)
  else:
    continue

print(number)

Submission status: Accepted

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

P = []
C = []

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

ans = float("inf")

for bit in range(1 << D) :
    A = []
    score = 0
    cost = 0
    
    for k in range(D) :
        if bit & (1 << k) :
            A.append(k)
    
    
    for a in A :
        score += 100*(a+1)*P[a] + C[a]
        cost += P[a]
    
    if score < G :
        for i in range(D-1,-1,-1) :
            if i in A :
                continue
            
            if score + 100*(i+1)*P[i] + C[i] < G :
                score += 100*(i+1)*P[i] + C[i]
                cost += P[i]
            
            else :
                cost += (G-score)//(100*(i+1)) + ((G-score) % ((100)*(i+1)) != 0)
                break
    
    ans = min(ans, cost)
    
print(ans)

Submission status: Accepted

Solution code:
import itertools

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

## i種類の問題を解いた時、(i-1)種類は完答してボーナス点をもらっている
## 完答する or それ以外 で分離することができて、状態数2**Dの全探索
## 完答するもので目標点を達成できていればOK.
## 完答するものだけで達成できていなければ、残っているうちで一番高い問題を解く

complete = [100*(i+1)*PC[i][0]+PC[i][1] for i in range(D)]

cost = 1000000000 ## Inf
for state in itertools.product(range(2), repeat=D): ## K**N 通りの全探索
  score = 0
  pre_cost = 0
  not_complete = []
  for i in range(D):
    if state[i] == 0:
      not_complete.append(i)
    else:
      score += 100*(i+1)*PC[i][0] + PC[i][1]
      pre_cost += PC[i][0]
  if score < G:
    idx = max(not_complete)
    if (G - score) > 100*(idx+1)*(PC[idx][0]-1):
      continue
    else:
      n_not_complete = ((G - score) + 100*(idx+1)-1) // (100*(idx+1))
      pre_cost += n_not_complete
  cost = min(cost, pre_cost)
  
print(cost)

Submission status: Accepted

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

def solve(g,i):
  if i==-1:
    return 100000
  n=min(g//(100*(i+1)),pc[i][0])
  s=n*(i+1)*100
  if n==pc[i][0]:
    s+=pc[i][1]
  if g-s>0:
    n+=solve(g-s,i-1)
  return min(n,solve(g,i-1))

print(solve(g,d-1))

Submission status: Accepted

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


def main():
    d, g = map(int, input().split())
    ps = [0 for _ in range(d)]
    cs = [0 for _ in range(d)]
    score_with_bonus = dict()
    ans = float('inf')

    for i in range(d):
        pi, ci = map(int, input().split())
        ps[i] = pi
        cs[i] = ci
        score_with_bonus[i] = (i + 1) * pi * 100 + ci

    # See:
    # https://img.atcoder.jp/abc104/editorial.pdf
    for bit in range(1 << d):
        total_score = 0
        problem_count = 0
        pmax = 0

        for j in range(d):
            if bit & (1 << j):
                total_score += score_with_bonus[j]
                problem_count += ps[j]
            else:
                pmax = max(pmax, j)

        for k in range(1, ps[pmax]):
            if total_score < g:
                total_score += (pmax + 1) * 100
                problem_count += 1

        if problem_count > 0 and total_score >= g:
            ans = min(ans, problem_count)

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

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

pt = 100
st = []
for i, (p, c) in enumerate((map(int, input().split()) for _ in range(D))):
    st.append([pt * p + c, p, 2**i, (p-1, pt)])
    pt += 100

mincnt = 10 ** 10
for i in range(pow(2,D)):

    score = G
    cnt = 0
    maxpt = (0, 1)
    for allscore, allcnt, pos, eachpt in st:
        if pos & i:
            score -= allscore
            cnt += allcnt
        else:
            maxpt = eachpt
    else:
        if score > 0:
            p, pt = maxpt
            wcnt = score // pt + bool(score % pt) * 1
            if wcnt <= p:
                cnt += wcnt
            else:
                continue
        
        mincnt = min(mincnt, cnt)

print(mincnt)

Submission status: Accepted

Solution code:

from itertools import product
import math
D,G = map(int,input().split())

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

#pc.sort(key=lambda x:x[1])

ans = 1001
# 各セットをコンプするか否かでまずループ
for comp in product(range(2), repeat=D):
    
#    print(comp)

    #コンプしたものだけでOKな場合はその数を既存の回答数と比較して小さい方を保存
    num_ans = 0
    score = 0
    max_index = -1 #コンプしないセットで1問あたりの特典が最大のセット番号
    for i in range(D):
        if comp[i]:
            num_ans +=pc[i][0]
            score += 100*(i+1)*pc[i][0]+pc[i][1]
        else:
            max_index = i
            
    
    if score >= G:
        ans = min(ans, num_ans)
    else:
        #コンプしたものだけではNGな場合
        #コンプしていない各セットについて全探索して最小値を保存
        #このときコンプしていないセットのなかで個別の特典が一番高いものだけ見ればOK
        if score + 100*(max_index+1)*(pc[max_index][0]-1) >= G:
           num_ans += math.ceil((G-score)/(100*(max_index+1)))
           ans = min(ans, num_ans)
#    if ans == 60:
#        print(comp)

print(ans)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline

def inpl(): return list(map(int, input().split()))
D, G = inpl()
P = [0]*D
C = [0]*D
for i in range(D):
    P[i], C[i] = inpl()

ans = sum(P)
for k in range(2**D):
    score = 0
    cnt = 0
    for i in range(D):
        if (k >> i) & 1:
            cnt += P[i]
            score += 100*(i+1)*P[i] + C[i]
    
    for i in range(D-1, -1, -1):
        if (k >> i) & 1 == 0:
            tmp = -(-(G - score)//(100*(i+1)))
            x = max(0, min(P[i]-1, tmp))
            cnt += x
            score += 100*(i+1)*x
    if score >= G:
        ans = min(ans, cnt)
            
print(ans)

Submission status: Accepted

Solution code:
def solve(g,i):
    if i==0:
        return 10**9
    n=min(g//(100*i),PC[i][0])
    s=n*i*100
    if n==PC[i][0]:
        s+=PC[i][1]
    if s<g:
        n+=solve(g-s,i-1)
    return min(n,solve(g,i-1))

d,g=map(int,input().split())
PC=[0]+list(list(map(int,input().split())) for i in range(d))

print(solve(g,d))

Submission status: Accepted

Solution code:
difficulties, goal = map(int, input().split())

pcs = [list(map(int, input().split())) for _ in range(difficulties)]

total_problem = 0
new_dp = [0] * 1001

for d, pc in enumerate(pcs, 1):
    dp = new_dp[:]

    problem, complete = pc
    total_problem += problem

    score = {x: x*100*d for x in range(problem)}
    score[problem] = problem * 100 * d +complete

    for i in range(1, total_problem + 1):
        for j in range(0, i + 1):
            if i - j > problem:
                continue
            else:
                new_dp[i] = max(new_dp[i], dp[j] + score[i-j])

for i, a in enumerate(new_dp):
    if a >= goal:
        print(i)
        exit()

Submission status: Accepted

Solution code:
difficulties, goal = map(int, input().split())

pcs = [list(map(int, input().split())) for _ in range(difficulties)]

dp = [[0] * 1102 for _ in range(difficulties + 1)]

total_problem = 0
for d, pc in enumerate(pcs, 1):
    problem, complete = pc
    total_problem += problem

    score = {x: x*100*d for x in range(problem)}
    score[problem] = problem * 100 * d +complete

    for i in range(1, total_problem + 1):
        for j in range(0, i + 1):
            if i - j > problem:
                dp[d][i] = max(dp[d][i], dp[d - 1][j])
            else:
                dp[d][i] = max(dp[d][i], dp[d-1][j] + score[i-j])

for i, a in enumerate(dp[difficulties]):
    if a >= goal:
        print(i)
        exit()

Submission status: Accepted

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

ans = float("inf")
# iを状態にする
for i in range(2**d):
    hoge = 0
    score = 0
    cnt = 0
    for j in range(d):
        if i & 1<<j:
            score += (j+1)*100*pq[j][0] + pq[j][1]
            cnt += pq[j][0]
        else:
            hoge = j
    tmp = max(0, -(-(g - score)//((hoge+1)*100)))
    #print(bin(i), cnt,score, tmp)
    if tmp <= pq[hoge][0]:
        ans = min(ans, cnt+tmp)
print(ans)

Submission status: Accepted

Solution code:
import math
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())

# 完全に解く 1
# 全く解かない 0
min_cost = 10**10
for i in range(2**d):
    count = 0
    score = 0
    use_list = []
    for bit in range(d):
        if i & 2 ** bit > 0:
            use_list.append(bit + 1)
            count += p[bit]
            score += (bit + 1) * 100 * p[bit] + c[bit]
    if score < g:
        p_i = max(set(range(1, d+1)) - set(use_list))
        p_count = math.ceil((g - score) / (p_i * 100))
        if p_count <= p[p_i - 1]:
            count += p_count
            score += p_count * (p_i * 100)
    if score >= g:
        min_cost = min(min_cost, count)
print(min_cost)

Submission status: Accepted

Solution code:
from itertools import permutations

D,G = [int(i) for i in input().split()]
L = [[int(i) for i in input().split()] for _ in range(D)]

ans = []
for i in range(2**D):
    tmp = 0
    index = 0
    index_li = []
    ans_tmp = 0
    for j in range(D):
        if (i >> j) & 1:
            tmp += L[j][0]*100*(j+1)+L[j][1]
            ans_tmp += L[j][0]
        else:
            index_li.append(j+1)
    if G >= tmp:
        for index in index_li[::-1]:
            p = 0
            while G > tmp:
                if p > L[index-1][0]:
                    break
                p += 1
                ans_tmp += 1
                tmp += index*100

    ans.append(ans_tmp)

print(min(ans))

Submission status: Accepted

Solution code:
import sys, os

f = lambda:list(map(int,input().split()))
if 'local' in os.environ :
    sys.stdin = open('./input.txt', 'r')

def solve():
    d, g = f()
    ps = [ f() for i in range(d)]

    ans = 1e9
    for all_solve in range(1<<d):
        score = 0
        max_unused = 0
        cnt_p = 0
        for j in range(d):
            if all_solve&(1<<j):
                score += ps[j][0] * 100 *(j+1) + ps[j][1]
                cnt_p += ps[j][0]
            else:
                max_unused = j
        if score>g:
            ans = min(ans, cnt_p)
            continue
        
        max_unused_score = 100*(max_unused+1)
        if (g - score+ max_unused_score -1 )//max_unused_score > ps[max_unused][0]:
            continue
        else:
            cnt_p += (g - score+ max_unused_score -1 )//max_unused_score
        
        ans = min(ans,cnt_p)
    
    print(ans)


solve()

Submission status: Accepted

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

min_count = float("inf")
for ptn in range(2**D):
    completed = []
    for i in range(D):
        if (ptn >> i) & 1 == 1:
            completed.append(i)

    score = 0
    count = 0
    for i in completed:
        score += 100*(i+1)*ps[i] + cs[i]
        count += ps[i]
    if score < G:
        selected_prob = max([i for i in range(D)
                             if i not in completed])
        if (selected_prob+1)*100*(ps[selected_prob]-1) < G - score:
            continue
        if (G-score) % ((selected_prob+1)*100) == 0:
            count += (G-score)//((selected_prob+1)*100)
        else:
            count += (G-score)//((selected_prob+1)*100)+1

    if count < min_count:
        min_count = count
print(min_count)

Submission status: Accepted

Solution code:
#!/usr/bin/env python
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])
    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())
pc = []
for i in range(D):
    pc.append(list(map(int,input().split())))

ans = 10**10
for i in range(1 << D):
    c = 0
    p = 0
    l = []
    for j in range(D):
        if ((i >> j) & 1) == 1:
            c += pc[j][0]
            p += (j+1)*100*pc[j][0] + pc[j][1]
            l.append(j)
    ma = 0
    for ii in range(D-1,-1,-1):
        if ii not in l:
            ma = ii
            break
    for k in range(pc[ma][0]):
        if p >= G:
            break
        c += 1
        p += (ma+1)*100

    if p >= G:
        ans = min(ans , c)
print(ans)

Submission status: Accepted

Solution code:
import sys


if __name__ == '__main__':
    D, G = map(int, input().split())
    p = ['-1'] * D
    c = ['-1'] * D
    for i in range(D):
        p[i], c[i] = map(int, input().split())

    answer = sys.maxsize
    for i in range(pow(2, D)):
        bonus_flags = format(i, "b").zfill(D)

        score = 0
        count = 0
        remain = []
        for index, bonus_flag in enumerate(bonus_flags):
            if bonus_flag == '1':
                score += (index + 1) * 100 * p[index] + c[index]
                count += p[index]
            else:
                remain.append(index)
        if score < G:
            R = G - score
            j = remain[-1]

            if (p[j] - 1) * (j+1) * 100 < R:
                continue
            count += -(-R//(100*(j+1)))
        answer = min(answer, count)

    print(answer)

Submission status: Accepted

Solution code:
def Search(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+=Search(g-s,t-1)
    return min(n,Search(g,t-1))
d,g=map(int,input().split())
p=[]
c=[]
sum=[]
for i in range(d):
    a,b=map(int,input().split())
    p.append(a)
    c.append(b)
for i in range(d):
    sum.append((i+1)*100*p[i]+c[i])
print(Search(g,d))

Submission status: Accepted

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

ans = float("inf")
for i in range(2 ** D):
    bit = bin(i)[2:].zfill(D)
    sum_num = 0
    cnt = 0
    used = set()
    for j in range(D):
        b = bit[j]
        if b == "1":
            used.add(j)
            cnt += items[j][0]
            sum_num += 100 * (j + 1) * items[j][0] + items[j][1]
    if sum_num >= G:
        ans = min(ans, cnt)
    else:
        for p, c, j in reversed(items):
            if j in used:
                continue
            for a in range(p - 1):
                sum_num += 100 * (j + 1)
                cnt += 1
                if sum_num >= G:
                    break
            if sum_num >= G:
                ans = min(ans, cnt)
                break
print(ans)

Submission status: Accepted

Solution code:
import math


def main():

    num, goal = map(int, input().split())
    data = [list(map(int, input().split())) for i in range(num)]

    ans = 10 ** 10

    for i in range(2 ** num):
        toku_flg = list(map(int, list(bin(i)[2:])))
        toku_flg = [0 for i in range(num - len(toku_flg))] + toku_flg

        now_score = 0
        now_mondai = 0
        for i in range(num):
            if toku_flg[i] == 1:
                now_score += (i + 1) * 100 * data[i][0] + data[i][1]
                now_mondai += data[i][0]

        if now_score < goal:
            for i in range(num)[::-1]:
                if toku_flg[i] == 0:
                    if now_score + (i + 1) * 100 * (data[i][0] - 1) < goal:
                        break
                    nokori = goal - now_score
                    add_num = math.ceil(nokori / ((i + 1) * 100))
                    now_score += (i + 1) * 100 * add_num
                    now_mondai += add_num
                    break

        if now_score >= goal:
            if now_mondai < ans:
                ans = now_mondai

    print(ans)





if __name__ == '__main__':
    main()

Submission status: Accepted

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

def func(i, t):
    if i == 0:
        return 10 ** 9
    
    # Solve all problems, or part of them
    k = min(t // (100 * i), X[i][0])
    s = 100 * i * k
    
    # If all problems are solved, add bonus
    if k == X[i][0]:
        s += X[i][1]
        
    # If score < objective, go next step
    if s < t:
        k += func(i - 1, t - s)
        
    # Select minimum number of solved problems
    # k: solve i-th line
    # func(i-1,t): pass i-th line
    return min(k, func(i - 1, t))

# Solve backward
print(func(D, G))

Submission status: Accepted

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

def func(i, t):
    if i == 0 or i > D:
        return 10 ** 9
    
    # Solve all problems, or part of them
    k = min(t // (100 * i), X[i][0])
    s = 100 * i * k
    
    # If all problems are solved, add bonus
    if k == X[i][0]:
        s += X[i][1]
        
    # If score < objective, go next step
    if s < t:
        k += func(i - 1, t - s)
        
    # Select minimum number of solved problems
    # k: solve i-th line
    # func(i-1,t): pass i-th line
    return min(k, func(i - 1, t))

# Solve backward
print(func(D, G))

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
import itertools
import math


def solve(D: int, G: int, p: "List[int]", c: "List[int]"):

    cpl = [ (i+1)*100*pp+cc for i,(pp,cc) in enumerate(zip(p,c)) ]

    min_n = float("inf")
    for tfl in itertools.product([True,False],repeat=D):
        cmp_total_n = sum(itertools.compress(p,tfl))
        cmp_total_p = sum(itertools.compress(cpl,tfl))
        if cmp_total_p < G:
            ntfl = [ not i for i in tfl ]
            max_i = max(itertools.compress([i for i in range(0,D)],ntfl))
            max_ip = 100*(max_i+1)

            additinal_n = int(math.ceil((G-cmp_total_p)/max_ip))
            if additinal_n < p[max_i]:
                min_n = min(min_n,cmp_total_n+additinal_n)
        else:
            min_n = min(min_n, cmp_total_n)

    print(min_n)



# Generated by 1.1.4 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    D = int(next(tokens))  # type: int
    G = int(next(tokens))  # type: int
    p = [int()] * (D)  # type: "List[int]" 
    c = [int()] * (D)  # type: "List[int]" 
    for i in range(D):
        p[i] = int(next(tokens))
        c[i] = int(next(tokens))
    solve(D, G, p, c)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from heapq import heappop, heappush, heapify, heappushpop
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits

def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

D, G = MAP()
pc = [LIST() for _ in range(D)]
count_min = 1000000000
for i in range(1<<D):
	sum_ = 0
	count = 0
	i = list("{:b}".format(i).zfill(D))
	# print(i)
	for j in range(D):
		if i[j] == '1':  # j = '1' なら全部加える
			sum_ += (j+1)*100*pc[j][0] + pc[j][1]
			count += pc[j][0]
	if sum_ >=  G:
		if count < count_min:
			# print("更新", count_min,"->",count)
			count_min = count
	else:  # 中途半端にとる
		for j in range(D-1, -1, -1):
			if i[j] == '0':  # G - sum_ : 残りのポイント
				num = ceil((G-sum_)/((j+1)*100))
				# print(num)
				if num > pc[j][0]:
					count = 1000000000
					break
				count += ceil((G-sum_)/((j+1)*100))
				break
		if count < count_min:
			# print("更新", count_min,"->",count)
			count_min = count

print(count_min)

Submission status: Accepted

Solution code:
def abc104():

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


	def saisho(a,b):
		if a==0:
			return 10**10
		m=min(b//(a*100),p[a-1])
		s=100*a*m
		if m==p[a-1]:
			s+=c[a-1]
		if s<b:
			m+=saisho(a-1,b-s)
		return min(m,saisho(a-1,b))
	
	print(saisho(D,G))
	
abc104()

Submission status: Accepted

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

ans = 10**8
for i in range(2**D):
    score = 0
    tmp = 0
    n_list = []
    for j in range(D):
        if (i >> j & 1):
            k = l[j]
            score += (j+1)*100*k[0]+k[1]
            tmp += k[0]
        else:
            n_list.append([j+1]+l[j])
    e_flag = False
    for ii in n_list[::-1]:#[1or2or..,times,bonus]
        for jj in range(ii[1]-1):
            if score<G:
                score += ii[0]*100
                tmp += 1
            else:
                e_flag = True
                break
        if e_flag:
            break
    if score<G:
        continue
    ans = min(ans,tmp)
print(ans)

Submission status: Accepted

Solution code:
from math import ceil

D, G = [int(t) for t in input().split()]
p = []
c = []
for i in range(D):
    p_, c_ = [int(t) for t in input().split()]
    p.append(p_)
    c.append(c_)


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


print(minsolve(G, D))

Submission status: Accepted

Solution code:
import math

D, G = map(int, input().split())
p = [0] * D
c = [0] * D
ans = float('inf')
for i in range(D):
  p[i], c[i] = map(int, input().split())
for i in range(2 ** D):
  s = 0
  n = 0
  ma = -1
  for j in range(D):
    if ((i >> j) & 1) == 1:
      s += 100 * (j + 1) * p[j] + c[j]
      n += p[j]
    else:
      ma = j
  if s < G:
    m = math.ceil((G - s) / (100 * (ma + 1)))
    if m > p[ma]:
      continue
    else:
      n += m
  ans = min(ans, n)
print(ans)

Submission status: Accepted

Solution code:
D,G = map(int,input().split())
p = [0]*D
c = [0]*D
ans = 10 ** 9
for i in range(D):
    p[i],c[i] = map(int,input().split())
for i in range(2 ** D):
    point = 0
    count = 0
    for j in range(D):
        if (i>>j)&1 == 1:
            point += 100*(j+1)*p[j]+c[j]
            count += p[j]
    if point < G:
        for j in range(D)[::-1]:
            if ((i>>j)&1) == 0:
                for k in range(p[j]):
                    point += (j+1)*100
                    count += 1
                    if point >= G:
                        break
                break
    if point >= G:
        ans = min(ans,count)
print(ans)

Submission status: Accepted

Solution code:
import math

def dfs(sc, i=0, qn=0, used=set()):
    if sc <= 0:
        return qn
    if i == d:
        i -= 1
        while i in used:
            i -= 1
        hanpa = math.ceil(sc / (100 * (i + 1)))
        if hanpa >= pc[i][0]:
            return inf
        return qn + hanpa
    p, c = pc[i]
    zenbu = (i + 1) * 100 * p + c
    used.add(i)
    re1 = dfs(sc - zenbu, i + 1, qn + p, used)
    used.remove(i)
    re2 = dfs(sc, i + 1, qn, used)
    return min(re1, re2)

inf = 10 ** 9
d, g = map(int, input().split())
pc = [list(map(int, input().split())) for _ in range(d)]
print(dfs(g))

Submission status: Accepted

Solution code:
d,g=map(int,input().split())
g=g//100
p_list=[]
c_list=[]
s_list=[]
for i in range(d):
    p,c=map(int,input().split())
    c=c//100
    p_list.append(p)
    c_list.append(c)
    s_list.append(p*(i+1)+c)
Min=1000
for i in range(2**d):
    Sum=0
    Num=0
    for j in range(d):
        if (i>>j)&1==1:
            Sum=Sum+s_list[j]
            Num=Num+p_list[j]
        else:
            M=j
    if Sum>=g:
        if Num<Min:
            Min=Num
    else:
        r=((g-Sum)+M)//(M+1)
        if r<=p_list[M]:
            Num=Num+r
            if Num<Min:
                Min=Num
print(Min)

Submission status: Accepted

Solution code:
import math
d, g = map(int, input().split())
p = []
c = []
for _ in range(d):
    tp, tc = map(int, input().split())
    p.append(tp)
    c.append(tc)

ans = 1000
for i in range(2**d):
    score = 0
    num = 0
    r = -1
    for j in range(d):
        if i>>j & 1:
            score += 100 * (j+1) * p[j] + c[j]
            num += p[j]
        else:
            r = j
    if score < g:
        tmp = math.ceil((g-score) / (100*(r+1)))
        if tmp >= p[r]:
            continue
        num += tmp
    ans = min(ans, num)
print(ans)