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:
# -*- coding: utf-8 -*-
"""
Created on Sun Aug  5 19:16:59 2018
ABC104C
@author: maezawa
"""
import math

d, g = list(map(int, input().split()))
p = []
c = []
for i in range(d):
    pi, ci = list(map(int, input().split()))
    p.append(pi)
    c.append(ci)
 
min_cnt = 10**11 
    
for i in range(2**d):
    istr = '0'*d + format(i,'b')
    used = []
    cnt = 0
    maney = 0   
    for j in range(d):
        if istr[-1-j] == '1':
            maney += c[j]+p[j]*(j+1)*100
            cnt += p[j]
            used.append(j)
    if maney >= g:
        if min_cnt > cnt:
            min_cnt = cnt
            #print(istr)
            continue
    else:
        k = d-1
        while k>=0:
            if k not in used:
                break 
            k -= 1
        rem = math.ceil((g-maney)/(100*(k+1)))
        if rem >= p[k]:
            continue
        else:
            cntp = cnt + rem
            if min_cnt > cntp:
                min_cnt = cntp
                #print(istr, rem)
                continue
    #print(min_cnt, istr)
print(min_cnt)

Submission status: Accepted

Solution code:
from collections import defaultdict

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

bonus=[]

for i in range(D):
  a,b=map(int,input().split())
  bonus.append([a,b])

def solve(bit):
  ans=0
  turn=0
  for j in range(D):
    if (bit >> j ) % 2:
      ans+=(bonus[j][0] * (j+1) * 100 + bonus[j][1])
      turn+=bonus[j][0]
  if ans >= G:
    return turn
  for k in range(D-1,-1,-1):
    if (bit >> k ) % 2 == 0:
      for l in range(bonus[k][0]-1):
        ans += (k+1)*100
        turn += 1
        if ans >= G:
          return turn
  return -1
        

bits = (1 << D)

res=10**10
for i in range(bits):
  c=solve(i)
  if c > 0:
    res=min(res,c)
  
print(res)

Submission status: Accepted

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

Ans = []
# 全問解答する得点をbit全探索
for i in range(2**D):
    bits = bin(2**D+i)[3:]
    # 全問解いた時の得点と問題数を計算
    total,ans = 0,0
    for i,b in enumerate(bits):
        if b=="1":
            total += A[i]
            ans += P[i]
    # 目標を超えているなら解答候補に追加
    if total >= G:
        Ans.append(ans)
    # 目標を超えていないなら残りのうち一番得点が高い問題を順次解答
    else:
        j = 0 # 問題の前提から0で問題ない
        for i,b in enumerate(bits):
            if b=="0":
                j = i
        # 必要な残得点が問題数で達成可能かどうか
        res =  G - total
        if res/((j+1)*100) <= P[j]:
            ans += ceil(res/((j+1)*100))
            Ans.append(ans)

# 候補のうち最小のものが答え
print(min(Ans))

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)

num = float("inf")
for i in range(1 << d):
    cnt = 0
    rec = 0
    for j in range(d):
        if i & 1 << j:
            cnt += P[j]
            rec += P[j] * (j + 1) * 100
            rec += C[j]

    k = d - 1
    while k >= 0 and rec < g:
        if i & 1 << k:
            k -= 1
            continue
        else:
            q = 0
            while q < P[k] and rec < g:
                cnt += 1
                rec += (k + 1) * 100
                q += 1
        k -= 1

    if rec >= g:
        num = min(num, cnt)

print(num)

Submission status: Accepted

Solution code:
from itertools import product
D, G = map(int, input().split())
l = [tuple(map(int, input().split())) for i in range(D)]
s = [0] * D
ans = float('inf')
for b in product([0,1], repeat=D):
    s = sum([(i+1)*100 * l[i][0] + l[i][1] for i,f in enumerate(b) if f])
    tmp = sum([l[i][0] for i,f in enumerate(b) if f])
    if s < G:
        for i, j in enumerate(reversed(b)):
            if j == 0:
                d = D - i
                k = 0
                if s + 100 * d * (l[d-1][0] - 1 - k) < G:
                    tmp = float('inf')
                    break
                while True:
                    k += 1
                    if s + 100 * d * (l[d-1][0] - 1 - k) < G:
                        break
                tmp += l[d-1][0] - k 
                break
    ans = min(ans, tmp)
