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

ans = 10 ** 9
for i in range(2**d):
  ch = bin(i)[2:]
  ch = ch.zfill(d)
  tmpsum = 0
  cnt = 0
  for j in range(d):
    if ch[j] == "1":
      tmpsum += li[j][0]*100*(j+1) + li[j][1]
      cnt += li[j][0]
  if tmpsum >= g:
    ans = min(ans,cnt)
    #print("{} {}".format(bin(i),cnt))
  else:
    ind = ch.rfind("0")
    if tmpsum + (li[ind][0]-1)*100*(ind+1) >= g:
      ans = min(ans,cnt+(g-tmpsum-1)//(100*(ind+1))+1)
      #print("{} {} {}".format(bin(i),cnt,ans))
print(ans)

Submission status: Accepted

Solution code:
d,g = list(map(int,input().split()))
lis = []
for i in range(d):
    lis.append(list(map(int,input().split())))
ans = 10000000
for bit in range(2**d):
    price = 0
    count = 0
    use = [0]* d
    for j in range(d):
        if (bit >> j) & 1:
            use[d-1-j] = 1
    for i in range(d):
        if use[i] == 1:
            if price < g:
                price += (i+1)*100*lis[i][0] + lis[i][1]
                count += lis[i][0]
    if price < g:

        for k in reversed(range(d)):
            if use[k] == 0:
                for m in range(lis[k][0]):
                    if price < g:
                        price += (k+1)*100
                        count += 1

    if count < ans:
        ans = count

print(ans)

Submission status: Accepted

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

ans = 10 ** 7
for i in range(2 ** D):
    bit = format(i, 'b').zfill(D)
    count = 0
    score = 0
    # ボーナスの分を加算
    for index in range(len(bit)):
        if bit[index] == '1':
            score += 100 * (index + 1) * inputs[index][0] + inputs[index][1]
            count += inputs[index][0]
    if G <= score:
        ans = min(ans, count)
        continue
    
    for j in range(len(bit)-1, -1, -1):
        if bit[j] == '0':
            if G - score <= 100 * (j + 1) * (inputs[j][0] - 1):
                count += (G - score) // (100 * (j + 1)) + (1 if (G - score) % (100 * (j + 1)) != 0 else 0)
                ans = min(ans, count)
                break
            else:
                score += 100 * (j + 1) * (inputs[j][0] - 1)
                count += inputs[j][0] - 1

print(ans)

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)

S = []
for i in range(2**D):
    S.append(list(str(bin(i+2**D)))[3:])

ans = 10000
for l in S:
    total = 0
    cnt = 0
    for i, s in enumerate(l):
        if s == "1":
            total += 100 * (i + 1) * P[i] + C[i]
            cnt += P[i]
    if total >= G:
        if cnt < ans:
            ans = cnt

    i = D-1
    while i >= 0:
        if l[i] == "0":
            break
        i -= 1
    if i != -1:
        for j in range(1, P[i]):
            if total + 100 * (i + 1) * j >= G:
                if cnt+j < ans:
                    ans = cnt+j
                    break
print(ans)

Submission status: Accepted

Solution code:
import sys
import math
d,g=map(int,input().split())
p=[]
c=[]
s=[]
count=0
for i in range(d):
    pi,ci=map(int,input().split())
    p.append(pi)
    c.append(ci)
    s.append((i+1)*100*pi+ci)

l=2**d
count=10**6*d
for i in range(l):
    buf=g
    x=0
    n=0
    for j in range(d):
        if i & 1 ==1:
            x+=p[j]
            buf-=s[j]
        else:
            n=j
        i=i>>1
    if buf>=0:
        y=math.ceil(buf/((n+1)*100))
        if y>p[n]:
            continue
        x=x+y
    count=min(count,x)
print(count)

Submission status: Accepted

Solution code:
import numpy as np
row = list(map(int, input().split()))
row2 = [input().split() for i in range(row[0])]
f = np.vectorize(int)
p = f(row2)
ans = 10*100
for bit in range(1<<row[0]):
    sum = 0
    max_rest = 0
    num = 0
    for i in range(row[0]):
        if bit & (1<<i):
            
            sum += 100*(i+1) * p[i][0] + p[i][1]
            num += p[i][0]
        else:
            max_rest = i
    for j in range(p[max_rest][0]):
        if sum < row[1]:
            sum += 100*(max_rest+1)
            num += 1
        else:
            if num < ans:
                ans = num
            break
    
