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:
from itertools import product
import numpy as np

d, g = map(int, input().split())
p = np.empty(d, dtype=np.int64)
c = np.empty(d, dtype=np.int64)
for i in range(d):
    p[i], c[i] = map(int, input().split())

scores = np.array([p[i] * 100 * (i + 1) + c[i] for i in range(d)], dtype=np.int64)

ans = 10 ** 9
for permutation in product([0, 1], repeat=d):
    permutation = np.array(permutation, dtype=np.int64)
    score = np.inner(scores, permutation)
    problems = np.inner(p, permutation)
    if score >= g:
        ans = min(ans, problems)
    else:
        to_solve = np.max(np.where(permutation == 0))
        extra = -(-(g - score) // (100 * (to_solve + 1)))
        if extra < p[to_solve]:
            ans = min(ans, problems + extra)
print(ans)

Submission status: Accepted

Solution code:
D,G=map(int,input().split())
li=[list(map(int,input().split())) for _ in range(D)][::-1]
ans=float("inf")
for i in range(2**D):
  S=0
  cnt=0
  q="{:0>10b}".format(i)[::-1]
  ads=q.find("0")
  for j in range(D):
    if int(q[j])&1:
      S+=(D-j)*100*li[j][0]+li[j][1]
      cnt+=li[j][0]
  if S<G and (D-ads)*100*(li[ads][0]-1)>=G-S:
    for k in range(li[ads][0]):
      S+=(D-ads)*100
      cnt+=1
      if S>=G:
        break
  if S>=G:
    ans=min(ans,cnt)
print(ans)

Submission status: Accepted

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

ans = 10 ** 18
import itertools
for i in itertools.product([0, 1], repeat=d):
    point = 0
    num = 0
    # ボーナス加算
    for j in range(d):
        if i[j] == 1:
            num += pc[j][0]
            point += pc[j][1] + 100 * (j+1) * pc[j][0]
    #print('-b-', i, g, point, num)
    # 足りない分を後ろから全問-1問まで加算
    for j in reversed(range(d)):
        if g <= point:
            break
        if i[j] == 0:
            c = (g - point) // (100 * (j+1))
            if c < pc[j][0]:
                num += c
                point += 100 * (j+1) * c
            else:
                num += pc[j][0] - 1
                point += 100 * (j+1) * (pc[j][0] - 1)
        #print(i,j, g, point, num)
    #print('---', ans, num, point)
    if g <= point:
        ans = min(ans, num)
print(ans)

Submission status: Accepted

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

ans = 10 ** 18
import itertools
for i in itertools.product([0, 1], repeat=d):
    point = 0
    num = 0
    for j in range(d):
        if i[j] == 1:
            num += pc[j][0]
            point += pc[j][1] + 100 * (j+1) * pc[j][0]
    #print('-b-', i, g, point, num)
    for j in reversed(range(d)):
        if g <= point:
            continue
        if i[j] == 0:
            c = (g - point) // (100 * (j+1))
            if c < pc[j][0]:
                num += c
                point += 100 * (j+1) * c
            else:
                num += pc[j][0] - 1
                point += 100 * (j+1) * (pc[j][0] - 1)
        #print(i,j, g, point, num)
    #print('---', ans, num, point)
    if g <= point:
        ans = min(ans, num)
print(ans)

Submission status: Accepted

Solution code:
"""
i=7
bin_i=format(i,'b')
bin_i='0'+bin_i
print(bin_i)
"""
d,g=map(int,input().split())
#d=int(input())
#g=int(input())
p=[0]*d
c=[0]*d
res=pow(10,7)
"""
初期化パターン
p=[0]*d
"""
for i in range(d):
    p[i],c[i]=map(int,input().split())
    #p.append(int(input()))
    #c.insert(i,int(input()))

for bit in range(1<<d):
    #print(bit)
    score=0
    num=0
    for i in range(d):
        if(bit & (1<<i)):
            score+=c[i]+p[i]*100*(i+1)
            num+=p[i]
    if(score>=g):
        res=min(res,num)
    else:
        for i in range(d-1,-1,-1):               
            if(bit & (1<<i)):
                continue
            for j in range(0,p[i]):
                if(score>=g):
                    break                    
                score+= 100*(i+1)
                num+=1
        res=min(res,num)
print(res)

Submission status: Accepted

Solution code:
D,G=map(int,input().split())
p=[]
c=[]
for i in range(D):
  p1,c1=map(int,input().split())
  p.append(p1)
  c.append(c1)
ans=sum(p)
for i in range(2**D):
  num=0
  point=0
  flag=[0]*D
  for j in range(D):
    if(i>>j&1):
      num+=p[j]
      flag[j]=1
      point+=(j+1)*100*p[j]+c[j]
  if(point<G):
    sitt=flag[::-1]
    loc=D-1-sitt.index(0)
    k=0
    while(point<G):
      num+=1
      k+=1
      point+=(loc+1)*100
    if(k<p[loc]):
      ans=min(ans,num)
  else:
    ans=min(ans,num)
  #print(loc)
print(ans)

Submission status: Accepted

Solution code:
d,g = map(int,input().split())
P = [0]*d
C = [0]*d
for i in range(d):
    P[i],C[i] = map(int,input().split())

ans = float('inf')
for i in range(2**d):
    tmp = 0
    res = 0
    for j in range(d):
        if ((i>>j)&1):
            tmp+=C[j]+(j+1)*100*P[j]
            res+=P[j]
    if tmp<g:
        for j in range(d-1,-1,-1):
            if not ((i>>j)&1):
                if tmp>=g:
                    break
                if tmp+(j+1)*100*P[j]<=g:
                    tmp+=(j+1)*100*P[j]
                    res+=P[j]
                else:
                    for p in range(P[j]):
                        if tmp>=g:
                            break
                        tmp+=(j+1)*100
                        res+=1
    ans = min(ans,res)
print(ans)

Submission status: Accepted

Solution code:
D,G = map(int,input().split())
questions = [list(map(int,input().split())) for _ in range(D)]
ans = float('inf')
for bit in range(1 << D):
  count = 0
  score = 0
  max_zero_index = 0
  for i in range(D):
    if (bit >> i) & 1:
      score += questions[i][0]*100*(i+1)+questions[i][1]
      count += questions[i][0]
    else:
      max_zero_index = i
  if score >= G:
    ans = min(count,ans)
  else:
    for _ in range(1,questions[max_zero_index][0]):
      count +=1
      score += 100*(max_zero_index+1)
      if score >= G:
        ans = min(count,ans)
print(ans)

Submission status: Accepted

Solution code:
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 bit in range(1 << D):
    score = 0
    cnt = 0
    unused = set(range(1, D+1))
    for i in range(D):
        if (bit >> i) & 1 == 1:
            cnt += P[i]
            score += 100 * (i + 1) * P[i] + C[i]
            unused.discard(i + 1)

    if score < G:
        use = max(unused)
        num = min(P[use - 1], -(-(G - score) // (use * 100)))
        cnt += num
        score += use * 100 * num

    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 i in range(d)]
ans=10**18
for i in range(2**d):
  t_point,t_solved=0,0
  for j in range(d):
    if i&(1<<j):
      t_solved+=pc[j][0]
      t_point+=pc[j][0]*(j+1)*100+pc[j][1]
  if t_point>=g:
    ans=min(ans,t_solved)
    continue
  
  j=d-1
  while j>=0:
    if i&(1<<j):
      j-=1
      continue
    p,c=pc[j]
    point=(j+1)*100
    if t_point+(p-1)*point<g:
      t_point+=(p-1)*point
      t_solved+=p-1
    else:
      husoku=g-t_point
      count=-(-husoku//point)
      t_point+=count*point
      t_solved+=count
    if t_point>=g:
      break
    j-=1
  else:
    continue
  if t_point>=g:
    ans=min(ans,t_solved)
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):
    score=0
    cnt=0
    com=-1
    for j in range(d):
        if ((i >> j) & 1):
            score+=100*(j+1)*p[j]+c[j]
            cnt+=p[j]
        else:
            com=j
 
    flg=0
    if score<g and com>=0:
        while p[com]>flg:
            score+=100*(com+1)
            flg+=1
            if score>=g:
                break
    if score>=g:
        cnt+=flg
        if ans>cnt:
            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)]

