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())
p,c = [],[]
ans = float('inf')
for i in range(d):
    x,y = map(int,input().split())
    p.append(x)
    c.append(y)
for i in range((1<<d)):
    tmp,cnt = 0,0
    for j in range(d):
        if i&(1<<j):
            tmp = tmp + 100*(j+1)*p[j]+c[j]
            cnt += p[j]
    if tmp>=g:
        if cnt<ans: ans=cnt
    else:
        for j in range(d-1,-1,-1):
            if i&(1<<j): continue
            for k in range(p[j]):
                if tmp>=g: break
                tmp = tmp + 100*(j+1)
                cnt+=1
        if cnt<ans: ans = cnt
print(ans)

Submission status: Accepted

Solution code:
import math
def li():
    return [int(x) for x in input().split()]

d, g = li()
ps, cs = [], []
for i in range(d):
    p, c = li()
    ps.append(p)
    cs.append(c)
ps.reverse()
cs.reverse()
# ボーナス得点のパターンを先に全て列挙し、点数が届いていなければ高得点から埋めていく
qcnts = []

for mask in range(2**d):
    score = 0
    qcnt = 0
    #ボーナス計算
    for i in range(d):
        # i番目のフラグが立ってる
        if mask & (1 << i):
            score += cs[i] + ps[i] * 100 * (d-i)
            qcnt += ps[i]
    #残りを高得点から埋めていく
    required_score = g - score
    if required_score >= 0:
        for i in range(d):
            # i番目のフラグが立っているならスキップ
            if mask & (1 << i):
                continue
            required_qcnt = min(math.floor(required_score / (100 * (d-i))), ps[i])
            qcnt += required_qcnt
            score += required_qcnt * (100 * (d-i))
            if score >= g:
                break
    qcnts.append(qcnt)

print(min(qcnts))

Submission status: Accepted

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

#sys.setrecursionlimit(10**9)
#from functools import lru_cache

def RD(): return input().rstrip().decode()
def II(): return int(input())
def FI(): return float(input())
def MI(): return map(int,input().split())
def MF(): return map(float,input().split())
def LI(): return list(map(int,input().split()))
def LF(): return list(map(float,input().split()))
def TI(): return tuple(map(int,input().split()))
# rstrip().decode()