print(ans)

Submission status: Accepted

Solution code:
import math
from itertools import combinations
d,g = map(int,input().split())
x = []
for i in range(d):
    x1,y1=[int(i) for i in input().split()]
    x.append([x1,y1])
zy = [i for i in range(1,d+1)]
zyu = []
for i in range(d+1):
  zyu.extend(list(combinations(zy, i)))
ans2 = 100000000000000000000000
gou = g+0
for i in zyu:
  ans = 0
  g = gou +0
  for j in i:
    g -= (x[j-1][0] * j*100 + x[j-1][1])
    ans += x[j-1][0]
  if g >0:
    y = d+0
    while y in i:
      y -= 1
    a = x[y-1][0]
    if g > a*y*100:
      continue
    ans += math.ceil(g/(y*100))
  ans2 = min(ans,ans2)
print(ans2)

Submission status: Accepted

Solution code:
d,g=map(int,input().split())
p=[]
c=[]
for l in range(d):
    t1,t2=map(int,input().split())
    p.append(t1)
    c.append(t2)
ans=1e9
for i in range(1<<d):
    s=0
    n=0
    r=-1
    for j in range(d):
        if(i>>j & 1):
            s+=100*(j+1)*p[j]+c[j]
            n+=p[j]
        else:
            r=j
    if(s<g):
        s1=100*(r+1)
        ne=(g-s+s1-1)//s1
        if(ne>=p[r]):continue
        n+=ne
    ans=min(ans,n)
print(ans)

Submission status: Accepted

Solution code:
import bisect
from operator import itemgetter

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

curr_idx = d
curr_bit = 0
curr_cmp, curr_qtt = 0, 0
complete_combinations = [None] * (1 << d)
complete_combinations[0] = (0, 0, 0)
for use in range(1, 1 << d):
    if use & curr_bit == 0:
        curr_idx -= 1
        curr_bit = use
        curr_cmp = complete_scores[curr_idx]
        curr_qtt = problem_quantities[curr_idx]
    ps, pq, _ = complete_combinations[use ^ curr_bit]
    complete_combinations[use] = (ps + curr_cmp, pq + curr_qtt, use)

complete_combinations.sort()

bi = bisect.bisect(complete_combinations, (g,))