ans=float('inf')
for bit in range(2**d):
    b = 0
    score = 0
    num = 0
    # ボーナスを貰えるまで問題を解く場合を計算
    # bit探索し、ボーナスを貰うパターンを網羅する
    for i in range(d):
        if (bit >> i) & 1:
            # 問題を解いた点 + ボーナス
            score += pc[i][0] * (i+1) * 100 + pc[i][1]
            # 解いた問題数
            num += pc[i][0]
        else:
            # ボーナスを貰えるまで解かない問題の場合
            # この値には最終的にはボーナスを貰えるまでは解かない、最大点がもらえる問題の番号が入る
            b = i

    # ボーナスを貰えるまでは解かない問題による加点と回答の更新を行う
    for j in range(pc[b][0]):
        if score>=g and num<ans:
            ans=num
        score+=(b+1)*100
        num+=1

print(ans)

Submission status: Accepted

Solution code:
import sys
from itertools import product

sys.setrecursionlimit(10 ** 7)
f_inf = float('inf')
mod = 10 ** 9 + 7


def resolve():
    d, g = map(int, input().split())
    PC = []
    for i in range(d):
        p, c = map(int, input().split())
        PC.append([(i + 1) * 100, p, c])

    res = f_inf
    for pattern in product([0, 1], repeat=d):
        score = 0
        cnt = 0
        remain = []
        for idx, p in enumerate(pattern):
            if p == 1:
                point, num, bonus = PC[idx]
                score += point * num + bonus
                cnt += num
            else:
                remain.append(PC[idx])

        if score >= g:
            res = min(res, cnt)
        else:
            remain = sorted(remain, key=lambda x: x[0], reverse=True)
            diff = g - score
            for point, num, bonus in remain:
                if diff <= point * (num - 1):
                    cnt += diff // point + (1 if diff % point else 0)
                    res = min(res, cnt)
                    break
                else:
                    cnt += num - 1
                    score += point * (num - 1)

    print(res)