def main():
	d,g=MI()
	P=[]
	C=[]
	for _ in range(d):
		p,c=MI()
		P.append(p)
		C.append(c)
	#print(P,C)

	ans=10**10

	for i in range(1<<d):
		cnt=0
		gg=0
		for j in range(d):
			if i&1<<j:
				cnt+=P[j]
				gg+=P[j]*100*(j+1)+C[j]
		#print(i,cnt,gg)

		for j in reversed(range(d)):
			if not i&1<<j:
				if gg+(P[j]-1)*100*(j+1)>=g:
					cnt+=max(0,-((-g+gg)//(100*(j+1))))
					gg=g
					break
				else:
					cnt+=P[j]-1
					gg+=(P[j]-1)*100*(j+1)

		if gg>=g:
			ans=min(ans,cnt)
	print(ans)

















if __name__ == "__main__":
	main()

Submission status: Accepted

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

P=[0]*(D+1)
C=[0]*(D+1)

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

Min_Solved=float("inf")

for i in range(2**D):
    Rest=G
    Solved=0

    A=[0]*(D+1)

    x=i
    for j in range(1,D+1):
        A[j]=x%2
        if x%2:
            Rest-=j*P[j]+C[j]
            Solved+=P[j]
        x>>=1

    for k in range(D,0,-1):
        if Rest<=0:
            break

        if A[k]==0:
            if k*P[k]<=Rest:
                Rest-=k*P[k]+C[k]
                Solved+=P[k]
            else:
                z=(Rest+(k-1))//k
                Rest-=k*z
                Solved+=z

    Min_Solved=min(Min_Solved,Solved)
    assert 1

print(Min_Solved)

Submission status: Accepted

Solution code:
d,g=map(int,input().split())
T=[]
for _ in range(d):
  p,c=map(int,input().split())
  T.append([p,c])

ans=float('inf')
for i in range(1<<d):
  Q=[]
  cnt=0
  score=0
  for j in range(d):
    if (i>>j)&1:
      Q.append(j)
  for v in Q:
    score+=100*(v+1)*(T[v][0])+T[v][1]
    cnt+=T[v][0]
  if score>=g:
    ans=min(ans,cnt)
  else:
    for i in range(d-1,-1,-1):
      if i in Q:
        continue
      if score>=g:
        continue
      rest=T[i][0]
      while rest:
        if score>=g:
          break
        score+=100*(i+1)
        rest-=1
        cnt+=1
    ans=min(ans,cnt)
print(ans)

Submission status: Accepted

Solution code:
D,G=map(int,input().split())
p=list()
c=list()
for _ in range(D):
  P,C=map(int,input().split())
  p.append(P)
  c.append(C)
ans=1<<29
for bit in range(1<<D):
  sum_=0
  num_=0
  for i in range(D):
    if bit&(1<<i):
      sum_+=c[i]+p[i]*100*(i+1)
      num_+=p[i]
  if sum_>=G:
    ans=min(ans,num_);
  else:
    for i in range(D-1,-1,-1):
      if bit&(1<<i):
        continue
      for j in range(p[i]):
        if sum_>=G:
          break
        sum_+=100*(i+1)
        num_+=1
    ans=min(ans,num_);
print(ans)

Submission status: Accepted

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

res = 10**9
# どの問題を全完するか決め打つ
for bit in range(1 << D):
    sum = 0
    num = 0

    # bitが立っている = 全完する問題について
    for i in range(D):
        if bit & (1 << i):
            sum += c[i] + p[i] * 100 * (i + 1)
            num += p[i]

    # 既にGを超えていたら「中途半端に」解く必要はない
    if sum >= G:
        res = min(res, num)

    # 「中途半端に」解く必要がある場合
    else:
        # どの問題を「中途半端に」解くか
        # 全完していない問題のうち、最も点数が高いもの
        # 全て全完している場合に注意
        d = -1
        for i in range(D - 1, -1, -1):
            if not(bit & (1 << i)):
                d = i
                break
        if d == -1:
            continue
        else:
            # 全完１歩手前まで順に試す
            for j in range(p[d] - 1):
                sum += 100 * (d + 1)
                num += 1
                if sum >= G:
                    break
            # p-1問解いてもGに達していない場合に注意
            if sum >= G:
                res = min(res, num)

print(res)

Submission status: Accepted

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

ans = 10**15
for i in range(2**D):
    score = 0
    prob = 0
    lst = []
    for j in range(D):
        if((i >> j) & 1):
            score += (j+1)*100*problem[j][0]+problem[j][1]
            prob += problem[j][0]
        else:
            lst.append(j)
            
            
    if(score < G):
        r = lst[-1]
        for _ in range(problem[r][0]-1):
            score += 100*(r+1)
            prob += 1
            if(score >= G):
                break
        
    if(score >= G):
        ans = min(ans, prob)
            
print(ans)

Submission status: Accepted

Solution code:
import bisect,collections,copy,itertools,math,string
import sys
def I(): return int(sys.stdin.readline().rstrip())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))
def S(): return sys.stdin.readline().rstrip()
def LS(): return list(sys.stdin.readline().rstrip().split())
def main():
    d, g = LI()
    lst = [0 for _ in range(d)]
    for i in range(d):
        p, c = LI()
        lst[i] = (p, c)
    
    ans = float("inf")
    bits = itertools.product([0,1],repeat=d)

    for bit in bits:
        point = 0
        cnt = 0
        for i in range(d):
            if bit[i] == 1:
                cnt += lst[i][0]
                point += (i+1)*100*lst[i][0] + lst[i][1]
        for i in range(d-1,-1,-1):
            if point>=g:
                break
            if bit[i] == 0:
                for _ in range(lst[i][0]-1):
                    cnt += 1
                    point += (i+1)*100
                    if point>=g:
                        break
        if point>=g:
            ans = min(ans,cnt)
    print(ans)

main()

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)]

ans = float("inf")
for bit in range(1<<d):
    sum = 0
    cnt = 0
    #残ってるやつのmaxのインデックス取得するためsetを設定
    nokori = set(range(1, d + 1))
    for i in range(d):
        if bit & (1 << i):
            sum += pc[i][0]*100*(i+1) + pc[i][1]
            cnt += pc[i][0]
            nokori.discard(i+1)
    
    if sum < g:
        use = max(nokori)
        husoku = min(ceil((g-sum)/(use*100)),pc[use-1][0])
        cnt += husoku
        sum += husoku*use*100
    
    if sum >= g:
        ans = min(cnt,ans)

