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 heapq import *
import sys
from collections import *

from itertools import *
from decimal import *
import copy
from bisect import *
import time

import math

def gcd(a,b):
    if(a%b==0):return(b)
    return (gcd(b,a%b))
sys.setrecursionlimit(10**7)
input=lambda :sys.stdin.readline().rstrip()
D,G=map(int,input().split())
PC=[list(map(int,input().split())) for i in range(D)]
value=10**18
for i in range(2**D):
    count=0
    score=G
    bit=[i>>m&1 for m in range(D)]
    for d in range(D):
        p,c=PC[d]
        if bit[d]:
            count+=p
            score-=c+p*(d+1)*100
    for d in range(D)[::-1]:
        p,c=PC[d]
        if not bit[d] and score>0:
            _p=min(p,score//((d+1)*100)+bool(score%((d+1)*100))*1)
            count+=_p
            score-=c+_p*(d+1)*100
    value=min(value,count)
print(value)

Submission status: Accepted

Solution code:
def main():
    D, G = map(int, input().split())
    info = [tuple(map(int, input().split())) for _ in range(D)]

    ans = 100 * 10
    for bit in range(1<<D):
        score = 0
        num_problem = 0

        # complete bonus
        for i in range(D):
            if (bit>>i) & 1:
                base = 100 * (i+1)
                score += base * info[i][0] + info[i][1]
                num_problem += info[i][0]
        
        # other
        if score >= G:
            ans = min(ans, num_problem)
        else:
            for i in range(D-1, -1, -1):
                if not((bit>>i) & 1):
                    rest = G - score
                    base = 100 * (i+1)
                    need = (rest + base -1) // base
                    if need <= info[i][0] - 1:
                        num_problem += need
                        score += base * need
                        ans = min(ans, num_problem)
                    break

    print(ans)


if __name__ == "__main__":
    main()

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 = []
K = 2 #選択肢の数
N = D #問題の個数
for i in range(K**N):
    TF=[0]*N

    for j in range(N):
        TF[N-j-1] = i % K
        i //= K

    sc = 0
    for j in range(D):
        sc += (100*(j+1)*p[j] + c[j]) *TF[j]

    m = 0
    for j in range(D):
        m += p[j] *TF[j]
    
    g = G-sc
    if g <= 0:
        ans.append(m)
    else:
        for j in range(D)[::-1]:
            if TF[j] == 0:
                break
        for _ in range(p[j]):
            g -= 100*(j+1)
            m += 1
            if g <= 0:
                break
        else:
            m = 100000
        
        ans.append(m)
    
print(min(ans))

Submission status: Accepted

Solution code:
def main():
    D, G = map(int, input().split())
    info = [tuple(map(int, input().split())) for _ in range(D)]

    ans = 100 * 10
    for bit in range(1<<D):
        score = 0
        num_problem = 0

        # complete bonus
        for i in range(D):
            if (bit>>i) & 1:
                base = 100 * (i+1)
                score += base * info[i][0] + info[i][1]
                num_problem += info[i][0]
        # other 
        for i in range(D-1, -1, -1):
            if score >= G:
                break
            
            if not((bit>>i) & 1):
                base = 100 * (i+1)
                rest = G - score
                need = (rest + base - 1) // base

                if need > info[i][0] - 1:
                    score += base * (info[i][0] - 1)
                    num_problem += (info[i][0] - 1)
                else:
                    score += base * need
                    num_problem += need
                    break
        
        if score >= G:
            ans = min(ans, num_problem)

    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

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

point=[0]*2**D
num=[0]*2**D

for i in range(2**D):
    b=bin(i)[2:].zfill(D)
    for j in range(D):
        num[i]+=int(b[D-j-1])*p[j]
        point[i]+=int(b[D-j-1])*(100*(j+1)*p[j]+c[j])
        if b[D-j-1]=="0":
            rest=j #足りない時は100(rest+1)点の問題を解く
    k=0
    while point[i]<G and k<p[rest]:
#        print(k,point[i])
        point[i]+=100*(rest+1)
        num[i]+=1
        k+=1
    if point[i]<G:
        num[i]+=1000
#    print(b,rest,point[i],num[i])
print(min(num))

Submission status: Accepted

Solution code:

from math import ceil
INF = 10 ** 10

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

minimumsolve = INF

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

print(minimumsolve)

Submission status: Accepted

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

ans=float('inf')

for bit in range(1<<d):
  count=0
  sum=0
  nokori=set(range(1,d+1))
  
  for i in range(d):
    if bit&(1<<i):
      sum+=pc[i][0]*(i+1)*100+pc[i][1]
      count+=pc[i][0]
      nokori.discard(i+1)
      
  if sum<g:
    use=max(nokori)
    n=min(pc[use-1][0], -(-(g-sum)//(use*100)))
    count+=n
    sum+=n*use*100
    
  if sum>=g:
    ans=(min(ans,count))

print(ans)

Submission status: Accepted

Solution code:
import math, sys
from bisect import bisect_left, bisect_right
from collections import Counter, defaultdict, deque
from copy import deepcopy
from functools import lru_cache
from heapq import heapify, heappop, heappush
from itertools import accumulate, combinations, permutations
input = sys.stdin.readline
mod = 10**9 + 7
ns = lambda: input().strip()
ni = lambda: int(input().strip())
nm = lambda: map(int, input().split())
nl = lambda: list(map(int, input().split()))

d, g = nm()
pc = [nl() for _ in range(d)]
costs = []
for i in range(2**d):
    binary = '0'*(d-len(bin(i)[2:])) + bin(i)[2:]
    #print(binary)
    point = 0
    num = 0
    remain = [100 * len(pc), 0]
    for j, digit in enumerate(binary):
        if digit == '1':
            point += 100 * (j + 1) * pc[j][0] + pc[j][1]
            num += pc[j][0]
        if digit == '0':
            remain = [100 * (j + 1), pc[j][0]]
    if point < g:
        num += math.ceil(min((g - point) / remain[0], remain[1]))
        point = point + min(g - point, remain[0] * remain[1])
    costs.append([point, num, binary])
    #print(binary, [point, num], remain)
costs.sort(key=lambda x: (x[1], x[0]))
#print(costs)
for value in costs:
    if value[0] >= g:
        print(value[1])
        exit()

Submission status: Accepted

Solution code:
import sys

n, g, *pc = map(int, sys.stdin.read().split())
p, c = pc[::2], pc[1::2]
s = [100 * (i + 1) for i in range(n)]

def main():
    res = float('inf')
    for i in range(1 << n):
        tot = 0
        cnt = 0
        for j in range(n):
            if i >> j & 1:
                cnt += p[j]
                tot += s[j] * p[j] + c[j]
            else:
                k = j
        if tot >= g: res = min(res, cnt); continue
        d = (g - tot + s[k] - 1) // s[k]
        if d < p[k]: res = min(res, cnt + d)
    print(res)

if __name__ ==  '__main__':
    main()

Submission status: Accepted

Solution code:
import sys

n, g, *pc = map(int, sys.stdin.read().split())
p, c = pc[::2], pc[1::2]

def main():
    res = float('inf')
    for i in range(1 << n):
        tot = 0
        cnt = 0
        for j in range(n):
            if i >> j & 1:
                cnt += p[j]
                tot += 100 * (j + 1) * p[j] + c[j]
            else:
                k = j
        if tot >= g: res = min(res, cnt); continue
        d = (g - tot + 100 * (k + 1) - 1) // (100 * (k + 1))
        if d < p[k]: res = min(res, cnt + d)
    print(res)

if __name__ ==  '__main__':
    main()

Submission status: Accepted

Solution code:
#from statistics import median
#import collections
#aa = collections.Counter(a) # list to list
#from itertools import combinations # (string,3) 3回

mod = 10**9 + 7

def readInts():
  return list(map(int,input().split()))
d,g = readInts()
cl = [readInts() for _ in range(d)]
ans = float("inf")
def dfs(i,sum,count,nokori):
    global ans
    #まだ解いてない配点をnokori
    if i == d:
        # G点に満たなければ nokoriのうち1番大きい物を解く
        if sum < g:
            use = max(nokori)
            # 解く問題が問題数を超えないように注意
            n = min(cl[use - 1][0], -(-(g-sum) // (use * 100)))
            count += n
            sum += n * use * 100
        if sum >= g:
            ans = min(ans,count)
    else:
        dfs(i + 1, sum, count, nokori)
        #print(i+1,nokori,nokori - {i+1})
        dfs(i + 1, sum + cl[i][0] * (i + 1) * 100 + cl[i][1], count + cl[i][0], nokori - {i + 1})

def main():


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




if __name__ == '__main__':
  main()

Submission status: Accepted

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

def ans(a,b):
  if a==0:
    return 10**9
  n = min(b//(a*100), Q[a][0])
  score = a*100*n
  if n == Q[a][0]:
    score += Q[a][1]
  if score < b:
    n += ans(a-1, b-score)
  n = min(n, ans(a-1,b))
  return(n)

print(ans(D,G))

Submission status: Accepted

Solution code:
_lst = input().split()
d = int(_lst[0])
g = int(_lst[1])

pc = list()

for i in range(d):
    _lst = input().split()
    pc.append((int(_lst[0]), int(_lst[1])))

score = 0
result_count = -1

# 全て回答したパターンを探索する
for i in range(2 ** d):
    count = 0
    score = 0

    # 全問正解した配点のスコアを足す
    for j in range(d):
        if i >> j & 1:
            score += 100 * (j + 1) * pc[j][0] + pc[j][1]
            count += pc[j][0]

    # すでに配点を超えている場合は、最小のcountだけ考慮して処理終了
    if score >= g:
        if result_count >= count or result_count == -1:
            result_count = count
        continue

    not_reach = True
    for j in range(d-1, -1, -1):
        if not (i >> j & 1):  # 全問正解していない配点(一番大きい0)のindexを特定
            if -((score - g) // ((j + 1) * 100)) < pc[j][0]:  # 配点が全問正解しないでも目標値を超えるか確認
                count -= (score - g) // ((j + 1) * 100)  # 全問正解していない配点の正解数
                not_reach = False
                break

    # gに届かなかった場合は考慮しない
    if not_reach:
        continue

    if result_count >= count or result_count == -1:
        result_count = count

print(result_count)

Submission status: Accepted

Solution code:
d, g = map(int, input().split(' '))
p = []
c = []
for _ in range(d):
    p_, c_ = map(int, input().split(' '))
    p.append(p_)
    c.append(c_)
 
sum_p = []
for i in range(d):
    sum_p.append((i + 1) * 100 * p[i] + c[i])
 
def ans(g, t):
    if t <= 0:
        return float('inf')
    n = min(int(g / (100 * t)), p[t-1])
    s = 100 * t * n
 
    if n == p[t-1]:
        s = sum_p[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 math

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

digit = "0"+str(D)+"b"
ans = float('INF')
for i in range(2**D):
    flags = list(str(format(i,digit)))
    point = 0
    count = 0
    last0 = -1
    for j in range(D):
        if flags[j] == "1":
            point += pc[j][0]*100*(j+1) + pc[j][1]
            count += pc[j][0]
        else:
            last0 = j
    if point >= G:
        ans = min(ans,count)
    else:
        if last0 != -1:
            r = G - point
            if math.ceil(r/(100*(last0+1))) < pc[last0][0]:
                count += math.ceil(r/(100*(last0+1)))
                ans = min(ans,count)

print(ans)

Submission status: Accepted

Solution code:
def dfs(i, sum, count, nokori):
    global ans
    if i == d:
        # G 点に満たなければ nokori のうち一番大きいものを解く
        if sum < g:
            use = max(nokori)
            # 解く問題が問題数を超えないように注意
            n = min(pc[use - 1][0], -(-(g - sum) // (use * 100)))
            count += n
            sum += n * use * 100

        if sum >= g:
            ans = min(ans, count)
    else:
        # 総合スコア、解いた問題数、まだ解いてない問題を更新
        dfs(i + 1, sum, count, nokori)
        dfs(i + 1, sum + pc[i][0] * (i + 1) * 100 + pc[i][1], count + pc[i][0], nokori - {i + 1})


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

ans = float("inf")

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

Submission status: Accepted

Solution code:
from sys import stdin

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

def calculate_score(arr): #arrは100i点の問題を解いた数の配列, 長さはD
    tot_score = 0
    for i in range(len(arr)):
        num = arr[i]
        tot_score += num * 100*(i+1)
        if num == data[i][0]:
            tot_score += data[i][1]
    return tot_score

def func1(arr,G): #arrは長さDの配列で、それぞれi点問題のボーナスを得るかどうか
    #arrだけのボーナスを得たときに、総合スコアをG点にするための問題数は容易に求められる

    problem_num = 0
    tot_score = 0
    for i in range(len(arr)):
        if arr[i] == 1:
            tot_score += data[i][1]
            tot_score += data[i][0]*100*(1+i)
            problem_num += data[i][0]
    
    if tot_score>=G:
        return problem_num

    for i in range(len(arr)):
        if arr[len(arr)-i-1]==0:
            for j in range(data[len(arr)-i-1][0]-1):
                tot_score += 100*(len(arr)-i)
                problem_num+=1
                if tot_score>=G:
                    return problem_num
    
    return 100000

min_problem = 10000
for i in range(2**D):
    i_bin = bin(i)
    i_bin_arr = []
    for j in range(D-len(i_bin[2:])):
        i_bin_arr.append(0)

    for j in range(len(i_bin[2:])):
        i_bin_arr.append(int(i_bin[2+j]))

    problem_num = func1(i_bin_arr,G)
    if problem_num<min_problem:
        min_problem=problem_num

print(min_problem)

Submission status: Accepted

Solution code:
def dfs(i,f):
    #print(i,f,check)
    global min
    if i==d:
        if f >= g:
            ans = 0
            for j in range(d):
                if check[j]==1 :
                    ans += p[j]
            if ans<min:
                min=ans
                return
        else:
            l=0
            max=0
            for j in range(d):
                if check[j]==0:
                    l=j
                    max=100*(j+1)
            for j in range(p[l]):
                if j == p[l]-1:
                    return
                sum = f + max*(j+1)
                if sum >= g:
                    ans=0
                    for j1 in range(d):
                        if check[j1]==1 :
                            ans += p[j1]
                    ans += j+1
                    if ans<min:
                        min=ans
                        return
    else:
        check[i]=1
        dfs(i+1,f+s[i])
        check[i]=0
        dfs(i+1,f)

d,g=map(int,input().split())
p=[0]*d
c=[0]*d
s=[0]*d
check=[0]*d
min=1000
for i in range(d):
    p[i],c[i]=map(int,input().split())
    s[i]=100*(i+1)*p[i]+c[i]
dfs(0,0)
print(min)

Submission status: Accepted

Solution code:
import sys
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
read = sys.stdin.buffer.read
sys.setrecursionlimit(10 ** 7)

D, G = map(int, readline().split())
problems = []
for i in range(1, D+1):
    p, c = map(int, readline().split())
    score = 100 * i
    problems.append({
        "score": score,
        "number": p,
        "bonus": c,
        "sum": score * p + c
    })

keta = len(problems)
answer = float("inf")
for i in range(0, 2 ** D):
    bits = list(str(format(i, "0{}b".format(keta))))
    sum_number = 0
    sum_score = 0
    half_index = None
    for j, is_full in enumerate(bits):
        if is_full == "1":
            sum_number += problems[j]["number"]
            sum_score += problems[j]["sum"]
        else:
            half_index = j
    if half_index is None:
        if sum_score >= G:
            answer = min(answer, sum_number)
        continue
    for _ in range(problems[half_index]["number"]):
        if sum_score >= G:
            break
        sum_score += problems[half_index]["score"]
        sum_number += 1
    if sum_score >= G:
        answer = min(answer, sum_number)

print(answer)

Submission status: Accepted

Solution code:
D,G=map(int,input().split())
 
pc=[list(map(int,input().split())) for i in range(D)]
 
ans=float('inf')
 
for i in range(1<<D):
    s=0
    c=0
    for k in range(D):
        if 1&i>>k:
            s+=(k+1)*100*pc[k][0]+pc[k][1]
            c+=pc[k][0]
 
    if s>=G:
        ans=min(ans,c)
 
    if s<G:
        for k in reversed(range(D)):
            if not(1&i>>k):
                ac=-(-(G-s)//((k+1)*100))
                if  pc[k][0]>ac:
                    ans=min(ans,c+ac)
                    break
print(ans)

Submission status: Accepted

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

def condition(num):
    for i in range(0,2**D):
        complete=set([])
        score=0
        solve=0
        for j in range(0,D):
            if i>>j &1 ==1:
                complete.add(j)
                score+=compscore[j]+100*(j+1)*problem[j]
                solve+=problem[j]

        if solve>num:
            continue
        else:
            x=num-solve
            full=set([i for i in range(0,D)])
            nokori=full-complete
            nokori=list(nokori)
            if not nokori:
                return score>=G
            else:
                m=max(nokori)
                if x>=problem[m]:
                    continue
                else:
                    score+=x*100*(m+1)
                    if score>=G:
                        return True

    return False

start=1
end=sum(problem)
while end-start>1:
    test=(end+start)//2
    if condition(test):
        end=test
    else:
        start=test

if condition(start):
    print(start)
else:
    print(end)

Submission status: Accepted

Solution code:
D,G = map(int, input().split())
li=[]
for i in range(D):
    li.append(list(map(lambda x: int(x), input().split())))
def bit():
    ans=10000040000
    for i in range(2 **D):
        #問題数n　得点p
        n=0
        p=0
        for j in range(D):
            if ((i >> j) & 1):
                n += li[j][0]
                p += li[j][1] 
                p += li[j][0] *100*(j+1)
        
        if p >= G:
            if n <= ans:
                ans=n
        
        for j in reversed(list(range(D))):
            if ((i >> j) & 1):
                continue
            else:
                for k in range(li[j][0]):
                    if p < G:
                        n += 1
                        p += 100*(j+1)
                    else:
                        if n <= ans:
                            ans=n
                            break
    print(ans)

bit()

Submission status: Accepted

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

def bit():
    ans=10000040000
    for i in range(2 **D):
        #問題数n　得点p
        n=0
        p=0
        for j in range(D):
            if ((i >> j) & 1):
                n += li[j][0]
                p += li[j][1] 
                p += li[j][0] *100*(j+1)
        
        if p >= G:
            if n <= ans:
                ans=n
        
        for j in reversed(list(range(D))):
            if ((i >> j) & 1):
                continue
            else:
                for k in range(li[j][0]):
                    if p < G:
                        n += 1
                        p += 100*(j+1)
                    else:
                        if n <= ans:
                            ans=n
                            break
    print(ans)

bit()

Submission status: Accepted

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

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

ans=float('inf')

for i in range(1<<D):
    s=0
    c=0
    for k in range(D):
        if 1&i>>k:
            s+=(k+1)*100*pc[k][0]+pc[k][1]
            c+=pc[k][0]

    if s>=G:
        ans=min(ans,c)

    if s<G:
        for k in reversed(range(D)):
            if not(1&i>>k):
                ac=-(-(G-s)//((k+1)*100))
                if  pc[k][0]>ac:
                    ans=min(ans,c+ac)
                    break
print(ans)

Submission status: Accepted

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

ans = float('inf')

for bit in range(1<<d):
  sum = 0
  cnt = 0
  rem = set(range(d))
  for i in range(d):
    if bit & 1<<i:
      sum += pc[i][0]*(i+1)*100 + pc[i][1]
      cnt += pc[i][0]
      rem.discard(i)
    
  if sum < g:
    u = max(rem)
    n = min(pc[u][0],  -( -(g-sum)//((u+1)*100) ))
    cnt += n
    sum += n*(u+1)*100
    
  if sum >= g:
    ans = min(ans, cnt)
    

print(ans)

Submission status: Accepted

Solution code:
import math
D, G = map(int, input().split())
P, C = [], []
for _ in range(D):
    p, c = map(int, input().split())
    P.append(p)
    C.append(c)

ans = float('inf')
for i in range(2**D):
    score = 0
    cnt = 0
    max_zero = 0
    # print(bin(i))
    # b = bin(i)[2:][::-1]
    # print(b)
    # for j, c in enumerate(b):
    for j in range(D):
        x = (i >> j) & 1
        # x = int(c)
        if x == 1:
            cnt += P[j]
            score += 100 * (j + 1) * P[j] + C[j]
        else:
            max_zero = j
    if G <= score:
        ans = min(ans, cnt)
    else:
        diff = G - score
        base = 100 * (max_zero + 1)
        if P[max_zero] <= math.ceil(diff / base):
            continue
        else:
            cnt += math.ceil(diff / base)
            ans = min(ans, cnt)
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())

def count(bit):
    cnt = 0
    point = 0
    i = 0
    comp = [False]*D
    while bit > 0:
        if bit&1:
            cnt += P[i]
            point += P[i]*100*(i+1) + C[i]
            comp[i] = True
        i += 1
        bit = bit >> 1
    if point >= G:return cnt
    for i in range(D-1,-1,-1):
        if comp[i]:continue
        if point + 100*(i+1)*(P[i]-1) < G:
            cnt += P[i] - 1
            point += 100*(i+1)*(P[i]-1)
        else:
            cnt += (G-point-1)//(100*(i+1)) + 1
            return cnt
    return 1e100

ans = 1e100
for i in range(2**D):
    # i:下からj桁目は100j問題でc-bonusを取るか
    ans = min(ans, count(i))
print(ans)

Submission status: Accepted

Solution code:
import math

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

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

digit = "0"+str(D)+"b"
ans = float("INF")
for i in range(2**D):
    flags = list(str(format(i,digit)))
    points = 0
    count = 0
    last0 = -1
    for j in range(D):
        if flags[j]=="1":
            points += pc[j][0]*100*(j+1) + pc[j][1]
            count += pc[j][0]
        else:
            last0 = j
    r = G - points
    if r<=0:
        ans = min(ans,count)
    else:
        if last0 == -1:
            continue
        need = math.ceil(r/(100*(last0+1)))
        if need >= pc[last0][0]:
            continue
        else:
            count += need
            ans = min(ans,count)

print(ans)

Submission status: Accepted

Solution code:
import copy
D,G = map(int, input().split())
m = [0]*D
for i in range(D):
    m[i] = list(map(int,input().split()))
score = 0
count = 0
ans = 0

for i in range(1 << D):
    l = copy.deepcopy(m)
    score = 0
    count = 0
    for j in range(D):
        if i >> j & 1 == 1:
            score += l[j][1] + l[j][0]*(j+1)*100
            count += l[j][0]
            l[j][0] = 0
    k = D-1
    while score < G:
        if l[k][0] > 1:
            l[k][0] -= 1
            score += 100*(k+1)
            count += 1
        else:
            k -= 1
            if k < 0:
                break
    if score >= G:
        if ans > count or ans == 0:
            ans = count

print(ans)

Submission status: Accepted

Solution code:
import math

def main():
    D, G = map(int, input().split())

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

    ans = 100**10
    for i in range(1<<D):
        score = 0
        prob = 0
        last = -1
        for j in range(D):
            p, c = pc[j]
            if i & (1<<j):
                score += (j+1)*100*p + c
                prob += p
            else:
                last = j
        if score >= G:
            ans = min(ans, prob)
            continue
        elif last == -1:
            continue
        else:
            need = math.ceil((G-score)/((last+1)*100))
            if need > pc[last][0]-1:
                continue
            else:
                ans = min(ans, prob+need)
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

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

def bitlist(n):
  res = []
  for i in range(2**n):
    pattern = []
    for j in range(n):
      if (i >> j) & 1:
        pattern.insert(0, True)
      else:
        pattern.insert(0, False)
    res.append(pattern)
  return res

res = 10000
pattern = bitlist(d)
for i in range(2**d):
  point = 0
  solve = 0
  for j in range(d):
    if pattern[i][j]:
      point += lst[j][0]*(j+1)*100 + lst[j][1]
      solve += lst[j][0]
  if point >= g:
    res = min(res, solve)
  else:
    yet = 0
    for k in range(d):
      if not pattern[i][k]:
        yet = k
    for l in range(lst[yet][0]-1):
      point += (yet+1)*100
      solve += 1
      if point >= g:
        res = min(res, solve)
        break
print(res)

Submission status: Accepted

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

def fnc(a,b):#点の大きいものから解いていく
    if a==0:#全部試したらおわり
        return 10**9
    s=min(l[a][0],b//(a*100))#全部か部分か
    t=100*a*s#基本スコア
    if s==l[a][0]:
        t+=l[a][1]#ボーナス
    if t<b:#達してないなら
        s+=fnc(a-1,b-t)#次の問題
    return(min(s,fnc(a-1,b)))#a-1問目から解く
print(fnc(d,g))

Submission status: Accepted

Solution code:
d,g = map(int,input().split())
l = list(list(map(int,input().split())) for i in range(d))
ans = 10**7


for bit in range(1<<d):
  count = 0
  sum =0
  nokori = set(range(1,d+1))
  
  for j in range(d):
    if bit&(1<<j):
      count += l[d-j-1][0]
      sum += l[d-j-1][0]*100*(d-j)+l[d-j-1][1]
      nokori.discard(d-j)
      
      
  if sum<g:
    use = max(nokori)
    n = min(l[use-1][0]-1,-(-(g-sum)//(100*use)))
    count += n
    sum += 100*(use)*n
     
  if sum>=g:
    ans = min(ans,count)
  
print(ans)

Submission status: Accepted

Solution code:
import  itertools
d,g=map(int,input().split())
p=[]
c=[]
for i in range(d):
    x,y=map(int,input().split())
    p.append(x)
    c.append(y)
ans=float('inf')
def judge(tmp):
    ss=g
    count=0
    for i in range(d):
        if tmp[i]==1:
            ss-=((i+1)*p[i]*100+c[i])
            count+=p[i]
    if ss<=0:
        return count
    else:
        for i in range(d-1,-1,-1):
            if tmp[i]==0:
                if ss%((i+1)*100)==0:
                    fgh=ss//((i+1)*100)
                else:
                    fgh=1+ss//((i+1)*100)
                if fgh>=p[i]:
                    count+=float('inf')
                else:
                    count+=fgh
                ss -= fgh * ((i + 1) * 100)
            if ss<=0:
                return count
        return count+float('inf')
nums=[0,1]
for sd in itertools.product(nums,repeat=d):
    pat=list(sd)
    sdf=judge(pat)
    ans=min(ans,sdf)
print(ans)