ans = float('inf')
for s, p, use in complete_combinations[:bi]:
    i = d
    while use & 1:
        i -= 1
        use >>= 1
    cmp = complete_scores[i - 1]
    remain = g - s
    if remain >= cmp:
        continue
    q = min(problem_quantities[i - 1], (remain - 1) // i + 1)
    ans = min(ans, p + q)

ans = min(ans, min(map(itemgetter(1), complete_combinations[bi:])))
print(ans)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Mon Aug  6 16:07:14 2018

@author: Yuki
"""


# 入力
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)

# 全部解いた場合の点数
MAX_POINT_LIST = []
for i in range(D):
    MAX_POINT_LIST.append(P[i] * 100 * (i + 1) + C[i])

# 全部解く問題のパターン最大2**10を全探索する。
res_list = []
flag = [False for i in range(D)]
for i in range(2**D):
    tmp_point = 0
    tmp_count = 0
    tmp_bin = bin(i)[2:].zfill(D)
    for ii in range(D):
        flag[ii] = False
        if tmp_bin[ii] == '1':
            flag[ii] = True
            tmp_point += MAX_POINT_LIST[ii]
            tmp_count += P[ii]
    if tmp_point >= G:
        res_list.append(tmp_count)
    else:
        for ii in range(D):
            if flag[ii] == False:
                # flag[ii]　この点数の問題を全解きしてない場合使える
                if tmp_point + (P[ii] - 1) * 100 *(ii + 1) >= G:
                    comp_cnt = (G - tmp_point - 1) // (100 * (ii + 1)) + 1
                    res_list.append(comp_cnt + tmp_count)
    # 今回のMAX_POINTだけでは足りない場合
    # MAX_POINTに選ばれていない点数のやつから足していく
                
print(min(res_list))

Submission status: Accepted

Solution code:
import math
d,g = map(int,input().split())
ans = []
data = []

for i in range(0,d):
    P,C = map(int,input().split())
    data.append((P,C,(i+1)*100))

def dfs(i,sum,a,last):
    if i >= d:
        p,c,point = data[last]
        if sum >= g-(c+p*point):
            global ans
            a += max(0,min(math.ceil((g-sum)/point),p))
            ans.append(a)
        return
    dfs(i+1,sum,a,last)
    p,c,point = data[i]
    if i != last:
        dfs(i+1,sum+c+p*point,a+p,last)

for i in range(0,d):
    p,c,point = data[i]
    dfs(0,0,0,i)
print(min(ans))

Submission status: Accepted

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

g //= 100

p = [0 for _ in range(d)]
c = [0 for _ in range(d)]
b = [0 for _ in range(d)]
for i in range(d):
    p[i], c[i] = map(int, input().split())
    b[i] = p[i] * (i + 1) + (c[i] // 100)

res = sum(p)
com = [0 for _ in range(d)]
for i in range(2 ** d):
    temp = i
    temp_res = 0
    total = 0
    for j in range(d):
        com[j] = temp % 2
        temp //= 2
        if com[j] == 1:
            total += b[j]
            temp_res += p[j]
    if total >= g:
        res = min(temp_res, res)
        #print(com, temp_res)
        continue

    j = d
    while total < g:
        j -= 1
        if j < 0:
            break
        if com[j] == 1:
            continue
        if (p[j] - 1) * (j + 1) + total >= g:
            temp_res += (g - total) // (j + 1)
            if (g - total) % (j + 1) != 0:
                temp_res += 1
            total += (p[j] - 1) * (j + 1)
            break
        else:
            temp_res += p[j] - 1
            total += (p[j] - 1) * (j + 1)
    if total >= g:
        #print(com, temp_res, total)
        res = min(temp_res, res)

print(res)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
d,g=map(int, input().split())
A=[]
a=0
b=0
for i in range(d):
  a,b=map(int, input().split())
  A.append([a,b])


minp=0#現時点での問題数の最小値（最初は全問題数の合計にしておく）
for i in range(d):
  minp+=A[i][0]



for i in range(2**d):
  sco=0 #点数
  pro=0 #問題数
  bini=bin(i)[2:].zfill(d)
  #print(bini)
  for j in range(d):
    if bini[j]=="1" : #iの2進数で1の問題セットは完全に解く
      pro+=A[j][0]
      sco+=A[j][0]*100*(j+1)+A[j][1]
  if sco<g : #このとき、解いてない中でスコア最大の問題を何問か解く必要がある
    #print(bini)
    totyuu=-1
    j=0
    while totyuu==-1 :
      if bini[d-j-1]=="0" :
        totyuu=d-j-1
      j+=1
    #print(totyuu)
    #print(g-sco)
    if g-sco<=(A[totyuu][0]-1)*100*(totyuu+1):
      pro=pro+(g-sco-1)//(100*(totyuu+1))+1
    else:
      pro=minp

  #print(str(pro)+" "+bini)

  if pro<minp :
    minp=pro

print(minp)

Submission status: Accepted

Solution code:
D,G=map(int,input().split())
#x問解いたときに得られる得点の最大値でDP
table=[(0,0)]*D
s=0
for i in range(D):
    p,c=map(int,input().split())
    table[i]=(p,c)
    s+=p
dp=[-1]*(s+1)
dp[0]=0
t=0
for i in range(D):
    for j in range(t,-1,-1):
        for k in range(1,table[i][0]+1):
            if k<table[i][0]:
                dp[j+k]=max(dp[j+k],dp[j]+100*(i+1)*k)
            else:
                dp[j+k]=max(dp[j+k],dp[j]+100*(i+1)*k+table[i][1])
    t+=table[i][0]
    #print(dp)
for i in range(s+1):
    if dp[i]>=G:
        print(i)
        break

Submission status: Accepted

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

for i in range(D) :
    p, c = map(int, input().split())
    scores.append((p, c))
    
# if n is perfect -> combination
def calc_for(mask) :
    score, cnt = 0, 0
    for i in range(len(mask)) :
        if mask[i] == "1" :
            score += (i + 1) * 100 * scores[i][0] + scores[i][1]
            cnt += scores[i][0]
            
    min_cnt = 10**20
    
    if score >= G :
        return cnt
    else :    
        for i in range(len(mask)) :
            if mask[i] != "1" :
                cnt_tmp = 0 # 中途半端分
                score_tmp = score # 中途半端分
                achieve_flg = False


                for j in range(scores[i][0] - 1) :
                    score_tmp += (i + 1) * 100
                    cnt_tmp += 1
                    
                    if score_tmp >= G :
                        achieve_flg = True
                        break

                if achieve_flg == True : 
                    min_cnt = min(min_cnt, cnt + cnt_tmp)

        return min_cnt
            
# generate permutations 
perms = []

def permsgen(S) :
    global perms
    if len(S) >= D :
        perms.append(S)
    else :
        permsgen(S + "0")
        permsgen(S + "1")

permsgen("")

# do calc 
min_cnt = 10**20
for p in perms :
    min_cnt = min(min_cnt, calc_for(p))
    
print(min_cnt)

Submission status: Accepted

Solution code:
from itertools import product
import math
D,G=list(map(int, input().strip().split()))
pc=[list(map(int, input().strip().split())) for i in range(D)]

minCount=float("inf")
# Completeする数字を全パターン選択
for idx in product(*([0,1]for i in range(D))):
    ct=0
    score=0
    max_0=-1
    for i,ix in enumerate(idx):
        if ix:
            ct+=pc[i][0]
            score+=pc[i][1]+pc[i][0]*100*(i+1)
        else:
            max_0=i
    if score<G and max_0>=0:
        pt=(max_0+1)*100
        add=int(math.ceil((G-score)/pt))
        if add<pc[max_0][0]:
            ct+=add
            score+=add*pt
    if score>=G and ct<minCount:
        minCount=ct
print(minCount)

Submission status: Accepted

Solution code:
from sys import stdin

D, G = [int(x) for x in stdin.readline().rstrip().split()]

list = []
for i in range(D):
    tmp = [int(x) for x in stdin.readline().rstrip().split()]
    list.append(tmp)

ans = 1e9

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) * list[i][0] + list[i][1]
            num += list[i][0]
        else:
            rest_max = i
    if s < G:
        s1 = 100 * (rest_max + 1)
        need = (G - s + s1 - 1) // s1
        if need >= list[rest_max][0]:
            continue
        num += need
    ans = min(ans, num)

print(ans)

Submission status: Accepted

Solution code:
# &演算子は、bit形式には使えない。でも、数値には使える
d, g = map(int, input().split())
p = [[0, 0] for i in range(d)]
for i in range(d):
    p[i][0], p[i][1] = map(int, input().split())
## bit全探索

ans = 100000
for i in range(2 ** d):
    sum = 0
    ans_tmp = 0
    s = bin(i)
    #　得点の合計とそれまでの数を反映。
    for j in range(d):
        if bin(2 ** j) == bin(2 ** j & i):
            sum += p[j][0] * (j+1) * 100 + p[j][1]
            ans_tmp += p[j][0]
    if sum < g:
        for j in range(d-1, -1, -1):
            if bin(2 ** j) != bin(2 ** j & i):
                for k in range(p[j][0]-1):
                    sum += (j+1) * 100
                    ans_tmp += 1
                    if g <= sum:
                        break
                if g <= sum:
                    if ans_tmp < ans:
                        ans = ans_tmp
                    break
            else:
                continue
    else:
        if ans_tmp < ans:
            ans = ans_tmp
print(ans)

Submission status: Accepted

Solution code:
D,G = map(int, input().split())
prob_num = []
bonus = []
comp_pt = []
for i in range(D):
    p,b = map(int, input().split())
    prob_num.append(p)
    bonus.append(b)
    comp_pt.append(100*(i+1)*p+b)

def dfs(hascomp:str, target:int, prob:int, depth:int) -> int:
    if target <= 0:
        #print(hascomp, depth, prob)
        return prob
    
    elif depth == D:
        for i in range(D-1,-1,-1):
            if hascomp[i] == "n":
                if target <= 100*(i+1)*(prob_num[i]-1):
                    prob += (target//(100*(i+1)))+bool(target%(100*(i+1)))
                    #print(hascomp, depth, prob)
                    return prob
                
                else:
                    prob += (prob_num[i]-1)
                    target -= 100*(i+1)*(prob_num[i]-1)
                    
        if target > 0:
            #print(hascomp, depth, prob)
            return 10**5
        
    else:
        new_tar = target-comp_pt[depth]
        new_prob = prob + prob_num[depth]
        return min(dfs(hascomp+"y",new_tar, new_prob, depth+1),
                   dfs(hascomp+"n",target, prob, depth+1))
        

ans = dfs("",G,0,0)
print(ans)

Submission status: Accepted

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

from collections import deque
import itertools as it
import sys
import math

sys.setrecursionlimit(10000000)

D, G = map(int, raw_input().split())
lst = []

for loop in range(D):
    p, c = map(int, raw_input().split())
    lst.append((p, c))

ans = 100000

for p in it.product([0, 1], repeat = D):
    S = 0
    cnt = 0
    rem = []
    for i in range(D):
        if p[i] == 1:
            S += 100 * (i + 1) * lst[i][0] + lst[i][1]
            cnt += lst[i][0]
        else:
            rem = [lst[i][0], i + 1]
    if S >= G:
        ans = min(ans, cnt)
        continue
    if S + 100 * rem[0] * rem[1] >= G:
        cnt += (G - S) / (100 * rem[1])
        if (G - S) % (100 * rem[1]) != 0:
            cnt += 1
        ans = min(ans, cnt)

print ans

Submission status: Accepted

Solution code:
from itertools import product as p

d,g=map(int,input().split())
l=[(0,0) for _ in range(d)]
for i in range(d):
  l[i]=tuple(map(int,input().split()))
f=lambda x:[i for (i,j) in enumerate(x) if j==0]
res={}

for i in p([0,1],repeat=d):
  b=f(i)
  cnt=0
  t_val=0

  for (j,k) in enumerate(i):
      if k:
        t_val+=((j+1)*100*l[j][0]+l[j][1])
        cnt+=(l[j][0])
  
  if b:
    inc=max(b)
    pl=g-t_val
    c_inc=0
    if pl>0:
      if pl%((inc+1)*100):
        c_inc=1+pl//((inc+1)*100)
      else:
        c_inc=pl//((inc+1)*100)
      if c_inc<l[inc][0]:
        t_val+=(c_inc*(inc+1)*100)
        cnt+=(c_inc)
      else:
        t_val+=((l[inc][0]-1)*(inc+1)*100)
        cnt+=(l[inc][0]-1)
  res[i]=(t_val,cnt)

o=sorted([i for i in res.values() if i[0]>=g],key=lambda x:x[1])
print(o[0][1])

Submission status: Accepted

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

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 solve(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]
    if G > s:
        n += solve(G - s, i - 1)
    return min(n, solve(G, i - 1))

print(solve(G, D))

Submission status: Accepted

Solution code:
from itertools import permutations

d, g = map(int, input().split())
g = g // 100
p = []
c = []

for _ in range(d):
	pp, cc = map(int, input().split())
	p.append(pp)
	c.append(cc // 100)

ans = float("inf")
for array in permutations(range(d)):
	gap = g
	num = 0
	for a in array:
		if p[a] * (a + 1) >= gap:
			num += (gap - 1) // (a + 1) + 1
			break
		elif p[a] * (a + 1) + c[a] >= gap:
			num += p[a]
			break
		else:
			num += p[a]
			gap -= p[a] * (a + 1) + c[a]

	if num < ans:
		ans = num

print(ans)

Submission status: Accepted

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

    min_p = 1001
    for i in range(2**d):
        s = 0
        max_s, t = -1, 0
        for j in range(d):
            if (i >> j) & 1:
                s += p[j] * (j+1) * 100 + c[j]
                t += p[j]
            else:
                max_s = j + 1

        if g <= s:
            min_p = min(t, min_p)
        elif max_s != -1 and (g-s) // (max_s*100) < p[max_s-1]:
            t += (g-s+max_s*100-1) // (max_s*100)
            min_p = min(t, min_p)

    print(min_p)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from itertools import product
from math import ceil
n,k=map(int,input().split())
A=[]
for i in range(1,n+1):
  a,b=map(int,input().split())
  A+=[(a,i*100,a*i*100+b)]

ans=1e9
for p in product([0,1],repeat=n):
  s=0
  c=0
  m=0
  for i,j in enumerate(p):
    if j==1:
      c+=A[i][0]
      s+=A[i][2]
    else:
      m=max(m,i)
  if s>=k:
    ans=min(ans,c)
  else:
    if (k-s)/A[m][1]<A[m][0]:
      ans=min(ans,c+ceil((k-s)/A[m][1]))
print(ans)

Submission status: Accepted

Solution code:
d, g = [int(i) for i in input().split()]
A, B = zip(*[[int(i) for i in input().split()] for j in range(d)])

D = [0] * 10
ans = 10 ** 3

for bit in range(1, 2**10+1):
    score = 0
    cnt = 0
    for i in range(d):
        if bit >> i & 1:
            score += A[i] * (i+1) * 100 + B[i]
            cnt += A[i]

    if not score >= g:
        for i in range(d-1, -1, -1):
            if not bit >> i & 1:
                for j in range(A[i]):
                    score += (i+1) * 100
                    cnt += 1
                    if score >= g:
                        break
                else:
                    continue
                break

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

print(ans)

Submission status: Accepted

Solution code:
from itertools import combinations

def exclude_combi_idx(combis, scores):
    a = [score[1] for score in combis]
    v = []
    for score in scores:
        if score[1] in a:
            continue
        v.append(score)
    return v

def set_all_solve(combi):
    current = 0
    num = 0
    for item in combi:
        num += item[0]
        current += item[2]
    return num, current

def track_residue(num, score, current, target):
    for i in range(num):
        current += score
        if current >= target:
            return i + 1
    return None

def main():
    D, G = [int(c) for c in input().split()]
    items = []
    for idx in range(1, 1+D):
        num, bonasu = [int(c) for c in input().split()]
        items.append((idx * 100, num, bonasu))
    scores = [(num, idx,idx * num + bonasu) for idx, num, bonasu in items]
    max_prob = sum([num for num,_, _ in scores])
    min_prob = max_prob
    for i in range(0, D+1):
        combis = list(combinations(scores, i))
        # print('i = {}, combinations = {}'.format(i, combis))
        for combi in combis:
            s = 0
            prob = 0
            # print('combi = {}'.format(combi))
            tmp, tmp2 = set_all_solve(combi)
            prob += tmp
            s += tmp2
            # print('all solves num = {} score = {}'.format(prob, s))
            if s >= G:
                if prob < min_prob:
                    min_prob = prob
                    continue
            else:
                v = exclude_combi_idx(combi, scores)[-1] # 値が最大のもののみ必要
                res = track_residue(v[0], v[1], s, G)
                if res is None:
                    continue
                if res + prob < min_prob:
                    # print('track solve: num = {}, score = {}'.format(res + prob, s))
                    min_prob = res + prob
    print(min_prob)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
d,g = map(int,input().split())
pc = [list(map(int,input().split()))for _ in[0]*d]
ans = []
for mask in range(1 << d):
    s = 0
    num = 0
    rest_max = -1
    for i in range(d):
        p,c = pc[i]
        if mask >> i & 1:
            s += p * 100 * (i + 1) + c
            num += p
        else:
            rest_max = i
    if s < g:
        s1 = 100 * (rest_max + 1)
        need = (g - s + s1 - 1) // s1
        if need >= pc[rest_max][0]:
            continue
        num += need
    ans.append(num)
print(min(ans))

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul

sys.setrecursionlimit(10000)


def read_int():
    return int(input())


def read_int_n():
    return list(map(int, input().split()))


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


@mt
def slv(D, G, PC):

    ans = sys.maxsize
    PC = list(reversed(PC))
    for i in product([0, 1], repeat=D):
        g = G
        p = 0
        for j, v in enumerate(i):
            if v == 0:
                continue
            p += PC[j][0]
            g -= PC[j][1] + PC[j][0] * (D-j) * 100
        if g > 0 and 0 in i:
            j = i.index(0)
            for _ in range(PC[j][0]-1):
                p += 1
                g -= (D-j)*100
                if g <= 0:
                    break
        if g <= 0:
            ans = min(ans, p)

    return ans


def main():
    D, G = read_int_n()
    PC = [read_int_n() for _ in range(D)]
    print(slv(D, G, PC))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
#coding:utf-8

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

ans = 1e9
for mask in range(1 << d):
    score = 0
    num = 0
    rest_max = -1
    for i in range(d):
        if mask >> i & 1:
            score += sums[i]
            num += P[i]
        else:
            rest_max = i
    if score < g:
        tmp = 100 * (rest_max + 1)
        need = (g - score + tmp - 1) // tmp
        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())
 
p = []
 
for i in range(d):
    p.append(list(map(int,input().split())))

from itertools import product
from math import ceil
 
ans = 1e09
 
for c in product([0,1],repeat=d):
    score = 0
    num = 0
    ind = 0
    for i in range(d):
        if c[i] == 1:
            score += p[i][0]*100*(i+1) + p[i][1]
            num += p[i][0]
        else:
            ind = max(i,ind)
    
    if g - score <= 0:
        ans = min(ans,num)
    elif g - score <= (p[ind][0]-1)*100*(ind+1):
        num += ceil((g-score)/(100*(ind+1)))
        ans = min(ans,num)
print(ans)

Submission status: Accepted

Solution code:
def c_all_green(D, G, Problems):
    ans = float('inf')
    for binary in range(1 << D):
        total_score = 0
        solved_problem = 0
        
        # 「全問正解する配点」の決定(1つも全問正解しない場合も含む)
        for k, (p, c) in enumerate(Problems):
            if binary & (1 << k) != 0:
                total_score += 100 * p * (k + 1) + c
                solved_problem += p

        # この時点で目標スコアを達成したなら、「中途半端に解く配点」
        # (解説に倣った呼び方)を考える必要はない
        if G <= total_score:
            ans = min(ans, solved_problem)
            continue

        # 「中途半端に解く配点」を決定
        for k, (p, c) in enumerate(reversed(Problems), 1):  # 高配点の順に見る
            if binary & (1 << (D-k)) != 0:
                continue  # 注目した配点はすでに全問正解した配点だった
            for _ in range(p):
                if G <= total_score:
                    break
                total_score += 100*(D-k+1)
                solved_problem += 1

        ans = min(ans, solved_problem)
    return ans

D, G = [int(i) for i in input().split()]
Problems = [[int(i) for i in input().split()] for j in range(D)]
print(c_all_green(D, G, Problems))

Submission status: Accepted

Solution code:
from collections import deque

def solve(count, i, g, pcs, rem):
    if g <= 0:
        return count
    if pcs == []:
        index, p = rem
        if index == 0:
            return count
        plus = g // (100 * index) + (1 if g % (100 * index) != 0 else 0)
        return count + plus if plus < p else float("Inf")
    p, c = pcs[0]
    l = pcs[1:]
    a = solve(count, i + 1, g, l, (i, p))
    b = solve(count + p, i + 1, g - c - 100 * i * p, l, rem)
    return a if a < b else b



if __name__ == "__main__":
    d, g = map(int, input().split())
    pcs = [tuple(int(s) for s in input().split()) for _ in range(d)]
    print(solve(0, 1, g, pcs, (0, 0)))