print(ans)

Submission status: Accepted

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

ans=10000
for i in range(2**D):
    score=0
    cnt=0
    rest=[]
    for j in range(D):
        if (i>>j)&1:
            score+=100*(j+1)*s[j][0]+s[j][1]
            cnt+=s[j][0]
        else:
            rest.append(j)

    if score<G:
        r=rest[-1]
        for _ in range(s[r][0]-1):
            score+=100*(r+1)
            cnt+=1
            if score>=G: break

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

print(ans)

Submission status: Accepted

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

for i in range(D):
    p,c = map(int,input().split())
    ans += p
    table.append((p,c))


for i in range(2**D):
    score = 0
    n = 0
    solved = [0] * D
    for j in range(D):
        if i>>j & 1:
            p,c = table[j]
            solved[j] = 1
            score += 100*(j+1)*p+c
            n += p
    if score<G:
        for k in range(D-1,-1,-1):
            if solved[k] == 0:
                p = table[k][0]
                for l in range(1,p):
                    score += 100*(k+1)
                    n += 1
                    if score>=G:
                        break
                break

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

Submission status: Accepted

Solution code:
d, g = map(int, input().split())
dp = [0 for i in range(1001)]
dp[0] = 0
num = 0
for i in range(1, d + 1):
    p, c = map(int, input().split())
    for j in range(num, -1, -1):
        for k in range(1, p + 1):
            if k != p:
                dp[j + k] = max(dp[j + k], dp[j] + 100 * i * k)
            else:
                dp[j + k] = max(dp[j + k], dp[j] + 100 * i * k + c)
    num += p
for i in range(1001):
    if dp[i] >= g:
        print(i)
        break

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
from itertools import combinations_with_replacement,product
def input(): return sys.stdin.readline().rstrip()


def main():
    D,G=map(int, input().split())
    problem=[]
    for i in range(1,D+1):
        p,c=map(int, input().split())
        problem.append([i,p,c])
    ans=10000000
    for bit in list(product([0,1],repeat=D)):
        pnum=0
        nokori=G
        notcomp=[]
        for i in range(D):
            if bit[i]==1:
                pnum+=problem[i][1]
                nokori-=problem[i][2]+problem[i][1]*problem[i][0]*100
            else:
                notcomp.append(problem[i])
        while nokori>0 and notcomp:
            score,p,c=notcomp.pop()
            if score*(p-1)*100<=nokori:
                nokori-=score*(p-1)*100
                pnum+=p-1
            else:
                tmp=score*100
                pnum+=(nokori+tmp-1)//tmp
                nokori=0
        if nokori<=0:
            ans=min(ans,pnum)
    print(ans)
    


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def main():
  ans = 1000
  d,g  = map(int,input().split())
  pc = [list(map(int,input().split())) for i in range(d)]
  pc.reverse()
  #print(pc)
  for i in range( 2 ** d):
    score = 0
    count = 0
    for j in range(d):
      if i & (1<<j):
        score += pc[j][0] * (d-j) * 100 + pc[j][1]
        count += pc[j][0]
    if score >= g:
      if ans > count:
        ans = count
      #print(bin(i),count,score)
      continue
    for j in range(d):
      if not(i &(1<<j)):
        #print("nokori"+str(j))
        c = 0
        for k in range(1,pc[j][0]):
          score += (d-j) * 100
          count += 1
          c += 1
          if score >= g:
            if ans > count:
              ans = count
            #print(bin(i),j,c,count,score)
            break
        break
  print(ans)

if __name__ == '__main__':
  ans = 0
  main()

Submission status: Accepted