print(ans)

Submission status: Accepted

Solution code:
import sys


q_size, g_score = map(int, input().split())
q_nums = [0] * q_size
bonus = [0] * q_size
for i in range(0, q_size):
    q_nums[i], bonus[i] = map(int, input().split())


def solve_q(score, q_cnt, q_solved, best_cnt):
    # ボーナスだけでGを突破していたら、そのまま返却する
    if score >= g_score: 
        return min(best_cnt, q_cnt)
    
    # 現状でどの問題が何問残っているかキャッシュし、配点の高い問題から先に解いていく
    q_remained = [0] * q_size
    for i in range(0, q_size):
        q_remained[i] = q_nums[i] - q_solved[i]
        
    for i in range(q_size - 1, -1, -1):
        while q_remained[i] > 0: # Gに達成するまで、あるだけ全部解く
#            print("while in score: ", score)
            score += 100 * (i + 1)
            q_cnt += 1
            q_remained[i] -= 1
            
            if score >= g_score:
                return min(best_cnt, q_cnt)
            
    # ボーナス未反映で、解なしの場合
    return min(best_cnt, q_cnt)

            
best_cnt = sum(q_nums)
# 各Qのボーナスを 使う or 使わない で分岐
for bi in range(0, 2 ** q_size):
    # 初期化
    score = 0
    q_cnt = 0
    q_solved = [0]*q_size

    for pos_i in range(0, q_size):
        if (bi >> pos_i) & 1: # True: ボーナスを使う
            score += 100 * (pos_i + 1) * q_nums[pos_i] + bonus[pos_i]
            q_cnt += q_nums[pos_i]
            q_solved[pos_i] += q_nums[pos_i]
            
    # スコアを引き継いで、得点の高い問題から解いていく
#    print(score, q_cnt, q_solved, best_cnt)
    best_cnt = solve_q(score, q_cnt, q_solved, best_cnt)
    

print(best_cnt)

Submission status: Accepted

Solution code:
import math
a,b=map(int,input().split())
c=[list(map(int,input().split())) for i in range(a)]
d=[0 for i in range(a)]
for i in range(a):
  d[i]=(c[i][0]*(i+1)*100+c[i][1])
e=[0 for i in range(a)]
f=100000000
def s(e,d,c,i):
  g=0
  h=0
  e[i]=c[i][0]
  for j in range(a):
    if e[j]!=0:
      g+=d[j]
    if e[j]==0:
      h=j
  gh=c[h][0]
  global b
  global f
  if b<=g:
    f=min(f,sum(e))
  elif b<=g+(h+1)*100*(gh-1):
    hh=math.ceil((b-g)/((h+1)*100))
    f=min(f,sum(e)+hh)
  if i!=a-1:
    s(e,d,c,i+1)
  g=0
  h=0
  e[i]=0
  for j in range(a):
    if e[j]!=0:
      g+=d[j]
    if e[j]==0:
      h=j
  gh=c[h][0]
  global b
  global f
  if b<=g:
    f=min(f,sum(e))
  elif b<=g+(h+1)*100*(gh-1):
    hh=math.ceil((b-g)/((h+1)*100))
    f=min(f,sum(e)+hh)
  if i==a-1:
    return
  else:
    s(e,d,c,i+1)

s(e,d,c,0)
print(f)

Submission status: Accepted

Solution code:
# G点を超えるために解く問題数の最小値
# 配点の大きいi=Dの問題から点数を加算していき、Gを超えた時点での解答数を出せばよさそう
# と思ったがコンプリートボーナスがあるからそう単純でない。

# 制約から全探索するとO(2***1000)かかるため、これは無理
# i番目の問題をx(i)個解くと考えると、x(i)の全探索はO(100)
# これをすべてのiについて考えるとO(1000)

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


# ボーナスの取り方（2**10 = 10**3）を全探索 → ボーナスが固定される
ans = float("inf")
for bit in range(0, 1<<D):
    s = 0
    num = [0 for _ in range(D)]  # i番目の問題を何個解いたか
    for i in range(D):
        if (bit>>i) & 1:
            num[i] += P[i]
            s += 100*(i+1)*P[i] + C[i]
    # 足りない場合は残ってる問題で100iの値が大きい順に解いていく
    if s < G:
        for i in reversed(range(D)):
            if not (bit>>i) & 1:
                while num[i] < P[i]-1:
                    s += 100*(i+1)
                    num[i] += 1
                    if s >= G:
                        ans = min(ans, sum(num))
                        break
                break
    else:
        ans = min(ans, sum(num))