if __name__ == '__main__':
    resolve()

Submission status: Accepted

Solution code:
from itertools import groupby, accumulate, product, permutations, combinations
def solve():
    ans = float('inf')
    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())
    for p in product([0,1],repeat=D):
        cnt = 0
        num = 0
        for i in range(D):
            if p[i]==1:
                cnt += 100*(i+1)*P[i]+C[i]
                num += P[i]
        if cnt<G:
            for i in range(D-1,-1,-1):
                if p[i]==0:
                    if (G-cnt+100*i)//(100*(i+1))<P[i]:
                        num += (G-cnt+100*i)//(100*(i+1))
                        break
            else:
                continue
        ans = min(ans,num)
    return ans
print(solve())

Submission status: Accepted

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

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

ans = 10 ** 9
for i in range(2 ** D): #全問解く問題
    score = 0
    problem = 0
    for j in range(D):
        if (i >> j) & 1:
            score += 100 * (j + 1) * PC[j][0] + PC[j][1]
            problem += PC[j][0]
    if score > G:
        continue
    left = G - score #残り必要な点数
    for j in range(D):
        if (i >> j) & 1:
            continue
        if left > 100 * (j + 1) * PC[j][0] + PC[j][1]: #そこをすべて解いても足りないとき
            pass
        else:
            tmp = (left + (100 * (j + 1)) - 1) // (100 * (j + 1))
            ans = min(ans, problem + min(tmp, PC[j][0]))

print (ans)

Submission status: Accepted

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

res = float("inf")        
for i in range(2**D):
  bs = format(i,"0{}b".format(D))
  ans = 0
  cnt = 0
  #コンプするやつをたす
  for j in range(D):
    if bs[j] == "1":
      ans += (j+1)*100*p[j] + c[j]
      cnt += p[j]
  if ans >= G:
    res = min(cnt,res)
    continue

  #コンプしないやつを寸止めでたす
  for j in range(D-1,-1,-1):
    if bs[j] == "0":
      ans += (j+1)*100*(p[j]-1)
      cnt += (p[j]-1)
      if ans >= G:
        cnt -= (ans-G)//((j+1)*100)
        res = min(res,cnt)
        break