Solution code:
def dsf(i,sum,count,nokori):
    global ans
    # 階層が最下層になった時
    if i == d:
        #sumは絶対答えではない
        if sum < g:
            use = max(nokori)
            n = min(pc[use - 1][0],-(-(g - sum) // (100 * use)))
            count += n
            sum += n * use * 100



        # sumは答えになる可能性あり
        if sum >= g:
            ans = min(ans,count)
    else:
        #問題を解かないパターン
        dsf(i+1,sum,count,nokori)
        #問題を解くパターン(階層、合計+最大のボーナス、現在の合計の数+最大の数、残りの問題を管理)
        dsf(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')

#階層、合計、現在の合計の数、残りの問題を管理
dsf(0,0,0,set(range(1,d + 1)))
print(ans)

Submission status: Accepted

Solution code:
# まだ解いてない配点を nokori として持つ
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:
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 math import ceil

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):
    cnt = 0
    sum = 0
    remain = set(range(1,D+1))

    for i in range(D):
        if bit & (1 << i):
            cnt += pc[i][0]
            sum += pc[i][0]*(i+1)*100 + pc[i][1]
            remain.discard(i+1)

    if sum < G:
        use = max(remain)
        n = min(pc[use-1][0], ceil((G-sum)/(use*100)))
        cnt += n
        sum += n*use*100

    if sum >= G:
        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())

ans = 1001
import math
for i in range(2**D):
    pp = 0
    t = 0
    b = format(i, "0" + str(D) + "b")
    #print(b)
    for j in range(D):
        pp += (100 * (j + 1) * p[j] + c[j]) * int(b[j])
        t += p[j] * int(b[j])
    if pp >= G:
        ans = min(ans, t)
        continue
    for k in range(D-1, -1, -1):
        if b[k] == "0":
            a = math.ceil((G - pp)//100/(k+1))
            if a < p[k]:
                t += a
                ans = min(ans, t)
                break
            else:
                t += p[k]-1
                pp += 100* (k + 1) *(p[k] - 1)

print(ans)

Submission status: Accepted

Solution code:
import sys

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

d, g = map(int, readline().split())
pc = []
for _ in range(d):
    pc.append(readline().split())

def main(d, g, pc):
    min_cnt = 1000000000
    for i in range(2**d):
        wa = 0
        cnt = 0
        nokori = [i for i in range(d)]
        for j in range(d):
            if i & 2**j:
                wa += int(pc[j][1]) + 100 * int(pc[j][0]) * (j+1)
                cnt += int(pc[j][0])
                nokori.remove(j)
        if wa < g:
            if int(pc[nokori[-1]][0]) * 100 *(nokori[-1]+1) > int(g) - wa:
              if (g-wa) % (100 *(nokori[-1]+1)) != 0:
                  ato = 1 + (g-wa) // (100 *(nokori[-1]+1))
              else:
                  ato = (g-wa) // (100 *(nokori[-1]+1))
              cnt += ato
              wa += ato * 100 * (nokori[-1]+1)
        if g <= wa:
	        min_cnt = min(cnt, min_cnt)
    return min_cnt


print(main(d, g, pc))

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):
    cnt = 0
    sum = 0
    remain = set(range(1,D+1))

    for i in range(D):
        if bit & (1 << i):
            cnt += pc[i][0]
            sum += pc[i][0]*(i+1)*100 + pc[i][1]
            remain.discard(i+1)

    if sum < G:
        use = max(remain)
        n = min(pc[use-1][0],-(-(G - sum)//(use*100)))
        cnt += n
        sum += n*use*100

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

print(ans)

Submission status: Accepted

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

ans = 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)

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

print(ans)

Submission status: Accepted

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

for i in range(2**d):
    count = 0
    total = 0
    for j in range(d):
        if (i >> j) & 1 == 1:
            count += pc[j][0]
            total += (j+1)*100*pc[j][0] + pc[j][1]

    if total >= g:
        ans = min(ans, count)
    else:
        for k in reversed(range(d)):
            if ((i >> k) & 1) == 0:
                for _ in range(pc[k][0]-1):
                    count += 1
                    total += (k+1)*100
                    if total >= g:
                        ans = min(ans, count)
                        break

print(ans)

Submission status: Accepted

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

for i in range(2**d):
    count = 0
    total = 0
    for j in range(d):
        if (i >> j) & 1 == 1:
            count += pc[j][0]
            total += (j+1)*100*pc[j][0] + pc[j][1]

    if total >= g:
        ans = min(ans, count)
    else:
        for k in reversed(range(d)):
            if ((i >> k) & 1) == 0:
                for _ in range(pc[k][0]):
                    if total >= g:
                        ans = min(ans, count)
                        break
                    count += 1
                    total += (k+1)*100

print(ans)

Submission status: Accepted

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

for i in range(2**D):
    score=0
    b=0
    cnt=0
    for j in range(D):
        if ((i>>j)&1):
            score+=100*(j+1)*pc[j][0]+pc[j][1]
            cnt+=pc[j][0]
        else:
            b=j
    for k in range(pc[b][0]):
        if score>=G and cnt<ans:
            ans=cnt
        score+=(b+1)*100
        cnt+=1
print(ans)

Submission status: Accepted

Solution code:
d,g = map(int,input().split())
pc = list(list(map(int, input().split())) for _ in range(d))
ans = float("inf")

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

Submission status: Accepted

Solution code:
d,g = map(int, input().split())
pc = list(list(map(int,input().split())) for _ in range(d))
ans = float("inf")
          
for i in range(1<<d):
    count = 0
    sum = 0
    nokori = set(range(1, d+1))
    
    # ボーナスをもらえる解答のみでスコアを計算
    for j in range(d):
        if i & 1<<j:
            sum += pc[j][0]*(j+1)*100+pc[j][1]
            count += pc[j][0]
            nokori.discard(j+1)
            
    # スコアがG点に届かない場合
    if sum < g:
        use = max(nokori)
        n = min(pc[use-1][0], -(-(g-sum)//(use*100)))
        count += n
        sum += n*use*100
        
    # スコアがG点に届いた場合
    if sum >= g:
        ans = min(ans, count)
print(ans)

Submission status: Accepted

Solution code:
d,g=map(int,input().split())
p=[]
c=[]
for i in range(d):
    P,C=map(int,input().split())
    p.append(P)
    c.append(C)
ans=sum(p)
for i in range(2**d):
    z=i
    x=[]
    for j in range(d):
        x.append(z%2)
        z=z//2
    po=0
    m=0
    for j in range(d):
        if x[j]==1:
            po+=100*(j+1)*p[j]+c[j]
            m+=p[j]
    q=[[] for j in range(d)] #残りp、c
    s=0
    for j in range(d):
        if x[j]==0:
            q[s].append(100*(j+1))
            q[s].append(p[j])
            s+=1
    q=[q[j] for j in range(d) if q[j]!=[]]
    q=sorted(q,reverse=True)
    w=len(q)
    for j in range(w):
        q[j][1]-=1
    if po>=g:
        ans=min(ans,m)
    else:
        for j in range(w):
            if po+q[j][0]*q[j][1]>=g:
                m+=(g-po+q[j][0]-1)//q[j][0]
                ans=min(ans,m)
                break
            else:
                po+=q[j][0]*q[j][1]
                m+=q[j][1]
print(ans)

Submission status: Accepted

Solution code:
d,g=map(int,input().split())
p=[]
c=[]
for i in range(d):
    P,C=map(int,input().split())
    p.append(P)
    c.append(C)
ans=sum(p)
for i in range(2**d):
    z=i
    x=[]
    for j in range(d):
        x.append(z%2)
        z=z//2
    po=0
    m=0
    for j in range(d):
        if x[j]==1:
            po+=100*(j+1)*p[j]+c[j]
            m+=p[j]
    q=[[] for j in range(d)] #残りp、c
    s=0
    for j in range(d):
        if x[j]==0:
            q[s].append(100*(j+1))
            q[s].append(p[j])
            s+=1
    q=[q[j] for j in range(d) if q[j]!=[]]
    q=sorted(q,reverse=True)
    w=len(q)
    for j in range(w):
        q[j][1]-=1
    if po>=g:
        ans=min(ans,m)
    else:
        for j in range(w):
            if po+q[j][0]*q[j][1]>=g:
                m+=(g-po+q[j][0]-1)//q[j][0]
                ans=min(ans,m)
                break
            else:
                po+=q[j][0]*q[j][1]
                m+=q[j][1]
print(ans)

Submission status: Accepted

Solution code:
import itertools
from typing import List, Tuple
 
 
def main():
    d, g = map(int, input().split())
    v = []
    for _ in range(d):
        p, c = map(int, input().split())
        v.append((p, c))
 
    print(ag(v, g))
 
 
def ag(v: List[Tuple[int, int]], g: int) -> int:
    ret = 10 ** 10
    for comb in itertools.product((False, True), repeat=len(v)):
        cnt, score = 0, 0
        for i, bit in enumerate(comb):
            if bit:
                score += (i + 1) * 100 * v[i][0] + v[i][1]
                cnt += v[i][0]
        if score < g:
            idx = len(v) - list(reversed(comb)).index(False) - 1
            add = ((g - score) + ((idx + 1) * 100) - 1) // ((idx + 1) * 100)
            if add < v[idx][0]:
                cnt += add
            else:
                cnt = 10 ** 10  # impossible
        ret = min(ret, cnt)
    return ret
 
 
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import itertools
from typing import List, Tuple


def main():
    d, g = map(int, input().split())
    v = []
    for _ in range(d):
        p, c = map(int, input().split())
        v.append((p, c))

    print(ag(v, g))


def ag(v: List[Tuple[int, int]], g: int) -> int:
    ret = 10 ** 10
    for comb in itertools.product((False, True), repeat=len(v)):
        cnt, score = 0, 0
        for i, bit in enumerate(comb):
            if bit:
                score += (i + 1) * 100 * v[i][0] + v[i][1]
                cnt += v[i][0]
        if score < g:
            idx = len(v) - list(reversed(comb)).index(False) - 1
            add = ((g - score) + ((idx + 1) * 100) - 1) // ((idx + 1) * 100)
            if add < v[idx][0]:
                cnt += add
            else:
                cnt = 10 ** 10  # impossible
        ret = min(ret, cnt)
    return ret


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import itertools
from typing import List, Tuple


def main():
    d, g = map(int, input().split())
    v = []
    for _ in range(d):
        p, c = map(int, input().split())
        v.append((p, c))

    print(ag(v, g))


def ag(v: List[Tuple[int, int]], g: int) -> int:
    # ex. [(3, 500), (5, 800)] -> [(1, 3, 500), (2, 5, 800)]
    v = [(i + 1, v[i][0], v[i][1]) for i in range(len(v))]

    result = 100 ** 10

    for j in range(len(v) + 1):
        for cb in itertools.combinations(v, j):
            sc = 0
            cnt = 0
            # calc bonus score
            for (i, p, c) in cb:
                sc += i * 100 * p + c
                cnt += p

            for idx in reversed(range(len(v))):
                if sc >= g:
                    break
                if v[idx] in cb:
                    continue
                i, p, _ = v[idx]
                for _ in range(p - 1):
                    if sc >= g:
                        break
                    sc += i * 100
                    cnt += 1

            if sc >= g:
                result = min(result, cnt)
    return result


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import copy

from typing import List, Tuple


def main():
    d, g = map(int, input().split())
    v = []
    for _ in range(d):
        p, c = map(int, input().split())
        v.append((p, c))

    print(ag(v, g))


def ag(v: List[Tuple[int, int]], g: int) -> int:
    # ex. [(3, 500), (5, 800)] -> [(1, 3, 500), (2, 5, 800)]
    v = [(i, p, c) for i, (p, c) in enumerate(v, 1)]

    result = 100 ** 10
    for j in range(2 ** len(v)):
        cb = []
        for k in range(len(v)):
            if ((j >> k) & 1):
                cb.append(v[k])

        sc = 0
        cnt = 0
        # calc bonus score
        for (i, p, c) in cb:
            sc += i * 100 * p + c
            cnt += p

        for idx in reversed(range(len(v))):
            if sc >= g:
                break
            if v[idx] in cb:
                continue
            i, p, _ = v[idx]
            for _ in range(p - 1):
                if sc >= g:
                    break
                sc += i * 100
                cnt += 1

        if sc >= g:
            result = min(result, cnt)
    return result


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import copy
import heapq

from typing import List, Tuple


def main():
    d, g = map(int, input().split())
    v = []
    for _ in range(d):
        p, c = map(int, input().split())
        v.append((p, c))

    print(ag(v, g))


def ag(v: List[Tuple[int, int]], g: int) -> int:
    rs = []
    # ex. [(3, 500), (5, 800)] -> [(1, 3, 500), (2, 5, 800)]
    v = [(i, p, c) for i, (p, c) in enumerate(v, 1)]

    for j in range(2 ** len(v)):
        cb = []
        for k in range(len(v)):
            if ((j >> k) & 1):
                cb.append(v[k])

        sc = 0
        cnt = 0
        # calc bonus score
        for (i, p, c) in cb:
            sc += i * 100 * p + c
            cnt += p

        vv = [x for x in copy.copy(v) if not x in cb]
        while sc < g:
            if not vv:
                break
            i, p, _ = vv.pop()
            for _ in range(p - 1):
                if sc >= g:
                    break
                sc += i * 100
                cnt += 1

        if sc >= g:
            heapq.heappush(rs, cnt)
    return heapq.heappop(rs)


if __name__ == '__main__':
    main()