print(ans)

Submission status: Accepted

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

for i in range(D):
    b = [[List[i][0], List[i][0]*(i+1)*100+List[i][1]] for i in range(D)]
    
m = 10**9
for j in range(2**D):
    cnt = 0
    score = 0
    flg = 0
    for k in range(D):
        if ((j>>k)&1):
            cnt+=b[k][0]
            score+=b[k][1]
            flg+=1
            used = k
        else:
            unused = k
    if G<=score:
        if flg==1:
            cnt = min(-(-G//((used+1)*100)), cnt)
            if cnt<m:
                m = cnt
        else:
            if cnt<m:
                m = cnt
                
    else: 
        diff = G-score
        offset = -(-diff//((unused+1)*100))
        cnt += offset
        if offset<List[unused][0]:
            if cnt<m:
                m = cnt
print(m)

Submission status: Accepted

Solution code:
def resolve():

    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 = 1010

    for i in range(2 ** d):

        sum = 0
        cnt = 0

        for j in range(d):

            if (i >> (d-1-j)) & 1:
                sum += p[j] * (j+1) * 100
                sum += c[j]
                cnt += p[j]

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

        else:

            for j in range(d)[::-1]:

                if not (i >> (d-1-j)) & 1:
                    additional = -(-(g-sum) // ((j+1)*100))

                    if additional >= p[j]:
                        continue

                    cnt += additional
                    sum += additional * (j+1) * 100
                    break

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

    print(ans)
    
resolve()

Submission status: Accepted

Solution code:
# ABC104 C-All Green

D, G = map(int, input().split())
pc = []
for _ in range(D):
    pc.append(list(map(int, input().split())))
    
ans = 10**10
for i in range(1 << D):
    c = 0
    p = 0
    l = [] # lを初期化
    for j in range(D):
        if ((i >> j) & 1) == 1: # bit演算
            c += pc[j][0] # 問題数をメモ
            p += (j+1)*100*pc[j][0] + pc[j][1] # ここまで獲得した特典TKO\
            l.append(j) # 利用したjをメモ
    ma = 0
    for ii in range(D-1, -1, -1): # もっとも得点の高い問題を選択
        if ii not in l:
            ma = ii
            break
    for k in range(pc[ma][0]):
        if p >= G:
            break
        c += 1
        p += (ma+1)*100
    if p >= G:
        ans = min(ans, c)
        
print(ans)

Submission status: Accepted

Solution code:
n, s=map(int,input().split())
q=[list(map(int, input().split())) for i in range(n)]

import numpy as np
import itertools
import pprint

bit=[0,1]

cmp=list(itertools.product(bit, repeat=n))

cp=[0]*n
qt=[0]*n
cnt=[0]*2**n

for i in range(n):
	cp[i]=100*(i+1)*q[i][0]+q[i][1]
	qt[i]=q[i][0]

cmp_cnt=np.dot(np.array(qt),np.array(cmp).T)

for i in range(2**n):
	score=np.dot(np.array(cp),np.array(cmp[i]).T)
	cnt[i]=cmp_cnt[i]
	if score<s:
		j=n-1
		while score<s and j>=0:
			if cmp[i][j]==0:
				for k in range(qt[j]):
					score+=(j+1)*100
					cnt[i]+=1
					if score>=s:
						j=0
						break
			j-=1
                
print(min(cnt))

Submission status: Accepted

Solution code:
d, g = map(int, input().split())
s_list = [[0 for _ in range(2)] for __ in range(d)]
for i in range(d):
    s_list[i][0], s_list[i][1] = map(int, input().split())
ans = 100000
for i in range(1 << d):
    ansi = 0
    m_res = 0
    total_score = 0
    for j in range(d):
        if(i & (1 << j)):
            ansi += s_list[j][0]
            total_score += s_list[j][0]*(j+1)*100 + s_list[j][1]
        else:
            m_res = j
    if(total_score < g):
        q_s = 100*(m_res+1)
        di = g - total_score
        num = (di + q_s - 1) // q_s
        if(num > s_list[m_res][0]):
            continue
        ansi += num
    ans = min(ansi, ans)
print(ans)

Submission status: Accepted

Solution code:
d,g=map(int,input().split())
ps=[list(map(int,input().split()))for i in range(d)]
ans=9999999999
for i in range(2**d):
  s=bin(i)[2:].zfill(d)
  c=p=0
  a=[]
  for j in range(d):
    c+=ps[j][0]*int(s[j])
    p+=(ps[j][0]*(j+1)*100+ps[j][1])*int(s[j])
    if s[j]=="0":a.append(j)
  if p>=g:ans=min(ans,c)
  else:
    a.sort(reverse=1)
    while p<g:
      k=min((g-p+(a[0]+1)*100-1)//((a[0]+1)*100),ps[a[0]][0])
      p+=k*(a[0]+1)*100
      if k==ps[a[0]][0]:p+=ps[a[0]][1]
      c+=k
      del a[0]
    ans=min(ans,c)
print(ans)

Submission status: Accepted

Solution code:
from math import ceil

inf = float('inf')

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

ans = inf
for bits in range(1 << D):
    score = 0
    count = 0
    for j, (p, c) in enumerate(PCs):
        if (bits >> j) & 1:
            score += p * (j + 1) * 100 + c
            count += p
    if score < G:
        for j, (p, c) in zip(reversed(range(D)), reversed(PCs)):
            if not ((bits >> j) & 1):
                need = ceil((G - score) / ((j + 1) * 100))
                if need < p:
                    score += need * (j + 1) * 100
                    count += need
                    break

    if score >= G:
        ans = min(ans, count)
print(ans)

Submission status: Accepted

Solution code:
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)
bit_li = []
for i in range(2 ** d):
    bit = [0] * d
    for j in range(d):
        if (i >> j) & 1:
            bit[j] = 1
    bit_li.append(bit)
# bit_liは[0,0,1,1,0,...]みたいなのが要素であるリスト
ans = []
for li in bit_li:
    point = 0
    n = 0
    # 全部解くやつを加算
    for i in range(d):
        if li[i] == 1:
            point += (i + 1) * 100 * p[i] + c[i]
            n += p[i]
    flag = True
    if point >= g:  # 全部解くだけで条件満たしてたらappend
        ans.append(n)
        flag = False
    basepoint = point
    base_n = n
    # 中途半端にとくやつを加算
    for i in range(d):
        if li[i] == 0 and flag:
            for j in range(p[i] - 1):
                n += 1
                point += (i + 1) * 100
                if point >= g:
                    ans.append(n)
            point = basepoint
            n = base_n


print(min(ans))

Submission status: Accepted

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

minimum = 0

for i in range(2**d):
    score = 0
    solved = 0
    for j in range(d):
        if (i >> j) & 1 == 1:
            score += scoreMap[j][0] * 100 * (j + 1) + scoreMap[j][1]
            solved += scoreMap[j][0]
    if score < g:
        for k in range(d)[::-1]:
            if (i >> k) & 1 == 0:
                if (g - score > scoreMap[k][0] * 100 * (k + 1)):
                    score += scoreMap[k][0] * 100 * (k + 1) + scoreMap[k][1]
                    solved += scoreMap[k][0]
                    if score > g:
                        break
                else:
                    solved += (g - score) // (100 * (k + 1))
                    if (g - score) % (100 * (k + 1)) != 0:
                        solved += 1
                    score = g
                    break
    if minimum == 0 or solved < minimum:
        minimum = solved

print(minimum)

Submission status: Accepted

Solution code:
import itertools
import os
import sys

import numpy as np

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(2147483647)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7

D, G = list(map(int, sys.stdin.readline().split()))
P, C = list(zip(*[map(int, sys.stdin.readline().split()) for _ in range(D)]))

P = np.array(P, dtype=int)
C = np.array(C, dtype=int)
A = np.arange(1, D + 1, dtype=int) * 100  # 1問のスコア
comp_scores = P * A + C

# ans = P.sum()
# for i in range(D):
#     # i: 途中まで解く
#     # comp: True ならその問題は全部解く
#     for comp in itertools.product([True, False], repeat=D):
#         comp = np.array(comp)
#         comp[i] = False
#         cnt = P[comp].sum()
#         score = comp_scores[comp].sum()
#         add_cnt = max(0, min(P[i] - 1, math.ceil((G - score) / A[i])))
#         add_score = A[i] * add_cnt
#         if score + add_score >= G:
#             ans = min(ans, cnt + add_cnt)
# print(ans)


ans = P.sum()
for i in range(D):
    # i: 途中まで解く
    # True なら全部解く、False なら 1 問も説かない
    patterns = np.array(list(itertools.product([True, False], repeat=D)))
    patterns[:, i] = False
    cnt = np.dot(patterns, P)
    score = np.dot(patterns, comp_scores)
    add_cnt = np.maximum(0, np.minimum(P[i] - 1, np.ceil((G - score) / A[i])))
    add_score = A[i] * add_cnt
    ok = score + add_score >= G
    if any(ok):
        ans = min(ans, ((cnt + add_cnt)[ok]).min())
print(int(ans))

Submission status: Accepted

Solution code:
import bisect
import heapq
import itertools
import math
import os
import re
import string
import sys
from collections import Counter, deque, defaultdict
from decimal import Decimal
from fractions import gcd
from functools import lru_cache, reduce
from operator import itemgetter

import numpy as np

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(2147483647)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7

D, G = list(map(int, sys.stdin.readline().split()))
P, C = list(zip(*[map(int, sys.stdin.readline().split()) for _ in range(D)]))

P = np.array(P, dtype=int)
C = np.array(C, dtype=int)
A = np.arange(1, D + 1, dtype=int) * 100  # 1問のスコア
comp_scores = P * A + C

ans = P.sum()
for i in range(D):
    # i: 途中まで解く
    # comp: True ならその問題は全部解く
    for comp in itertools.product([True, False], repeat=D):
        comp = np.array(comp)
        comp[i] = False
        cnt = P[comp].sum()
        score = comp_scores[comp].sum()
        add_cnt = max(0, min(P[i] - 1, math.ceil((G - score) / A[i])))
        add_score = A[i] * add_cnt
        if score + add_score >= G:
            ans = min(ans, cnt + add_cnt)
print(ans)

Submission status: Accepted

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

def dfs(G, i):
    if i == 0:
        return 1e9
    n = min(G // (i*100), pc[i][0])
    s = n * i * 100
    if n == pc[i][0]:
        s += pc[i][1]
    if s < G:
        n += dfs(G-s, i-1)
    return min(n, dfs(G, i-1))

print(dfs(g, d))

Submission status: Accepted

Solution code:
import math
D,G = map(int,input().split())
pc = list(list(map(int,input().split()))for i in range(D))
ans = float('inf')
for i in range(2**D):    
    score = 0
    AC = 0
    b = bin(2**D+i)[3:]
    for j in range(D):
        if b[j] == "1":
            score += pc[j][1]+pc[j][0]*(j+1)*100
            AC += pc[j][0]
        else:
            hoge = j
    if G <= score + pc[hoge][0]*(hoge+1)*100:
        a = max(0,math.ceil((G-score)/((hoge+1)*100)))
        score = G
        AC+= a
    if score >= G:
        ans = min(ans,AC)
print(ans)

Submission status: Accepted

Solution code:
d,g = map(int, input().split())
pc = [0] + [list(map(int, input().split())) for _ in range(d)]
def function(G, i):
    if i == 0:
        return 10**9
    n = min(G // (i *100), pc[i][0])
    s = n * i * 100
    if n == pc[i][0]:
        s += pc[i][1]
    if s < G:
        n += function(G-s, i - 1)
    return min(n, function(G, i-1))
print(function(g, d))

Submission status: Accepted

Solution code:
import math

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

ans = sum(p)

for bit in range(1<<d):
    tmp_ans = 0
    tmp_score = 0
    for i in range(d):
        if (bit >> i) & 1 == 1:
            tmp_ans += p[i]
            tmp_score += (i+1) * p[i] + c[i]

    for i in reversed(range(d)):
        if (bit >> i) & 1 == 0 and tmp_score < g:
            if g - tmp_score > (i+1) * p[i]:
                tmp_ans += p[i]
                tmp_score += (i+1) * p[i] + c[i]
            else:
                n = math.ceil( (g - tmp_score) / (i+1) )
                tmp_ans += n
                tmp_score += (i+1) * n

    ans = min(ans, tmp_ans)

print(ans)

Submission status: Accepted

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

def function(G, i):
	if i==0:
		return 1e9
	n=min(G//(i*100), PC[i][0])
	s=n*i*100
	if n==PC[i][0]:
		s+=PC[i][1]
	if s<G:
		n+=function(G-s, i-1)
	return min(n, function(G,i-1))
print(function(G, D))

Submission status: Accepted

Solution code:
import itertools
import math

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

a = [i for i in range(d)]

b = itertools.permutations(a,d)

ans = float('inf')

for x in b:
    c = 0
    e = 0
    flag = False
    for i in x:
        if e+100*(i+1)*pc[i][0]<=g:
            c += pc[i][0]
            e+=100*(i+1)*pc[i][0]+pc[i][1]
            if e >= g:
                break
        else:
            c += math.ceil((g-e)/(100*(i+1)))
            break
    ans = min(ans, c)

print(ans)

Submission status: Accepted

Solution code:
D, G = map(int, input().split())
problems = []
for i in range(0, D):
	problems.append(list(map(int, input().split())))
min = 5000000000000000
for i in range(0, 2**D):
	cnt = 0
	sum = 0
	m = i
	notyet = []
	for j in range(0, D):
		if m % 2 == 1:
			cnt += problems[j][0]
			sum += (j+1)*100*problems[j][0]+problems[j][1]
		else:
			notyet.append(j)
		m //= 2
	if sum >= G:
		if cnt < min:
			min = cnt
	else:
		notyet.sort(reverse = True)
		flag = False
		for j in range(0, len(notyet)):
			for k in range(1, problems[notyet[j]][0]):
				cnt += 1
				sum += (notyet[j]+1) * 100
				if sum >= G:
					if cnt < min:
						min = cnt
					flag = True
					break
			if flag:
				break
print(min)

Submission status: Accepted

Solution code:
from math import ceil
d,g = map(int, input().split())
PC = [list(map(int, input().split())) for i in range(d)]
#print(PC)

fans = 10**10
for i in range(1<<d):
    su = 0
    ans = 0
    temp = [True for i in range(d)]
    #print("i=",i)
    for j in range(d):
        if (i>>j)&1 == 1:
            #print(PC[j],"を追加")
            su += (j+1)*100*PC[j][0] + PC[j][1]
            ans += PC[j][0]
            temp[j] = False
    if su < g:
        #print("su<g",su,ans)
        fnd = d
        while fnd >= 0:
            fnd += -1
            if temp[fnd] is False:
                continue
            else:
                if (fnd+1)*100*(PC[fnd][0]-1) + su >= g :
                    ans += ceil((g - su) / ((fnd+1) * 100))
                    fans = min(ans, fans)
                    #print("ans=", ans,"fnd=",fnd)

    else:
        fans = min(ans,fans)
        #print("ans=",ans)
    #print(fans)
print(fans)

Submission status: Accepted

Solution code:
import itertools

d, g = map(int, input().split())
p, c = [None] * d, [None] * d
for i in range(d):
    p[i], c[i] = map(int, input().split())


ans = float('inf')
for r in range(0, d + 1):
    for choice in itertools.combinations(range(d), r):
        total = sum(100 * (i + 1) * p[i] + c[i] for i in choice)
        count = sum(p[i] for i in choice)

        for i in reversed(range(d)):
            if i in choice:
                continue
            
            finished = True
            for _ in range(p[i]):
                if g <= total:
                    finished = False
                    break
                total += (i + 1) * 100
                count += 1
            
            if finished:
                total += c[i]
            
            if g <= total:
                ans = min(ans, count)

print(ans)

Submission status: Accepted

Solution code:
d, g = map(int, input().split())
p = [0]*d
c = [0]*d
for i in range(d):
  p[i], c[i] = map(int, input().split())
 
ans = 10**6

for i in range(2**d):
  cnt = 0
  sum = 0
  k = -1
  for j in range(d):
    if (i >> j) & 1:
      sum += (j+1)*100*p[j]+c[j]
      cnt += p[j]
    else:
      k = j
  if sum < g:
    s1 = 100 * (k + 1)
    need = (g - sum + s1 - 1) // s1
    if need >= p[k]:
      continue
    cnt += need
  ans = min(ans, cnt)
print(ans)

Submission status: Accepted

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

def make_pat(i):
    pat = [[0, 1]] * i + [[0]] + [[0, 1]] * (D-i-1)
    return product(*pat)

min_ = sum(p for p in P)
for i in range(D):
    for pat in make_pat(i):
        scr = sum(P[j] * (j+1) * 100 + C[j] for (j, p) in enumerate(pat) if p == 1)
        num = sum(P[j] for (j, p) in enumerate(pat) if p == 1)
        for k in range(P[i]):
            zbn = k * (i+1) * 100 + (0 if k < P[i] else C[i])
            if scr + zbn >= G:
                if min_ > num + k:
                    min_ = num + k
                break

print(min_)

Submission status: Accepted

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

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 = 100000

sum = 0
k = 0

for i in range(2 ** d):
    cnt = 0
    sum = 0
    k = - 1

    for j in range(d):

        if (i >> j) & 1:
            sum += 100 * p[j] * (j + 1) + c[j]
            cnt += p[j]

        else:
            k = j

    if sum < g:
        s1 = 100 * (k + 1)
        need = (g - sum + s1 - 1) // s1

        if need >= p[k]:
            continue

        cnt += need

    ans = min(ans, cnt)

print(ans)

Submission status: Accepted

Solution code:
d,g = map(int,input().split())
p,c = [0]*d,[0]*d
import math

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

ans = 10**9
for i in range(2**d):
    ls = ""
    for j in range(d):
        if (i>>j)&1:
            ls = "1"+ls
        else:
            ls = "0"+ls
    score = 0
    cnt = 0
    ls = list(ls)
    for i in range(d):
        if ls[(d-1)-i] == "1":
            score += 100*(i+1)*p[i] + c[i]
            cnt += p[i]
    if score>=g:
        ans = min(ans,cnt)
    else:
        index = d-1 - ls.index("0")
        maximum = p[index]
        score = g - score
        if maximum>=math.ceil(score/((index+1)*100)):
            cnt +=math.ceil(score/((index+1)*100))
            ans = min(ans,cnt)
        else:
            pass


print(ans)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(100000)
inf = float('inf')

def dfs(h, s):
    # 停止条件
    if h == D:
        tmp = 0
        p = 0
        ans = 0
        for i, c in enumerate(s):
            if c == '0':
                tmp = i
            else:
                ans += pc[i][0]
                p += (i+1) * 100 * pc[i][0] + pc[i][1]
        for i in range(pc[tmp][0]-1):
            if p < G:
                p += (tmp + 1) * 100
                ans += 1
        if p < G:
            return inf
        else:
            return ans
    tmp1 = dfs(h+1, s + '0')
    tmp2 = dfs(h+1, s + '1')
    return min(tmp1, tmp2)


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

Submission status: Accepted

Solution code:
# ABC104C - All Green
import sys
input = sys.stdin.readline

def ans(g, i, L):
    # Assume the case using question no.i
    if i == 0:  # base case
        return float("inf")

    n = min(g // (i * 100), L[i][0])  # n:count
    s = n * i * 100  # s:score

    # add bonus if available
    if n == L[i][0]:
        s += L[i][1]

    # make up for the shortage
    if s < g:
        n += ans(g - s, i - 1, L)

    # compare to other cases without question no.i recursively
    return min(n, ans(g, i - 1, L))


def main():
    d, g = list(map(int, input().rstrip().split()))
    arr = [0] + [list(map(int, input().rstrip().split())) for _ in range(d)]
    print(ans(g, d, arr))


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
# ABC104C - All Green
def ans(g, i, L):
    # Assume the case using question no.i
    if i == 0:  # base case
        return float("inf")

    n = min(g // (i * 100), L[i][0])  # n:count
    s = n * i * 100  # s:score

    # add bonus if available
    if n == L[i][0]:
        s += L[i][1]

    # make up for the shortage
    if s < g:
        n += ans(g - s, i - 1, L)

    # compare to other cases without question no.i recursively
    return min(n, ans(g, i - 1, L))


def main():
    d, g = list(map(int, input().rstrip().split()))
    arr = [0] + [list(map(int, input().rstrip().split())) for _ in range(d)]
    print(ans(g, d, arr))


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
D, G = map(int, input().split())
pc = [list(map(int, input().split())) for i in range(D)]
ans = 10**5

for i in range(2**D):
  score = 0
  tmp = 0
  solved = [False]*D
  for j in range(D):
    if (i>>j) & 1:
      score += (j+1) * 100 * pc[j][0] + pc[j][1]
      tmp += pc[j][0]
      solved[j] = True
  if score >= G:
    ans = min(ans, tmp)
  else:
    for k in range(D-1,-1,-1):
      if solved[k] == False:
        l = 0
        while score < G and l < pc[k][0]:
          score += (k+1)*100
          tmp += 1
          l += 1
        if score >= G:
          ans = min(ans, tmp)
          break
print(ans)