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:
def solve():
    inf = 1 << 60
    D, G = map(int, input().split())
    p = []
    c = []
    for i in range(D):
        pi, ci = map(int, input().split())
        p.append(pi)
        c.append(ci)

    bitD = 1 << D
    min_cnt = inf
    for b in range(bitD):
        sc = 0
        cnt = 0
        for i in range(D):
            if (b & (1 << i)) != 0:
                sc += (i + 1) * 100 * p[i] + c[i]
                cnt += p[i]
        if sc < G:
            for i in range(D-1,-1,-1):
                if (b & (1 << i)) == 0:
                    unit = (i + 1) * 100
                    cnt2 = min((G - sc + (unit - 1)) // unit, p[i] - 1)
                    sc += cnt2 * unit
                    cnt += cnt2
                    break
        if sc >= G:
            min_cnt = min(min_cnt, cnt)

    return min_cnt

print(solve())

Submission status: Accepted

Solution code:
import numpy as np
D,G=list(map(int,input().split()))
p=np.zeros(D)
c=np.zeros(D)
for i in range(D):
    a,b=list(map(int,input().split()))
    p[i]=a
    c[i]=b
    
def solve(x):  
    score=0
    cost=0
    no_use=0
    
    b=str(format(x,'010b'))
    for i in range(1,D+1):
        if b[-i]=="1": #全問解答する
            score+=100*i*p[i-1]+c[i-1]
            cost+=p[i-1]
        else:
            no_use=i-1

    if score<G: #足りていない場合
        no_solve=p[no_use]-1
        while(no_solve!=0):
            score+=100*(no_use+1)
            cost+=1
            if score>=G:
                return cost
            no_solve-=1
                
    if score<G:
        return 10**9+7
    return cost

min_cost=10**9+7
for x in range(2**D):
    cost=solve(x)
    if cost<min_cost:
        min_cost=cost
print(int(min_cost))

Submission status: Accepted

Solution code:
import numpy as np
D,G=list(map(int,input().split()))
p=np.zeros(D)
c=np.zeros(D)
for i in range(D):
    a,b=list(map(int,input().split()))
    p[i]=a
    c[i]=b
    
def calc(i,j):
    if i//j==0:
        return 1
    else:
        return i//j
      
min_cost=10**9+7
for x in range(2**D):
    score=0
    cost=0
    max_no_use=0
    
    b=str(format(x,'010b'))
    for i in range(1,D+1):
        if b[-i]=="1":
            score+=100*i*p[i-1]+c[i-1]
            cost+=p[i-1]
        else:
            max_no_use=abs(i)-1
    shortage=G-score
    if shortage>0:
        add=calc(shortage,100*(max_no_use+1))
        if add<=p[max_no_use]-1:
            cost+=add
            if min_cost>cost:
                min_cost=cost
    else:
        if min_cost>cost:
            min_cost=cost
print(int(min_cost))

Submission status: Accepted

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

for x in range(0,D):
    p,c = map(int,input().split())
    P.append(p)
    C.append(c)

answer = sum(P)

for x in range(1<<D):
    score = 0
    number = 0
    for i in range(1,D+1):
        if x & (1<<(i-1)) > 0:
            score += P[i]*i*100 + C[i]
            number += P[i]
    
    if score >= G:
        answer = min(answer,number)
        continue

    for i in range(D,0,-1):
        if x & (1<<(i-1)) == 0:
            n = (G-score)//(100*i)
            if n <= P[i]:
                score += 100*i*n
                number += n
            else:
                score += 100*i*P[i]
                number += P[i]
        if score >= G:
            answer = min(answer,number)
            break

print(answer)

Submission status: Accepted

Solution code:
def makelist(n, m):
    return [[0 for _ in range(m)] for _ in range(n)]

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


#
ans = int(1e18)
for pat in range(1<<D):
    score = G
    res = 0
    for i in range(1, D+1):
        if pat & (1<<(i-1)) > 0:
            res += p[i]
            score -= i * p[i] * 100 + c[i]
    
    for i in reversed(range(1, D+1)):
        if score <= 0:
            ans = min(ans, res)
            break
        if pat & (1<<(i-1)) == 0:
            now = (score + (i * 100) - 1) // (i * 100)
            if now <= p[i]:
                res += now
                ans = min(ans, res)
                break
            else:
                res += p[i]
                score -= i*100 * p[i]
print(ans)

Submission status: Accepted

Solution code:
def solve():
    inf = 1 << 60
    D, G = map(int, input().split())
    p = [0]
    c = [0]
    for i in range(D):
        pi, ci = map(int, input().split())
        p.append(pi)
        c.append(ci)
    sump = sum(p)
    # dp[i][j] = 100i点の問題までで、j問解いて得られる最大の点数
    dp = [[-inf for j in range(sump+1)] for i in range(D+1)]
    dp[0][0] = 0
    for d in range(1,D+1):
        for i in range(sump+1):
            for j in range(p[d]+1):
                if i - j >= 0:
                    dp[d][i] = max(dp[d][i], dp[d-1][i])
                    if dp[d-1][i-j] >= 0:
                        if j != p[d]:
                            dp[d][i] = max(dp[d][i], dp[d-1][i-j] + 100*d*j)
                        else:
                            dp[d][i] = max(dp[d][i], dp[d-1][i-j] + 100*d*j+c[d])
        #print(dp)
    for i in range(sump+1):
        if dp[D][i] >= G:
            return i

print(solve())

Submission status: Accepted

Solution code:
from copy import copy
D,G=map(int,input().split())
p=[]
c=[]
for i in range(D):
    a,b=map(int,input().split())
    p.append(a)
    c.append(b)
lst1=[]
lst2=[]
lst3=[]
def func1(l1,l2,l3,p,c,G):
    S=0
    n=0
    ind=0
    for i in range(len(l1)):
        S+=c[i]*l1[i]
        n+=p[i]*l1[i]
        S+=p[i]*100*(i+1)*l1[i]
    for i in range(len(l2)):
        if S>=G:
            break
        kazu=len(l2)-i
        a=l2[kazu-1]
        for j in range(1,a+1):
            if j==a:
                break
            S+=100*kazu
            n+=1
            if S>=G:
                break
    if S>=G:
        l3.append(n)
        l3.append(S)
    return 0
def func(l1,l2,l3,num,p,c,G):
    if num==0:
        func1(l1,l2,l3,p,c,G)
        return 0
    y1=copy(l2)
    y2=copy(l2)
    y2[len(l1)]=0
    x1=copy(l1)
    x1.append(0)
    x2=copy(l1)
    x2.append(1)
    num-=1
    return func(x1,y1,l3,num,p,c,G),func(x2,y2,l3,num,p,c,G)
func(lst1,p,lst3,D,p,c,G)
print(min(lst3))

Submission status: Accepted

Solution code:
import math

D, G = map(int, input().split())
prob = [list(map(int, input().split())) for i in range(D)]
tmp = 100*10

for i in range(1<<D):
    grade = 0
    cnt = 0
    judge = list(range(1, D+1))

    for j in range(D):
        if (i>>j & 1):
            grade += (100*(j+1)*prob[j][0] + prob[j][1])
            cnt += prob[j][0]
            judge[j] = 0

    if grade >= G and tmp > cnt:
        tmp = cnt
        
    num = prob[(max(judge))-1][0]

    if G > grade and num > math.ceil((G - grade)/(max(judge)*100)):
        cnt += math.ceil((G - grade)/(max(judge)*100)) 
        if tmp > cnt:
            tmp = cnt

print(tmp)

Submission status: Accepted

Solution code:
# /user/bin/python
# -*- coding: utf-8 -*-
import sys


D,G = list(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:
d,g=map(int,input().split())
PC=[list(map(int,input().split())) for i in range(d)]
P=list(map(lambda x:x[0],PC))
C=list(map(lambda x:x[1],PC))
ans=10**9
def dfs(cur,target):
  if cur==0:
    return 10**9
  cnt=min(target//(cur*100),P[cur-1]) #P[j]の一部を利用する/全部利用のどちらか小さい方選択
  tmp=(100*cur)*cnt
  if cnt==P[cur-1]:
    tmp+=C[cur-1]
  if tmp<target:
    cnt+=dfs(cur-1,target-tmp)       #減らした値でdfs実行
  return min(cnt,dfs(cur-1,target))
print(dfs(d,g))

Submission status: Accepted

Solution code:
import sys
input=sys.stdin.readline
d,g=map(int,input().split())
ls=[list(map(int,input().split())) for i in range(d)]
P=list(map(lambda x:x[0],ls))
C=list(map(lambda x:x[1],ls))

tmp=10**9
for i in range(1<<d):
  total=0
  num=0
  for j in range(d):
    if (i>>j)&1:
      total+=C[j]+P[j]*100*(j+1)
      num+=P[j]
  if total>=g:
    tmp=min(num,tmp)
  else:
    for j in range(d-1,-1,-1):
      if (i>>j)&1:
        continue
      for k in range(P[j]):
        if total>=g:
          break
        total+=100*(j+1)
        num+=1
    tmp=min(tmp,num)
print(tmp)

Submission status: Accepted

Solution code:
d,g=map(int,input().split())
ls=[list(map(int,input().split())) for i in range(d)]
P=list(map(lambda x:x[0],ls))
C=list(map(lambda x:x[1],ls))

tmp=10**9
for i in range(1<<d):
  total=0
  num=0
  for j in range(d):
    if (i>>j)&1:
      total+=C[j]+P[j]*100*(j+1)
      num+=P[j]
  if total>=g:
    tmp=min(num,tmp)
  else:
    for j in range(d-1,-1,-1):
      if (i>>j)&1:
        continue
      for k in range(P[j]):
        if total>=g:
          break
        total+=100*(j+1)
        num+=1
    tmp=min(tmp,num)
print(tmp)

Submission status: Accepted

Solution code:
d,g = map(int,input().split())
num = [list(map(int,input().split())) for i in range(d)]
lis = []
for i in range(1<<d):
    ind = [l for l in range(d)]
    cntT = 0
    cntA = 0
    for j in range(d):
        if (i>>j) & 1 == 1:
            cntT += num[j][0]
            cntA += num[j][0]*(j+1)* 100 + num[j][1]
            ind[j] = -1
    if cntA < g:
        m = 100*(max(ind)+1)
        s = min((g-cntA + m -1)//m,num[max(ind)][0])
        cntA += s*m
        cntT += s
    if cntA >= g:
        lis.append(cntT)

print(min(lis))

Submission status: Accepted

Solution code:
import math
length, goal = map(int, input().split(" "))
problems, bonus = [], []
for i in range(length):
    a, b = map(int, input().split(" "))
    problems.append(a)
    bonus.append(b)
problems = problems[::-1]
bonus = bonus[::-1]
answer = float("inf")
for bit in range(2 ** length):
    temp_ans = 0
    temp_sum = 0
    for i in range(length):
        temp_score = (length - i) * 100
        if bit & (1 << i):
            temp_ans += problems[i]
            temp_sum += bonus[i] + temp_score * problems[i]
    # print(bit, temp_ans, temp_sum)
    if temp_sum >= goal:
        answer = min(answer, temp_ans)
    else:
        for i in range(length):
            temp_score = (length - i) * 100
            if not(bit & (1 << i)):
                if temp_score * (problems[i] - 1) + temp_sum >= goal:
                    temp_ans += int(math.ceil((goal - temp_sum) / temp_score))
                    # print(math.ceil((goal - temp_sum) / temp_score))
                    answer = min(answer, temp_ans)
                    break
                else:
                    temp_ans += problems[i] - 1
                    temp_sum += temp_score * (problems[i] - 1)
        if temp_sum >= goal:
            answer = min(answer, temp_ans)
print(answer)

Submission status: Accepted

Solution code:
d,g=map(int,input().split())
s=[list(map(int,input().split()))for i in range(d)]
def dfs(d,g):
    if d==0:
        return 1e9
    l=min(g//(d*100),s[d-1][0])
    k=100*d*l
    if l==s[d-1][0]:
        k+=s[d-1][1]
    if k<g:
        l+=dfs(d-1,g-k)
    return min(l,dfs(d-1,g))
print(dfs(d,g))

Submission status: Accepted

Solution code:
def readln():
    return list(map(int, input().split()))


D, G = readln()
PC = [readln() for _ in range(D)]

ans = 10000

for i in range(1 << D):
    score = 0
    difficulty = -1  # バグにならないようにあとで注意
    n_problem = 0
    for j in range(D):
        if (i >> j) % 2:
            score += PC[j][1] + PC[j][0] * 100 * (j + 1)
            n_problem += PC[j][0]
        else:
            difficulty = max(difficulty, j)

    if difficulty == -1:  # すべてが−1となるとき全問取り終わっているということ
        ans = min(ans, n_problem)
        break

    for j in range(PC[difficulty][0]):
        # print(j)
        if score >= G:
            ans = min(ans, n_problem)
            # print(ans)
            break
        else:
            score += (difficulty+1) * 100
            n_problem += 1

print(ans)

Submission status: Accepted

Solution code:
import math
D,G = map(int,input().split())
L = []
for i in range(D):
  L.append(list(map(int,input().split())))
n = 2
ans = float('inf')
def Base_10_to_n(X, n):
  if (int(X/n)):
      return Base_10_to_n(int(X/n),n)+str(X%n)
  return str(X%n)
for i in range(2**D):
  K = Base_10_to_n(i, n).zfill(D)
  S = 0
  sub = 0
  for j in range(D):
    if K[j] == '1':
      S += L[j][0]*100*(j+1)+L[j][1]
      sub += L[j][0]
  if S >= G:
    if sub <= ans:
      ans = sub
  else:
    cnt = 0
    for l in range(D):
      if cnt == 0:  
        if K[D-l-1] == '0':
          cnt = 1
          if G-S <= L[D-l-1][0]*100*(D-l)+L[D-l-1][1]:
            if G-S > L[D-l-1][0]*100*(D-l):
              if ans >= sub+L[D-l-1][0]:
                ans = sub+L[D-l-1][0]
            else:
              if ans >= sub+math.ceil((G-S)/(100*(D-l))):
                ans = sub+math.ceil((G-S)/(100*(D-l)))
print(ans)

Submission status: Accepted

Solution code:
import math

d,gg = map(int,input().split())

p,c = [],[]

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

ans = 1145141919
for i in range(1 << d):
    g = gg
    cnt = 0
    sum = 0
    for j in range(d):
        if (1 << j) & (i):
            sum += (p[j]*(1+j)*100+c[j])
            cnt += p[j]
    
    g -= sum
    if (g <= 0) : 
        ans = min(ans,cnt)
        continue
    for j in list(reversed(range(d))):
        if (1 << j) & (i) == 0:
            aa = math.ceil(g/((1+j)*100))
            g -= ((1+j)*100)*min(aa,p[j]-1)
            cnt += min(aa,p[j]-1)
            break
    if (g <= 0) : ans = min(ans,cnt)

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

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:
a,b = map(int,input().split())

c = []

for i in range(a):
	c.append(list(map(int,input().split())))

ans = float('inf')

for i in range(1<<a):
	sc = 0
	co = 0
	for j in range(a):
		if i & (1<<j):
			sc += c[j][0]*(j+1)*100 + c[j][1]
			co += c[j][0]
	if sc >= b:
		ans = min(ans,co)
	else:
		for j in range(a)[::-1]:
			if i &(1<<j):
				continue
			else:
				for k in range(c[j][0]):
					sc += 100*(j+1)
					co += 1
					if sc >= b:
						break
				if sc >= b:
					break
		ans = min(ans,co)

print(ans)

Submission status: Accepted

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

def solve(index,total):
    res=0
    g=0
    for i in reversed(range(D)):
        if i in index:
            x=(pc[i][0]-1)*(i+1)*100
            if x<total:
                total-=x
                res+=pc[i][0]-1
            elif x==total:
                res+=pc[i][0]-1
                g=1
                break
            else:
                res+=(pc[i][0]-1)-(x-total)//((i+1)*100)
                g=1
                break
    if g==1:
        return res
    else:
        return 10**20

for i in range(2**D):
    f=0
    index=[]
    total=0
    problem=0
    while 1<<f <= i:
        if i & 1<<f:
            index.append(f)
        f+=1
    for a in reversed(range(D)):
        if not(a in index):
            total+=pc[a][0]*(a+1)*100+pc[a][1]
            problem+=pc[a][0]
    if total<G:
        total=G-total
        ans.append(problem+solve(index,total))
    else:
        ans.append(problem)
print(min(ans))

Submission status: Accepted

Solution code:
# itertools.product()でお手軽bit全探索
from itertools import product
D, G = map(int, input().split())
Problems_info = {}
Problems = []
Bonus = []
for i in range(D):
    p, c = map(int, input().split())
    Problems_info[i] = p
    Problems += [100 * (i + 1)] * p
    Bonus.append(c)


# 点数が高い順にソート
Problems.sort(reverse=True)

ans = float('inf')
# bit全探索
for bs in product([0, 1], repeat=D):
    tmp_ans = 0  # これまでに解いた問題数を管理
    tmp_score = 0  # これまでの得点を管理
    solved_point = set()  # すでに解いた点数帯を管理するための集合

    for i in range(D):
        # ボーナスをとるなら
        if bs[i]:
            tmp_score += Bonus[i]
            tmp_score += Problems_info[i] * 100 * (i + 1)
            tmp_ans += Problems_info[i]
            solved_point.add(100 * (i + 1))

    for point in Problems:
        if tmp_score >= G:
            ans = min(ans, tmp_ans)
            break

        # ボーナスを未取得なら使える
        if point not in solved_point:
            tmp_ans += 1
            tmp_score += point

print(ans)

Submission status: Accepted

Solution code:
D, G = map(int, input().split())
Problems_info = {}
Problems = []
Bonus = []
for i in range(D):
    p, c = map(int, input().split())
    Problems_info[i] = p
    Problems += [100 * (i + 1)] * p
    Bonus.append(c)


# 点数が高い順にソート
Problems.sort(reverse=True)

ans = float('inf')
# bit全探索
for bs in range(2 ** D):
    tmp_ans = 0  # これまでに解いた問題数を管理
    tmp_score = 0  # これまでの得点を管理
    solved_point = set()  # すでに解いた点数帯を管理するための集合

    for i in range(D):
        # ボーナスをとるなら
        if (bs >> i) & 1:
            tmp_score += Bonus[i]
            tmp_score += Problems_info[i] * 100 * (i + 1)
            tmp_ans += Problems_info[i]
            solved_point.add(100 * (i + 1))

    for point in Problems:
        if tmp_score >= G:
            ans = min(ans, tmp_ans)
            break

        # ボーナスを未取得なら使える
        if point not in solved_point:
            tmp_ans += 1
            tmp_score += point

print(ans)

Submission status: Accepted

Solution code:
def solve(problem,l):
    re = []
    for i in range(len(l)):
        if i == problem:
            re.append(l[i] + 1)
        else:
            re.append(l[i])
    return re



D,G = (int(i) for i in input().split())  
p = []
c = []
for _ in range(D):
    p_t,c_t =  (int(i) for i in input().split())
    p.append(p_t)
    c.append(c_t)

state = []
for _ in range(10100):
    state.append([0] * (D + 1))

i = 0
for j in range(D):
    point = state[i][-1]
    if p[j] > state[i][j]:
        point += 100 * (j + 1) * (p[j] - state[i][j])
        point += c[j]

        if state[i + (p[j] - state[i][j])][-1] < point:
            new_state = state[i] 
            for _ in range(p[j] - state[i][j]):
                new_state = solve(j,new_state)
            state[i + (p[j] - state[i][j])] = new_state
            state[i + (p[j] - state[i][j])][-1] = point
i += 1
while(True):
     #最後だけ取れる得点
    problem = 0
    for j in range(D):
        point = state[i-1][-1]
        if p[j] > state[i-1][j]:
            point += 100 * (j + 1)
            if p[j] - state[i-1][j] == 1:
                point += c[j]

        if state[i][-1] < point:
            state[i] = solve(j,state[i-1])
            state[i][-1] = point
    #print(state[0:10])
    for j in range(D):
        point = state[i][-1]
        if p[j] > state[i][j]:
            point += 100 * (j + 1) * (p[j] - state[i][j])
            point += c[j]

            if state[i + (p[j] - state[i][j])][-1] < point:
                new_state = state[i] 
                for _ in range(p[j] - state[i][j]):
                    new_state = solve(j,new_state)
                state[i + (p[j] - state[i][j])] = new_state
                state[i + (p[j] - state[i][j])][-1] = point

    #print(state[0:10])
    if state[i][-1] >= G:
        #print(state)
        print(i)
        break
    i += 1

Submission status: Accepted

Solution code:
from itertools import product


D,G = map(int, input().split())
p = [0] * D
c = [0] * D

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


#print(p)
#print(c)

states = list(product([i for i in range(2)], repeat=D))

#print(states)

res = float('inf')

for state in states:
    score = 0
    num = 0

    for i in range(D):
        if state[i] == 1:
            score += p[i] * (i+1) * 100 + c[i]
            num += p[i]

    #print('num1',num)

    if score < G:
        for i in range(D):
            if state[D-i-1] != 1 and score < G:
                add_count = 0
                while score < G and add_count < p[D-i-1]:
                    add_count += 1
                    num += 1
                    score += (D-i) * 100

        if score < G:
            num = float('inf')
    
    #print('num2',num)
    res = min(res,num)

print(res)

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)


def bit_search(A):
    result = []
    for i in range(1 << len(A)):
        output = []
        for j in range(len(A)):
            if ((i >> j) & 1) == 1:
                output.append(A[j])
        result.append(output)

    return result


search_list = bit_search(list(range(D)))
ans = 10 ** 9
for complete_list in search_list:
    score = sum([100 * (i + 1) * P[i] + C[i] for i in complete_list])
    count = sum([P[i] for i in complete_list])
    if score >= G:
        ans = min(ans, count)
    else:
        j_max = max([i for i in range(D) if i not in complete_list])
        required = -(-(G - score) // (100 * (j_max + 1)))
        if required < P[j_max]:
            count += required
            ans = min(ans, count)
print(ans)

Submission status: Accepted

Solution code:
import itertools
import math

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

ls = []
for i in itertools.product([0, 1], repeat=D):
    sum = 0
    ans = 0
    for j, x in enumerate(i):
        if x == 1:
            sum += c[j] + (100*(j+1))*p[j]
            ans += p[j]
    if sum >= G:
        ls.append(ans)
    else:
        for j, x in enumerate(i[::-1]):
            if x != 1:
                if math.ceil((G-sum)/(100*(D-j))) <= p[D-1-j] - 1:
                    ans += math.ceil((G-sum)/(100*(D-j)))
                    ls.append(ans)
                    break
                else:
                    sum += (100*(D-j))*(p[D-1-j] - 1)
                    ans += p[D-1-j] - 1
print(min(ls))

Submission status: Accepted

Solution code:
#encoding:utf-8

# encoding:utf-8
import copy
import numpy as np
import random

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)

completed = []
for i in range(d):
    score = P[i]*(i+1)*100+C[i]
    completed.append(score)

def to_digital(num):
    dig = [0]*d
    for i in range(d):
        dig[i]=num%2
        num //= 2
    return dig

ans = 10**9
for i in range(2**d):
    digital = to_digital(i)
    score = 0
    count = 0
    for j in range(d):
        if digital[j]:
            score += completed[j]
            count += P[j]

    for j in range(d)[::-1]:
        if digital[j]==0:
            for k in range(P[j]-1):
                if g<=score:
                    break
                else:
                    count += 1
                    score += 100*(j+1)
        if g<=score:
            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)]

min_count = 10**18
for i in range(1<<D):
    # print(bin(i)[2:])
    count = 0
    point = 0
    top_zero = None
    for j, (p, c) in enumerate(PC):
        if (i>>j)%2:
            count += p
            point += 100*(j+1)*p + c
        else:
            top_zero = j
    if top_zero != None:
        for j in range(PC[top_zero][0]-1):
            # print(j, top_zero, point)
            if point >= G:
                break
            point += 100*(top_zero+1)
            count += 1
    # print("count:", count)
    if point >= G:
        min_count = min(min_count, count)

print(min_count)

Submission status: Accepted

Solution code:
d, g = map(int, input().split())
pc = [list(map(int, input().split())) for _ in range(d)]
ans = 1000
for i in range(1 << d):
    score = 0
    num = 0
    rest = 0
    for j in range(d):
        if ((i >> j) & 1) == 1:
            score += pc[j][0]*100*(j+1) + pc[j][1]
            num += pc[j][0]
        else:
            rest = j
    if score < g:
        need = (g-score-1)//(100*(rest+1))+1
        if need > pc[rest][0]-1:
            continue
        else:
            num += need
    ans = min(ans, num)
print(ans)

Submission status: Accepted

Solution code:
D,G=map(int,input().split())
PC=[0]+[list(map(int,input().split()))for i in range(D)]
def f(p,c):
    if p==0:
        return 10**9
    m=min(c//(p*100),PC[p][0])
    s=100*p*m
    if m==PC[p][0]:
        s+=PC[p][1]
    if s<c:
        m+=f(p-1,c-s)
    return min(m,f(p-1,c))
print(f(D,G))

Submission status: Accepted

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

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

ans = 10**9+7
result = []
for i in range(1 << D):
  point = 0
  cnt = 0
  tmp = []
  for j in range(D):
    if(((i >> j) & 1) == 1):
      point += PC[j][0] * 100 * (j+1) + PC[j][1]
      cnt += PC[j][0]
    else:
      tmp.append(j)
  if(point < G):
    r = G - point
    k = tmp[-1]
    if((PC[k][0]-1) * (k+1) * 100 < r):
      continue
    cnt += -(-r // (100 * (k + 1)))
  ans = min(ans, cnt)
print(ans)

Submission status: Accepted

Solution code:
import math
D, G = [int(i) for i in input().split()]
data_ls = list()
for i in range(D):
    data_ls.append([int(i) for i in input().split()])
ps, cs = zip(*data_ls)

def search(cnt, sum, flg, rest_max):
    if sum >= G:
        return cnt
    if flg == len(data_ls):
        if sum + (ps[rest_max] - 1) * 100 * (rest_max + 1) >= G:
            return cnt + math.ceil((G - sum) / (100 * (rest_max+1)))
        else:
            return 1e9
    cnt = min(search(cnt + ps[flg], sum + (ps[flg] * 100 * (flg+1) + cs[flg]), flg + 1, rest_max),
              search(cnt, sum, flg + 1, flg))
    return cnt

print(search(0,0,0,0))

Submission status: Accepted

Solution code:
import math
D,G = map(int,input().split())
pc = [list(map(int,input().split())) for i in range(D)]
perf = [(pc[i][0]*100*(i+1)+pc[i][1]) for i in range(D)]
bitD=2**D - 1
MIN=0
for i in range(D):
    MIN+=pc[i][0]
for i in range(bitD):
    b = bin(i)
    b = b.lstrip("0b")
    blen=len(b)
    j=0
    for j in range(D-blen):
        b="0"+b
    blist=list(b)
    k=0
    flag=0
    briflag=0
    count=0
    d=0
    for k in range(D):
        I=D-1-k
        if blist[k]=="1":
            d+=perf[I]
            count+=pc[I][0]
            if G < d:
                briflag=1
                break
        else:
            if flag == 0:
                flag+=1
                zanindex = I
            else:
                pass
    if briflag == 1:
        MIN=min(count,MIN)
    else:
        zan = math.ceil((G-d)/(100*(zanindex+1)))
        if zan <= pc[zanindex][0]:
        	count+=zan
        	MIN=min(count,MIN)
        else:
          pass
print(MIN)

Submission status: Accepted

Solution code:
D,G=map(int,input().split())
#[1問当たりの点数,問題数,ﾎﾞｰﾅｽ含むDの点数]
L=[]

for i in range(10):
    if i<D:
        p,c=map(int,input().split())
        L.append([100*(i+1),p,100*(i+1)*p+c])
    else:
        L.append([100*(i+1),0,0])
L.sort(reverse=True)
#print(L)

ans=100000000
for i in range(2**D):
    N=i
    Sco=0
    Prb=0
    l=[0 for i in range(10)]
    for j in range(10):
        if N//(2**(9-j))==1:
            Sco+=L[j][2]
            Prb+=L[j][1]
            l[j]=1
        N%=(2**(9-j))
    if Sco>=G: 
        if ans>Prb:
            ans=Prb
    else:
        for k in range(10):
            if l[k]==0:
                if (L[k][1]-1)*(L[k][0])+Sco>=G:
                    if (G-Sco)%(L[k][0])==0:
                        Prb+=((G-Sco)//(L[k][0]))
                        if ans>Prb:
                            ans=Prb
                    else:
                        Prb+=((G-Sco)//(L[k][0]))+1
                        if ans>Prb:
                            ans=Prb
print(ans)