print(res)

Submission status: Accepted

Solution code:
D,G = map(int, input().split())
INF = 10**10
# 各点数を得るときの、最小の問題数
n = 2*10**5
dp = [INF] * n
dp[0] = 0
for i in range(1,D+1):
    p,c = map(int, input().split())
    c //= 100
    tmp = dp[:]
    for j in range(G//100+1):
        if tmp[j] == INF: continue
        for k in range(1,p+1):
            dp[j+i*k] = min(tmp[j]+k, dp[j+i*k])
        dp[j+i*p+c] = min(tmp[j]+p, dp[j+i*p+c])
ans = INF
for score in dp[G//100:]:
    if score == INF: continue
    ans = min(score, ans)
print(ans)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10 ** 5 + 10)


def input(): return sys.stdin.readline().strip()


def resolve():

    D, G = map(int, input().split())
    P, C = [0] * D, [0] * D
    for i in range(D):
        P[i], C[i] = map(int, input().split())
    ans = 10**10

    # 昇順での探索だよ
    for i in range(2 ** D):
        checked = [False]*D
        pnt = 0
        cnt = 0

        for j in range(D):  # このループが一番のポイント
            if ((i >> j) & 1):  # 順に右にシフトさせ最下位bitのチェックを行う
                pnt += C[j]
                pnt += P[j]*(j+1)*100
                checked[j] = True
                cnt += P[j]
        if pnt < G:
            for k in reversed(range(D)):
                if not checked[k]:
                    prob_cnt = 0
                    br_fl = False

                    while prob_cnt < P[k]-1:
                        pnt += (k+1)*100
                        cnt += 1
                        prob_cnt += 1
                        if pnt >= G:
                            br_fl = True
                            break
                    if br_fl:
                        break
        if pnt >= G:
            ans = min(ans, cnt)

    print(ans)


resolve()

Submission status: Accepted

Solution code:
D, G = [int(s) for s in input().split()]
problems = [[int(s) for s in input().split()] for _ in range(D)]

result = 10 ** 8

for i in range(2 ** D):
    cnt_problem = 0
    cnt_score = 0
    for j in range(D):
        if i >> j & 1:
            cnt_score += problems[j][1] + 100 * (j + 1) * problems[j][0]
            cnt_problem += problems[j][0]

    for j in reversed(range(D)):
        if not i >> j & 1:
            for _ in range(problems[j][0]):
                if cnt_score >= G:
                    break
                else:
                    cnt_score += 100 * (j + 1)
                    cnt_problem += 1
    result = min(cnt_problem, result)

print(result)

Submission status: Accepted

Solution code:
import math
d, g = map(int, input().split())
p = [0 for _ in range(d+1)]
c = [0 for _ in range(d+1)]
ans = 10 ** 10
for i in range(d):
    pi, ci = map(int, input().split())
    p[i+1] = pi
    c[i+1] = ci     
for bit in range ( 1 << d):
    score = 0
    cnt = 0
    tokanai_saidai = 0
    for i in range(d):
        if bit & (1 << i):
            score += p[i+1] * 100 * (i+1) + c[i+1]
            cnt += p[i+1]
        else:
            tokanai_saidai = i + 1
    if score >= g:
        if cnt < ans:
            ans = cnt
    else:
        nokori_score = g - score
        if nokori_score < 100 * (tokanai_saidai) * p[tokanai_saidai]:
            cnt += math.ceil(nokori_score / (100 * tokanai_saidai))
            if cnt < ans:
                ans = cnt 
print(ans)

Submission status: Accepted

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

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

max_cnt = sum(P)

def solve(i, score, cnt, nm):
    if i == D:
        if score >= G:
            return cnt
        else:
            add_cnt = (G-score)/((nm+1)*100)
            if add_cnt > P[nm]:
                return max_cnt
            else:
                return cnt + int(math.ceil(add_cnt))
    return min([solve(i+1, score+P[i]*(i+1)*100 + C[i], cnt+P[i], nm), 
                solve(i+1, score, cnt, i)])

a = solve(0, 0, 0, 0)
print(a)

Submission status: Accepted

Solution code:
import itertools

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

#ボーナスをどの問題でもらうか
#bonus=[0]*D

a = [0,1]
Ls = list(itertools.product(a, repeat=D))

#最大数 更新していく
out=1000

for L in Ls:
    count=0
    score=0

    for i in range(D):
        if L[i]==1:
            count+=PC[i][0]
            score+=100*(i+1)*PC[i][0]
            score+=PC[i][1]

    hanpa = D-1
    while (L[hanpa]==1) and (hanpa>=0):
        hanpa-=1
    if hanpa==-1:
        cnt=0
    else:
        cnt=0
        while (score<G) and (cnt<PC[hanpa][0]):
            cnt+=1
            count+=1
            score+=(hanpa+1)*100
    if (score>=G) and (count<out):
        out=count
print(out)

Submission status: Accepted

Solution code:
import itertools
# 入力もらう
D,G = list(map(int,input().split()))
PC = []
for i in range(D):
    PC.append(list(map(int,input().split())))

#[0,0,0,0,0,0,0,0,0,0]という形で、どのボーナスをもらうかを管理したい
#例えば[1,0,0,0,1,0,0,0,0,0]は100点問題と500点問題のボーナスをもらうということ
#2^D通り(D<=10)だから全探索できる
#itertools使って2^D通りのケースを用意
a = [0,1]
Ls = list(itertools.product(a, repeat=D))

#pは100以下、Dは10以下だから解く問題数は多くて1000
#最大値を初期値として設定して、小さい値が実現できたら更新していく
out = 1000

#戦略としては、「ボーナスをもらう問題」を先に決めて計算し、
#その後「中途半端に解く問題」を合計得点がGに足るまで計算する、というもの。

for L in Ls: #どの問題でボーナスをもらうか、2^D通りのシナリオを逐一チェック
    #Lには「ボーナスをもらう問題」をどれにするか決めた結果が格納されている
    num = 0 #このシナリオにおける解いた問題の数
    point = 0 #このシナリオにおける得点

    #このシナリオにおいて「ボーナスをもらう問題」をまずは計算
    for i in range(D):
        if L[i]==1: #ボーナスをもらう問題では
            num+=PC[i][0] #解いた問題の数にプラス
            point+=PC[i][1] #特典もプラス
            point+=(i+1)*100*PC[i][0] #ボーナスもプラス

    #ここから、「中途半端に解く問題」の計算を行う
    #1問あたりの得点が高い方を選んだ方が得。D*100点問題から埋めていく。
    #ただしその問題でボーナスをもらっていた場合はすでに計算に入れているので、スキップする必要がある
    #さらに、重要なこととして、「ボーナスをもらわない問題」は1種類で十分である
    #なぜなら、「ボーナスをもらわない問題」を2問作るくらいなら、その2問のうち1問あたりの得点が高い方に集中させた方がいいからである。

    #「中途半端に解く問題」をどれにするか決めて、そのインデックスをhampaに格納する
    hampa = D-1 #D*100点問題
    while (L[hampa]==1)and(hampa>=0): #もし「ボーナスをもらう問題」に入れていたら
        hampa+=-1 #次に得点が高い問題を候補とする
        #ただし、[1,1,1,1,1,1,1,1,1,1]の時はそもそも「中途半端に解く問題」は作らない
        #hampaが負になったら抜ける、という方法でそれを実装している

    if hampa==-1: #先述のように、hampaが負の時は「中途半端に解く問題」は作らない
        cnt = 0
    else:
        cnt = 0 #「中途半端に解く問題」を解いた数を格納
        #「中途半端に解く問題」を解き進める条件は「今まだ得点がGに達していないこと」及び「あと一問解いてもまだ中途半端であること」
        while (point<G)and(cnt<PC[hampa][0]):
            cnt+=1
            num+=1
            point+=(hampa+1)*100

    #以上でこのシナリオにおける計算はおしまい、
    #「中途半端に解く問題」が1種類ではGに届いていないケースもある。
    #その場合はこの時点でpointはG未満であり、outの候補としては不適切。除くことが必要。
    if (point>=G)and(num<out): #問題数の最小値を更新したら、outに格納
        out=num
print(out)

Submission status: Accepted

Solution code:
import itertools
# 入力もらう
D,G = list(map(int,input().split()))
PC = []
for i in range(D):
    PC.append(list(map(int,input().split())))

#[0,0,0,0,0,0,0,0,0,0]という形で、どのボーナスをもらうかを管理したい
#例えば[1,0,0,0,1,0,0,0,0,0]は100点問題と500点問題のボーナスをもらうということ
#2^D通り(D<=10)だから全探索できる(もちろん全部0というのはありえないけど)
#itertools使って2^D通りのケースを用意
a = [0,1]
Ls = list(itertools.product(a, repeat=D))

#pは100以下、Dは10以下だから解く問題数は多くて1000
#最大値を初期値として設定して、小さい値が実現できたら更新していく
out = 1000

#戦略としては、「ボーナスをもらう問題」を先に決めて計算し、
#その後「中途半端に解く問題」を合計得点がGに足るまで計算する、というもの。

for L in Ls: #どの問題でボーナスをもらうか、2^D通りのシナリオを逐一チェック
    #Lには「ボーナスをもらう問題」をどれにするか決めた結果が格納されている
    num = 0 #このシナリオにおける解いた問題の数
    point = 0 #このシナリオにおける得点

    #このシナリオにおいて「ボーナスをもらう問題」をまずは計算
    for i in range(D):
        if L[i]==1: #ボーナスをもらう問題では
            num+=PC[i][0] #解いた問題の数にプラス
            point+=PC[i][1] #特典もプラス
            point+=(i+1)*100*PC[i][0] #ボーナスもプラス

    #ここから、「中途半端に解く問題」の計算を行う
    #1問あたりの得点が高い方を選んだ方が得。D*100点問題から埋めていく。
    #ただしその問題でボーナスをもらっていた場合はすでに計算に入れているので、スキップする必要がある
    #さらに、重要なこととして、「ボーナスをもらわない問題」は1種類で十分である
    #なぜなら、「ボーナスをもらわない問題」を2問作るくらいなら、その2問のうち1問あたりの得点が高い方に集中させた方がいいからである。

    #「中途半端に解く問題」をどれにするか決めて、そのインデックスをhampaに格納する
    hampa = D-1 #D*100点問題
    while (L[hampa]==1)and(hampa>=0): #もし「ボーナスをもらう問題」に入れていたら
        hampa+=-1 #次に得点が高い問題を候補とする
        #ただし、[1,1,1,1,1,1,1,1,1,1]の時はそもそも「中途半端に解く問題」は作らない
        #hampaが負になったら抜ける、という方法でそれを実装している

    if hampa==-1: #先述のように、hampaが負の時は「中途半端に解く問題」は作らない
        cnt = 0
    else:
        cnt = 0 #「中途半端に解く問題」を解いた数を格納
        #「中途半端に解く問題」を解き進める条件は「今まだ得点がGに達していないこと」及び「あと一問解いてもまだ中途半端であること」
        while (point<G)and(cnt<PC[hampa][0]):
            cnt+=1
            num+=1
            point+=(hampa+1)*100

    #以上でこのシナリオにおける計算はおしまい、
    #「中途半端に解く問題」が1種類ではGに届いていないケースもある。
    #その場合はこの時点でpointはG未満であり、outの候補としては不適切。除くことが必要。
    if (point>=G)and(num<out): #問題数の最小値を更新したら、outに格納
        out=num
print(out)

Submission status: Accepted

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

a = [0,1]
Ls = list(itertools.product(a, repeat=D))

out = 1000
for L in Ls:
    num = 0
    point = 0
    for i in range(D):
        if L[i]==1:
            num+=PC[i][0]
            point+=PC[i][1]
            point+=(i+1)*100*PC[i][0]
    hampa = D-1
    while (L[hampa]==1)and(hampa>=0):
        hampa+=-1
    if hampa==-1:
        cnt = 0
    else:
        cnt = 0
        while (point<G)and(cnt<PC[hampa][0]):
            cnt+=1
            num+=1
            point+=(hampa+1)*100
    if (point>=G)and(num<out):
        out=num
print(out)

Submission status: Accepted

Solution code:
from math import ceil


def dfs(i, sum, count, residue):
    global ans
    if i == d:
        if sum < g:
            use = max(residue)
            n = min(pc[use - 1][0], ceil((g - sum) / (use * 100)))
            count += n
            sum += n * use * 100

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

    else:
        dfs(i + 1, sum, count, residue)
        dfs(i + 1, sum + pc[i][0] * (i + 1) * 100 + pc[i][1], count + pc[i][0], residue - {i + 1})


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

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


nokori = set(range(1, d+1))


def dfs(i, sum, nokori, cnt):
    global ans
    if i == d:
        if sum < g:
            use = max(nokori)
            n = min(pc[use-1][0], -(-(g-sum)//(use*100)))
            cnt += n
            sum += n * use*100
        if sum >= g:
            ans = min(ans, cnt)
    else:
        dfs(i+1, sum, nokori, cnt)
        dfs(i+1, sum + pc[i][0] * (i+1) * 100 +
            pc[i][1], nokori-{i+1}, cnt+pc[i][0])


ans = float('inf')

dfs(0, 0, nokori, 0)

print(ans)

Submission status: Accepted

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

ans = float('inf')

for i in range(2**d):
    sum = 0
    cnt = 0
    nokori = set(range(1, d+1))
    for j in range(d):
        bitchk = 2**j
        if i & bitchk:
            sum += pc[j][0]*100*(j+1) + pc[j][1]
            cnt += pc[j][0]
            nokori.discard(j+1)
    if sum < g:
        use = max(nokori)
        # -(-(g-sum)//(use*100))は切り上げ除算
        # pc[use-1][0]はその点数帯の問題数（解ける最大数）
        # -(-(g-sum)//(use*100))でgを超えるのに必要な問題数を出せる。
        # ex) 300点問題が4問残ってるとする。不足している点数(g-sum)が500点のとき
        # -(-500//300)で2問解く必要があることがわかる。
        n = min(pc[use-1][0], -(-(g-sum)//(use*100)))
        # n = (-(-(g-sum)//(use**100)))
        sum += n * use * 100
        cnt += n

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

print(ans)

Submission status: Accepted

Solution code:
D,G=list(map(int,input().split()))
l=[list(map(int,input().split())) for i in range(D)]
cnt=0
tmp=0
dep=0
import math
m=set(range(D))
def main(cnt,tmp,dep,m):
   if dep==D:
      if tmp>=G:
         return cnt
      else:
         tmp=G-tmp
         if tmp <= (max(m)+1)*l[max(m)][0]*100:
            cnt+=math.ceil(tmp/((max(m)+1)*100))
            return cnt
         else:
            return float("Inf")
   return(min(main(cnt+l[dep][0],tmp+100*(dep+1)*l[dep][0]+l[dep][1],dep+1,m-{dep}),main(cnt,tmp,dep+1,m))) 
print(main(0,0,0,m))

Submission status: Accepted

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

# データ読み込み
d, g = map(int, input().split())
p = []
c = []
for i in range(d):
    pi, ci = map(int, input().split())
    p.append(pi)
    c.append(ci)

ans = sum(p) # 全部解いた場合を初期値にする

for i in range(1<<d): # 組み合わせループ（2^dパターン）
    score = 0
    count = 0

    # 完答問題の組み合わせから点数を計算する
    for k in range(d):
        if i>>k&1: # 1になっているビットに対応するボーナスポイントを獲得したとする
            score += (k+1)*100*p[k] # 通常得点を加算
            score += c[k] # ボーナスポイントを加算
            count += p[k] # 問題数を加算

    # print(bin(i),count, score)

    # 完答問題だけでスコアが目標を超えていなければ、残りの問題をスコアが目標に達するまで解く
    add_count = 0
    if score < g:
        flag = 0
        add = 0
        for k in range(d,0,-1): # k桁の上の桁からサーチ
            if not i>>(k-1)&1: # 完答していない問題(k桁目が0になっているビット)について
                for j in range(1, p[k-1], 1): # j問解いたとき
                    add += k*100
                    score += k*100 # 加算点
                    add_count += 1
                    # print('k,j,count,add_count',k,j,count, add_count)
                    if score >= g:
                        flag = 1
                        break
            if flag == 1:
                break

    count += add_count
    # print(bin(i), count, score, add)
    # 回数を更新
    if score >= g and ans > count:
        ans = count

print(ans)

Submission status: Accepted

Solution code:
from sys import stdin
from collections import OrderedDict
import math


if __name__ == "__main__":
    _in = [_.rstrip() for _ in stdin.readlines()]
    D,G = list(map(int,_in[0].split(' ')))  # type:list(int)
    p_c_arr = []
    for i in range(D):
        _ = list(map(int,_in[i+1].split(' ')))  # type:list(int)
        p_c_arr.append(_)
    # vvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvv
    cnt = float('inf')
    for bit in range(1<<D):
        score = 0
        prob = 0
        cache = OrderedDict()
        for i in range(D-1,-1,-1):
            if bit&(1<<i):
                score += 100*(i+1)*p_c_arr[i][0]+p_c_arr[i][1]
                prob += p_c_arr[i][0]
            else:
                cache[i+1] = p_c_arr[i]
        else:
            if score < G:
                for k,v in cache.items():
                    if G-score <= 100*k*(v[0]-1):
                        prob += math.ceil((G-score)/(100*k))
                        break
                    elif G-score <= 100*k*v[0]+v[1]:
                        prob += v[0]
                        break
                    else:
                        score += 100*k*v[0]+v[1]
                        prob += v[0]
        cnt = min(cnt,prob)
    ## ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
    print(cnt)

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=10000000000000000000
for i in range(1<<d):
    s=0
    ans_=0
    for j in range(d):
        if (i>>j)&1:
            s+=(pc[j][1]+pc[j][0]*100*(j+1))
            ans_+=pc[j][0]
    #print(s,ans_)
    if s>=g:
        ans=min(ans,ans_)
    else:
        for j in range(d-1,-1,-1):
            if not((i>>j)&1):
                if s+(pc[j][0]*100*(j+1))>=g:
                    h=-((s-g)//(100*(j+1)))
                    s+=(h*100*(j+1))
                    ans_+=h
                    ans=min(ans,ans_)
                    break
                else:
                    break
print(ans)
#ansとans_
#謎のWA

Submission status: Accepted

Solution code:
#!/usr/bin python3
# -*- coding: utf-8 -*-

def main():
    D, G = map(int, input().split())
    P = [0] * D
    C = [0] * D
    for i in range(D):
        p, c = map(int,input().split())
        P[i] = p
        C[i] = p * 100 * (i+1) + c

    ret = 1000
    for i in range(2 ** D):
        pt = 0
        ct = 0
        for j in range(D):
            if i >> j & 1:
                pt += C[j]
                ct += P[j]
            else:
                mxi = j
        for j in range(P[mxi]):
            if pt>=G:
                break
            else:
                pt += 100*(mxi+1)
                ct += 1
        if pt>=G:
            ret = min(ret, ct)
    print(ret)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys 
sys.setrecursionlimit(10**8)

def dfs(i,sum,count,nokori):
  global ans
  if i==d:
    if sum<g:
      use=max(nokori)
      n=min(pc[use-1][0],-(-(g-sum)//(100*use)))
      count +=n
      sum +=n*100*use

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

  else:
    dfs(i+1,sum,count,nokori)
    dfs(i+1,sum+pc[i][0]*100*(i+1)+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)