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:
#!usr/bin/env python3
from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS():return list(map(list, sys.stdin.readline().split()))
def S(): return list(sys.stdin.readline())[:-1]
def IR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = I()
    return l
def LIR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LI()
    return l
def SR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = S()
    return l
def LSR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = SR()
    return l
mod = 1000000007

#A
def A():
    return

#B
def B():
    return

#C
def C():
    def dfs(i,k):
        if i == d:
            l.append(k)
        else:
            for j in range(2):
                dfs(i+1,k+[j])
    d,g = LI()
    p = LIR(d)
    ans = float("inf")
    l = []
    dfs(0,[])
    for k in l:
        m = 0
        o = 0
        q = [[p[i][0],p[i][1]] for i in range(d)]
        for i in range(d):
            if k[i]:
                o += q[i][0]
                m += q[i][0]*(i+1)*100+q[i][1]
                q[i][0] = 0
        while m < g:
            for i in range(d)[::-1]:
                for j in range(q[i][0]):
                    m += (i+1)*100
                    o += 1
                    if m >= g:break
                if m >= g:break
        ans = min(ans,o)
    print(ans)
#D
def D():
    return

#E
def E():
    return

#F
def F():
    return

#G
def G():
    return

#H
def H():
    return

#Solve
if __name__ == "__main__":
    C()

Submission status: Accepted

Solution code:
D,target=map(int,input().split())
l=[]
ans=10**9

for i in range(D):
    l.append(list(map(int,input().split())))

for i in range(2**D):
    score=0
    problems=0
    resindex=-1
    for j in range(D):
        if i>>j&1==1:
            score+=(j+1)*100*l[j][0]+l[j][1]
            problems+=l[j][0]
        else:
            resindex=j

    if score>=target:
        ans=min(ans,problems)
    elif resindex>=0 and score+l[resindex][0]*(resindex+1)*100>=target:
        problems+=-(-(target-score)//((resindex+1)*100))
        ans=min(ans,problems)

print(ans)

Submission status: Accepted

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

counter = []

for i in range(1 << D):
    goukei = 0
    count = 0
    amari = [i for i in range(D)]
    for j in range(D):
        if (i >> j) & 1:
            goukei += p[j] * 100 * (j + 1) + c[j]
            count += p[j]
            amari.remove(j)
    if goukei < G:
        for i in range(p[max(amari)]):
            goukei += 100 * (max(amari) + 1)
            count += 1
            if goukei >= G:
                counter.append(count)
                break
    else:
        counter.append(count)

print(min(counter))

Submission status: Accepted

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

time_list = []
for i in range(1<<D):
    point = 0
    time = 0
    output = []
    #for j in range(D): 
        #print(i,j+1,bin(i>>j))
        #if ((i >> j) & 1) == 1: #ある数と1とのANDを取ることは，その数の右端のbitが0か1を調べることに等しい．iの右からj+1番目のbitが1かどうかを確認している．
            #output.append(A[j])
    #print(output)
    for d in range(D):
        if ((i>>d) & 1) == 1:
            point += 100*(d+1)* p[d] + c[d]
            time += p[d]
    if point < G:
        # iで一番左側にある0を探す。
        for d in range(D)[::-1]:
            if ((i>>d) & 1) == 0: # and論理積は1==1以外はすべてfalse
                for k in range(p[d]):
                    if point < G:
                        point += 100*(d+1) 
                        time += 1
                    else: break
                break
            else: continue
    if point >= G:
        time_list.append(time)
print(min(time_list))

Submission status: Accepted

Solution code:
import math

D, G = list(map(int, input().split()))
p = [list(map(int, input().split())) for _ in range(D)]
ResMin = 1000

for i in range(2**D):
    numProb = 0
    numPoint = 0
    maxProb = 0
    bonusflag = [0]*D
    for j in range(D):
        if ((i >> j) & 1):
            bonusflag[D-1-j] = 1

    for k in range(D):
        if bonusflag[k] == 1:
            numProb += p[k][0]
            numPoint += (100*(k+1)*p[k][0] + p[k][1])
        else:
            maxProb = k
    if numPoint < G:
        sub = math.ceil((G-numPoint)/(100*(maxProb+1)))
        if sub <= p[maxProb][0]:
            numProb += sub
        else:
            continue
    if numProb < ResMin:
        ResMin = numProb

print(ResMin)

Submission status: Accepted

Solution code:
D, G = map(int, input().split())
mat = [[int(i+1)] + list(map(int, input().split())) for i in range(D)]
# 基本は高い得点から順に解いたほうがよいが、コンプリートボーナスは別
# bit全探索をかけるようにする
cost_list = []
for i in range(1<<D):
    point = 0
    cost = 0
    for j in range(D):
        if ((i>>j) & 1) == 1:
            point += 100* mat[j][1] * mat[j][0] + mat[j][2]
            cost += mat[j][1]
    if point < G:
        # iで一番左側にある0を探す。
        for j in range(D)[::-1]:
            if ((i>>j) & 1) == 0: # and論理積は1==1以外はすべてfalse
                for k in range(mat[j][1]):
                    if point < G:
                        point += 100* mat[j][0] 
                        cost += 1
                    else: break
                break
            else: continue
    if point >= G:
        cost_list.append(cost)
print(min(cost_list))

Submission status: Accepted

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

p=[]
c=[]

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


def ans(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+=ans(g-s,t-1)
    
    return min(n,ans(g,t-1))

print(ans(g,d))

Submission status: Accepted

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

d,g = map(int,input().split())
p = []
s = []
for i in range(d):
    x,y = map(int,input().split())
    p.append(x)
    s.append(100*(i+1)*x+y)

ans = 10**10
for i in range(1<<(d+1)):
    cnt = 0
    res = 0
    tank = []
    for j in range(d):
        if (i>>j)&1 == 1:
            cnt += s[j]
            res += p[j]
        else:
            tank.append([100*(j+1),p[j]])
    if cnt >= g:
        ans = min(ans,res)
    else:
        while cnt < g and tank[-1][1] > 0:
            cnt += tank[-1][0]
            tank[-1][1] -= 1
            res += 1
        if cnt >= g:
            ans = min(ans,res)
print(ans)

Submission status: Accepted

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


MAX_BIT = (1 << D)
minimum = 1000000000
# 各ビットが1のとき全部解く
for patternBit in range(MAX_BIT):
    if patternBit >= MAX_BIT:
        continue
    p = patternBit
    score = 0
    ans1 = 0
    use_c = None
    for i, c in enumerate(Ci):
        s = (i + 1) * 100 #1問のスコア
        if p % 2 > 0:
            score += s * c[0] + c[1]
            ans1 += c[0]
        else:
            use_c = c + [s]
        p = p // 2
    if score < G:
        remain = G - score
        add_count = remain // use_c[2]
        if remain % use_c[2] > 0:
            add_count += 1
        if add_count > use_c[0]:
            continue
        ans1 += add_count
    minimum = min(minimum, ans1)
    
print(minimum)

Submission status: Accepted

Solution code:
D,G =(int(i) for i in input().split())
pc = [[int(j) for j in input().split()] for i in range(D)]
unuse = -1
point = total = 0
G /= 100
answer = 1000
for i in range(1 << len(pc)):
  point = 0
  total = 0
  unuse = -1
  for j in range(len(pc)):
    if ((i >> j) & 1) == 1:
      point += pc[j][0] * (j+1) + (pc[j][1] / 100)
      total += pc[j][0]
    else:
      unuse = max(unuse,j)
    if(point >= G):
      answer = min(answer,total)
    elif(unuse > -1 and point + (pc[unuse][0] - 1) * (unuse + 1) >= G):
      if((G - point) % (unuse + 1) == 0):
        answer = min(answer, total+int((G - point) // (unuse + 1)))
      else:
        answer = min(answer, total+int((G - point) // (unuse + 1))+1)     
print(answer)

Submission status: Accepted

Solution code:
import math, string, itertools, fractions, heapq, collections, re,  array, bisect, sys, random, time, copy, functools
sys.setrecursionlimit(10**7)
inf = 10 ** 20
eps = 1.0 / 10**10
mod = 10**9+7
dd = [(-1, 0), (0, 1), (1, 0), (0, -1)]
ddn = [(-1, 0), (-1, 1), (0, 1), (1, 1), (1, 0), (1, -1), (0, -1), (-1, -1)]
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)

D, G = LI()
PC = []
for i in range(D):
    PC.append([(i+1)*100] + LI())

PC = [tuple(i) for i in PC]

results = []
# 完答しない場合もある。
result = 0
count = 0
for i in range(PC[-1][1]):
    result += PC[-1][0]
    count += 1
    if result >= G:
        results.append(count)

for i in range(1, D+1):
    # i種類の組み合わせを選ぶ
    combis = list(itertools.combinations(PC, i))
    #  print('i, combis', i, combis)
    for combi in combis:
        # iは完答する種類数
        result = 0
        result += sum([c[0] * c[1] + c[2] for c in combi])
        count = sum([c[1] for c in combi])
        if result >= G:
            results.append(count)
            continue
        rest = [_ for _ in PC if _ not in combi]
        for r in rest[::-1]:
            for ridx in range(r[1]):
                result += r[0]
                count += 1
                if result >= G:
                    results.append(count)
print(min(results))

Submission status: Accepted

Solution code:
import math, string, itertools, fractions, heapq, collections, re,  array, bisect, sys, random, time, copy, functools


sys.setrecursionlimit(10**7)
inf = 10 ** 20
eps = 1.0 / 10**10
mod = 10**9+7
dd = [(-1, 0), (0, 1), (1, 0), (0, -1)]
ddn = [(-1, 0), (-1, 1), (0, 1), (1, 1), (1, 0), (1, -1), (0, -1), (-1, -1)]


def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)

D, G = LI()
PC = []
for i in range(D):
    PC.append([(i+1)*100] + LI())

PC = [tuple(i) for i in PC]

# 全探索でよくね
# 組み合わせを選んで、高いほうから選んでいく。
# 組み合わせの数が少ない順に試していく
"""
1種類の場合
2種類の場合
3種類の場合
...
10種類の場合
Gを超えだしたらその種類数の中で決める。

10Cr
という形になる。
最大でも組み合わせの数は260通りほどなのでいけそうだ。
"""
results = []
def dfs(ls, limit, combis, count):
    is_end = True
    for i in range(len(ls)):
        #  print('saiki i, ls', i, ls)
        new_list = [_ for _ in ls]
        if new_list[i] < combis[i][1]:
            # 余力があればプラス
            new_list[i] += 1
            is_end = False

            p = 0
            for idx, j in enumerate(ls):
                #  if ls == [2,5]:
                #      import pdb
                #      pdb.set_trace()
                # 点数計算
                p += combis[idx][0] * j
                if j == combis[idx][1]:
                    p += combis[idx][2]

            if p >= G:
                results.append(count)
                return

            dfs(new_list, limit, combis, count+1)

# 完答しない場合もある。
result = 0
count = 0
for i in range(PC[-1][1]):
    result += PC[-1][0]
    count += 1
    if result >= G:
        results.append(count)
for i in range(1, D+1):
    # i種類の組み合わせを選ぶ
    combis = list(itertools.combinations(PC, i))
    #  print('i, combis', i, combis)
    for combi in combis:
        limit = sum([j[1] for j in PC])
        # iは完答する種類数
        result = 0
        result += sum([c[0] * c[1] + c[2] for c in combi])
        count = sum([c[1] for c in combi])
        if result >= G:
            results.append(count)
            continue
        rest = [_ for _ in PC if _ not in combi]
        for r in rest[::-1]:
            for ridx in range(r[1]):
                result += r[0]
                count += 1
                if result >= G:
                    results.append(count)

                

print(min(results))

Submission status: Accepted

Solution code:
D, G = map(int, input().split())
PC = []
for i in range(D):
    pi, ci = map(int, input().split())
    PC.append([pi, ci])
# dp[i][j]:得られる得点  (i番目の問題まで見る といた問題数j)
dp = [[0 for _ in range(2000)]for i in range(11)]
# print(dp)
for i in range(D):
    for j in range(1001):
        # k問解く(中途半端に解く)
        for k in range(PC[i][0]):
            #print(i, j, k)
            dp[i+1][j+k] = max(dp[i+1][j+k], dp[i][j]+k*(i+1)*100)
        # コンプボーナスもらえるまで解く
        dp[i + 1][j + PC[i][0]] = max(dp[i + 1][j + PC[i][0]],
                                      dp[i][j] + PC[i][0] * (i + 1) * 100 + PC[i][1])

# print(dp)
for j in range(1001):
    if dp[D][j] >= G:
        print(j)
        break

Submission status: Accepted

Solution code:
D,G = map(int,input().split())
b = []
c = []
for i in range(D):
    x,y = map(int,input().split())
    b.append(x)
    c.append(y)
res = 1e9
for i in range(1<<D):
    s = format(i,"0"+str(D)+"b")
    score = 0
    num = 0 
    for j in range(D):
        if s[j]=='1':
            num+=b[j]
            score += b[j]*(j+1)*100 + c[j]
    if score >= G:
        res = min(num,res)
    else:
        for j in range(D)[::-1]:
            if s[j] == '0':
                if score + (b[j]-1)*100*(j+1)>=G:
                    if (G-score)%(100*(j+1))==0:
                        num+= (G-score)//(100*(j+1))
                        score = G
                    else:
                        num+= (G-score)//(100*(j+1)) + 1
                        score = G
                    break
                else:
                    num+= b[j]-1
                    score += (b[j]-1)*100*(j+1)
        if score>=G:
            res = min(num,res)
print(res)

Submission status: Accepted

Solution code:
d, g=map(int, input().split())
p_list=[]
c_list=[]
all_list=[]
for i in range(d):
    p, c=map(int, input().split())
    p_list.append(p)
    c_list.append(c)
    all_list.append(100*(i+1)*p+c)



answer=[]

for i in range(2**d):
    number=0
    sum_score=0
    flag=0
    used_number=[]
    for j in range(d):
        if (i>>j)&1:
            sum_score=sum_score+all_list[j]
            number=number+p_list[j]
            used_number.append(j)
    if sum_score>=g:
        answer.append(number)
    else:
        for k in range(d-1, -1, -1):
            if not k in used_number:
                for l in range(p_list[k]):
                    if sum_score+100*(k+1)*l>=g:
                        answer.append(number+l)
                        flag=1
                        break
            if flag:
                break

print(min(answer))

Submission status: Accepted

Solution code:
import math

d, g = [int(i) for i in input().split(" ")]
p = [0] * (d + 1)
c = [0] * (d + 1)

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

p_min = 10000

def cp(a):
    global p_min
    r = g - sum([(p[i] * 100 * i + c[i]) * a[i] for i in range(1, d + 1)])
    ps = sum([p[i] * a[i] for i in range(1, d + 1)])
    if r <= 0:
        if ps < p_min:
            p_min = ps
        return
    
    for i in reversed(range(1, d + 1)):
        if a[i] == 0:
            s = (p[i] - 1) * 100 * i
            if r - s <= 0:
                ps += math.ceil(r / (100 * i))
                if ps < p_min:
                    p_min = ps
                break
            else:
                ps += p[i] - 1
                r -= s

def trav(a):
    global d
    if len(a) == d + 1:
        cp(a)
    else:
        trav(a + [0])
        trav(a + [1])

trav([0])

print(p_min)

Submission status: Accepted

Solution code:
# """
# コンプリートするものと、せざるものに分ける
# コンプリートしないものに関しては、得点の高い方から一個だけ潰す
# """

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

q_min = 1000000
for i in range(2**D):
    Gtmp = G
    ps = [p for p in ps_ini]
    s = "{:010b}".format(i)[::-1]
    q_all = 0
    for j,(p,c) in enumerate(zip(ps,cs)):
        # ボーナスの考慮
        Gtmp -= (p*(j+1)*100+c)*int(s[j]) 
        q_all += p*int(s[j])
        ps[j] -= p*int(s[j])
    # print(s,ps)
    if Gtmp <= 0:
        q_min = min(q_min, q_all)
    else:
        # コンプしていない問題で一番大きいやつ
        ind = 0
        for i,p in enumerate(ps):
            if p != 0:
                ind = i
        # print(Gtmp,ind,Gtmp//((ind+1)*100))
        # 比較
        if Gtmp//((ind+1)*100) > ps[ind]:
            continue
        if Gtmp%((ind+1)*100) == 0:           #割り切れない
            q_all += (Gtmp//((ind+1)*100))
        else:                           #割り切れる
            q_all += (Gtmp//((ind+1)*100) + 1) #最大値をコンプする以外ありえん
        q_min = min(q_min, q_all)
print(q_min)

Submission status: Accepted

Solution code:
d, g = map(int, input().split())
a = []
c = []
for i in range(d):
    a.append(list(map(int, input().split())))
for i in range(2 ** d):
    summ = 0
    count = 0
    j = list(bin(i)[2:].zfill(len(bin(2 ** d - 1)[2:])))
    for k in range(len(j)):
        summ += int(j[k]) * a[k][0] * (k+1) * 100
        if j[k] == '1':
            count += a[k][0]
            summ += a[k][1]
    if summ >= g:
        c.append(count)
        continue
    elif summ < g:
        idx = 0
        for l in range(len(j) - 1, 0, -1):
            if j[l] == '0':
                idx = l
                break
        for m in range(1, a[idx][0]):
            summ += (idx+1) * 100
            count += 1
            if summ >= g:
                c.append(count)
                break

print(min(c))

Submission status: Accepted

Solution code:
import math

INF = 1000000007

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)


def main():
    ans = INF

    # 2 ** D - 1 まで
    for b in range(2 ** D):
        num = 0
        pnt = 0

        # コンプリートしない MAX
        x = None

        # 得点が高い方から
        for i in range(D - 1, -1, -1):
            # i 番目 の フラグ が 立っている
            if b >> i & 1:
                num += p[i]
                # コンプリートする
                pnt += c[i] + 100 * (i + 1) * p[i]

            elif x is None:
                x = i

        # コンプリート オール
        # または 既に 目標の 総合スコア に到達
        if x is None or G <= pnt:
            ans = min(ans, num)

        # コンプリートしない
        elif math.ceil((G - pnt) / (100 * (x + 1))) < p[x]:
            ans = min(ans, num + math.ceil((G - pnt) / (100 * (x + 1))))

    print(ans)
    return


main()

Submission status: Accepted

Solution code:
INF = 1000000007

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)


def main():
    ans = INF

    # 2 ** D - 1 まで
    for b in range(2 ** D):
        num = 0
        pnt = 0

        # コンプリートしない MAX
        x = None

        # 得点が高い方から
        for i in range(D - 1, -1, -1):
            if b >> i & 1:
                num += p[i]
                # コンプリートする
                pnt += c[i] + 100 * (i + 1) * p[i]

            elif x is None:
                x = i

        # コンプリート オール
        if x is None:
            ans = min(ans, num)
            continue

        flg = True

        for i in range(p[x]):
            if G <= pnt:
                break

            pnt += 100 * (x + 1)
            num += 1

            # コンプリートした
            # 無効
            if i == p[x] - 1:
                flg = False

        if not flg:
            continue

        ans = min(ans, num)

    print(ans)
    return


main()

Submission status: Accepted

Solution code:
INF = 1000000007

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)


def main():
    ans = INF

    # 2 ** D - 1 まで
    for b in range(2 ** D):
        num = 0
        pnt = 0

        # コンプリートしない MAX
        x = None

        # 得点が高い方から
        for i in range(D - 1, -1, -1):
            if b >> i & 1:
                num += p[i]
                # コンプリートする
                pnt += c[i] + 100 * (i + 1) * p[i]

            elif not x:
                x = i

        # コンプリート オール
        if x is None:
            ans = min(ans, num)
            continue

        flg = True

        for i in range(p[x]):
            if G <= pnt:
                break

            pnt += 100 * (x + 1)
            num += 1

            # コンプリートした
            # 無効
            if i == p[x] - 1:
                flg = False

        if not flg:
            continue

        ans = min(ans, num)

    print(ans)
    return


main()

Submission status: Accepted

Solution code:
D,G = map(int,input().split())
b = []
c = []
for i in range(D):
    x,y = map(int,input().split())
    b.append(x)
    c.append(y)
res = 10**18
for i in range(1<<D):
    s = format(i,"0"+str(D)+"b")
    score = 0
    num = 0 
    for j in range(D):
        if s[j]=='1':
            num+=b[j]
            score += b[j]*(j+1)*100 + c[j]
    if score >= G:
        res = min(num,res)
    else:
        for j in range(D)[::-1]:
            if s[j] == '0':
                if score + (b[j]-1)*100*(j+1)>=G:
                    if (G-score)%(100*(j+1))==0:
                        num+= (G-score)//(100*(j+1))
                        score = G
                    else:
                        num+= (G-score)//(100*(j+1)) + 1
                        score = G
                    break
                else:
                    num+= b[j]-1
                    score += (b[j]-1)*100*(j+1)
        if score>=G:
            res = min(num,res)
print(res)

Submission status: Accepted

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

def dfs(d, g):
  if(d == 0):
    return 1e9

  x = min(g//(100*d), PC[d][0])
  point = x*100*d

  if(x == PC[d][0]):
    point += PC[d][1]
  
  if(point < g):
    x += dfs(d-1, g-point)
  
  return min(x, dfs(d-1, g))
print(dfs(D, G))

Submission status: Accepted

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

ans = 1e9
for i in range(1 << D):
  point = 0
  cnt = 0
  for j in range(D):
    if(((i >> j) & 1) == 1):
      point += PC[j][0]*(j+1)*100 + PC[j][1]
      cnt += PC[j][0]
    else:
      tmp = j
  if(point < G):
    x = G - point
    if((PC[tmp][0]-1)*(tmp+1)*100 < x):
      continue
    cnt += -(-x//(100*(tmp+1)))
  ans = min(ans, cnt)
print(ans)

Submission status: Accepted

Solution code:
from math import ceil


def all_green(D: int, G: int, PC: int)->int:
    min_coin_num = float('inf')
    for n in range(1 << D):
        # 中途半端に解く問題の(番号, 数)
        not_used = []
        # 完全に解く問題数と、使った時の得点
        used_coin_num, total_point = 0, 0
        for i, (p, c) in enumerate(PC):
            # n = 0b10110 とすると、
            # レベル 1 問題をとかない
            # レベル 2 問題をとく
            # レベル 3 問題をとく
            # レベル 4 問題をとかない
            # レベル 5 問題をとく
            # と考える。
            if n & 1 == 1:
                # 完全に解く問題
                total_point += (100*(i+1)) * p + c
                used_coin_num += p
            else:
                # 完全にとかない問題
                not_used.append((i, p))
            n = n >> 1

        if total_point >= G:
            # 完全に解く問題だけで間に合うならそれで終わり。
            min_coin_num = min(min_coin_num, used_coin_num)
        else:
            # 完全に解く問題だけで間に合わない場合は、いづれか一種類のレベル
            # の問題を中途半端に解いて補填する。
            for i, p in not_used:
                # (中途半端に使う問題数) = ceil((残っている得点) / (注目している問題一つの得点))
                coin_num = ceil((G-total_point)/(100*(i+1)))
                if coin_num < p:
                    # コインの枚数が足りる場合のみ
                    min_coin_num = min(min_coin_num, used_coin_num+coin_num)

    return min_coin_num


if __name__ == "__main__":
    D = 0
    D, G = map(int, input().split())
    PC = [tuple(int(s) for s in input().split()) for _ in range(D)]
    ans = all_green(D, G, PC)
    print(ans)

Submission status: Accepted

Solution code:
from itertools import product
from math import ceil


def solve(string):
    d, g, *pc = map(int, string.split())
    g //= 100
    p = [_p for _p in pc[::2]]
    c = [_c // 100 for _c in pc[1::2]]
    ans = 1000
    for f in product([True, False], repeat=d):
        sums = sum([(i + 1) * _p + _c for i, (_f, _p, _c) in enumerate(zip(f, p, c)) if _f])
        counts = sum([_p for _f, _p in zip(f, p) if _f])
        if g <= sums:
            ans = min(ans, counts)
            continue

        indices = [i + 1 for i, _f in enumerate(f) if not _f]
        tmp = ceil((g - sums) / indices[-1])
        if tmp < p[indices[-1] - 1]:
            ans = min(ans, counts + tmp)
    return str(ans)


if __name__ == '__main__':
    n, g = map(int, input().split())
    print(solve('{} {}\n'.format(n, g) + '\n'.join([input() for _ in range(n)])))

Submission status: Accepted

Solution code:
from itertools import product


def solve(string):
    d, g, *pc = map(int, string.split())
    g //= 100
    p = [_p for _p in pc[::2]]
    c = [_c // 100 for _c in pc[1::2]]
    ans = 1000
    for f in product([True, False], repeat=d):
        sums = sum([(i + 1) * _p + _c for i, (_f, _p, _c) in enumerate(zip(f, p, c)) if _f])
        counts = sum([_p for _f, _p in zip(f, p) if _f])
        if g <= sums:
            ans = min(ans, counts)
            continue
        indices = [i + 1 for i, _f in enumerate(f) if not _f]
        for i in range(1, p[indices[-1]-1]):
            if sums + indices[-1] * i >= g:
                ans = min(ans, counts + i)
                break
    return str(ans)


if __name__ == '__main__':
    n, g = map(int, input().split())
    print(solve('{} {}\n'.format(n, g) + '\n'.join([input() for _ in range(n)])))

Submission status: Accepted

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

def dfs(s):
    if len(s) == D:
        ans = 1000
        score = 0
        times = 0
        for i in range(D):
            if s[i] == "1":
                score += 100 * (i+1) * p[i] + c[i]
                times += p[i]
        if score >= G:
            ans = min(ans, times)
        else:
            idx = s.rfind("0")
            for i in range(1, p[idx]):
                if score + 100 * (idx+1) * i >= G:
                    ans = min(ans, times+i)
                    break
        return ans
    return min(dfs(s + "0"), dfs(s+ "1"))


print(dfs(""))

Submission status: Accepted

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

ans = float('inf')
for i in range(2**D):
    pnt = 0
    cnt = 0
    for j in range(D):
        if ((i >> j) % 2 == 1):
            pnt += p[j]*100*(j+1)+c[j]
            cnt += p[j]
        else:
            unsolved = j
    if pnt >= G:
        ans = min(ans,cnt)
    elif pnt + (p[unsolved]-1)*100*(unsolved+1) >= G:
        if G-pnt < 100*(unsolved+1):
            tmp = 1
        else:
            tmp = (G-pnt)//(100*(unsolved+1))
        ans = min(ans,cnt+tmp)
print(ans)

Submission status: Accepted

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

ans = 1e9
for i in range(1 << D):
  cnt = 0
  point = 0
  for j in range(D):
    if(((i >> j) & 1) == 1):
      point += pc[j][0]*100*(j+1) + pc[j][1]
      cnt += pc[j][0]
    else:
      tmp = j
  if(point < G):
    x = G - point
    if((pc[tmp][0]-1)*(tmp+1)*100 < x):
      continue
    cnt += -(-x//(100*(tmp+1)))
  ans = min(ans, cnt)
print(ans)