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())
pc = []
for i in range(D):
    p,c = map(int,input().split())
    pc.append([i+1,p,c])
pc.sort(reverse = True)
ansc = []
for i in range(2**D):
    count = 0
    sumb = 0
    pc2 = []
    for j in range(D):
        if (i >> j) & 1 == 1:
            sumb += 100*pc[j][0]*pc[j][1] + pc[j][2]
            count += pc[j][1]
        else:
            pc2.append(pc[j])
    pc2 = sorted(pc2,reverse = True)
    c2 = 0
    while sumb < G:
        sumb += 100*pc2[0][0]
        count += 1
        c2 += 1
        if c2 == pc2[0][1]:
            count = 10**9
            break
    ansc.append(count)
print(min(ansc))

Submission status: Accepted

Solution code:
import math
d, g = map(int, input().split())
lst = [list(map(int, input().split())) for _ in range(d)]
for i in range(d):
    lst[i].append((i+1) * 100)
    lst[i].append((i+1) * 100 * lst[i][0] + lst[i][1])

def make_bit(n, d):
    bit = [0] * d
    for i in range(d):
        bit[i] += n % 2
        n //= 2
    return bit

min_count = 10 ** 9 + 7
for n in range(2 ** d):
    bit = make_bit(n, d)
    #print(bit)
    now = 0
    count = 0
    for i in range(d):
        if bit[i] == 1:
            now += lst[i][3]
            count += lst[i][0]
    if now >= g:
        min_count = min(min_count, count)
    else:
        for i in range(d-1, -1, -1):
            if bit[i] == 0:
                c = math.ceil((g - now) / lst[i][2])
                if c < lst[i][0]:
                    count += c
                    min_count = min(min_count, count)
                break
print(min_count)

Submission status: Accepted

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

ans = 0

for i in range(2**D):
    point = 0
    count = 0

    for j in range(D):
        if(i>>j)&1: # コンプリート
            point += X[j][0]*(j+1)*100 + X[j][1]
            count += X[j][0]
    
    if G > point:
        for k in range(D-1,-1,-1):
            if(i>>k)&1 == 0:
                if (G - point) <= X[k][0]*(k+1)*100:
                    count += (G - point - 1) // ((k+1)*100)  + 1
                    break
                else:
                    count = 10**5 # とりあえず大きい数
                    break
    
    if ans == 0 or count < ans:
        ans = count

print(ans)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
d, g = map(int, input().split())
pc = []
for i in range(d):
    p, c = map(int, input().split())
    pc.append([p, c // 100])
g = g // 100
ans = 1000
for i in range(2 ** d):
    rem = g
    cost = 0
    for j in reversed(range(d)):
        if ((i >> j) & 1):
            p, c = pc[j]
            rem -= c + p * (j + 1)
            cost += p
    for j in reversed(range(d)):
        if  not ((i >> j) & 1):
            p, c = pc[j]
            p -= 1
            if rem >= p * (j + 1):
                rem -= p * (j + 1)
                cost += p
            else:
                while rem > 0:
                    rem -= j +1
                    cost += 1
                break
    if rem <= 0:
        ans = min(cost, ans)
print(ans)

Submission status: Accepted

Solution code:
# coding: utf-8


def solve(*args: str) -> str:
    d, g = map(int, args[0].split())
    pc = [tuple(map(int, a.split())) for a in args[1:]]
    inf = 10**5

    count = inf
    for b in range(2**d):
        score, cnt = 0, 0

        for i in range(d):
            p, c = pc[i]
            if b >> i & 1:
                score += p*100*(i+1)+c
                cnt += p

        if score < g:
            for i in reversed(range(d)):
                if b >> i & 1:
                    continue
                else:
                    p, c = pc[i]
                    j = 0
                    while score < g and j < p:
                        score += 100*(i+1)
                        cnt += 1
                        j += 1

                    if j == p:
                        score += c

        count = min(count, cnt)

    return str(count)


if __name__ == "__main__":
    print(solve(*(open(0).read().splitlines())))

Submission status: Accepted

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

import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 18
MOD = 10 ** 9 + 7

D, G = MAP()
G //= 100
DC = []
MAX = 0
for i in range(D):
    d, c = MAP()
    c //= 100
    MAX += d
    DC.append((d, c))

# dp[i][j] := i点問題まで見て、合計j問解いた状態でのスコア最大値
dp = list2d(D+1, MAX+1, 0)
for i in range(D):
    d, c = DC[i]
    for j in range(MAX+1):
        for k in range(d+1):
            if j+k > MAX:
                break
            if k == d:
                # 全完ボーナス付
                dp[i+1][j+k] = max(dp[i+1][j+k], dp[i][j] + (i+1) * k + c)
            else:
                # 通常
                dp[i+1][j+k] = max(dp[i+1][j+k], dp[i][j] + (i+1) * k)

# スコアがG以上となる最小の解いた問題数を出力
for j in range(MAX+1):
    if dp[D][j] >= G:
        print(j)
        break

Submission status: Accepted

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

res = 1000
for i in range(1 << d):
  s = 0
  c = 0
  for j in range(d):
    if i >> j & 1:
      s += 100 * (j + 1) * lst[j][0] + lst[j][1]
      c += lst[j][0]
    else:
      last = j
  if s < g:
    s100 = 100 * (last + 1)
    need = (g - s - 1) // s100 + 1
    if need > lst[last][0]:
      continue
    c += need
  if res > c:
    res = c
print(res)

Submission status: Accepted

Solution code:
D,G = map(int,input().split())
X = [list(map(int,input().split())) for _ in range(D)]
ans = 0
 
for i in range(2**D):
	point = 0
	count = 0
	for j in range(D):
		if (i>>j)&1:
			point += 100*(j+1)*X[j][0]+X[j][1]
			count += X[j][0]
	if 	G > point:
		for k in range(D)[::-1]:
			if (i>>k)&1==0:
				if (G-point) <= 100*(k+1)*(X[k][0]):
					count += (G-point-1) // (100*(k+1)) +1
					break
				else:
					count = 10**5
					break
	if ans == 0 or count < ans:
		ans = count
 
print(ans)

Submission status: Accepted

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

problems = []
for i in range(1, d + 1):
    num, bonus = map(int, input().split())
    point = i * 100
    problems.append([point, num, bonus])

ans = []
for mask in range(2 ** d):
    score = 0
    count = 0
    target = 0
    for bit in range(d):
        if (mask >> bit) & 1:
            point, num, bonus = problems[bit]
            score += (point * num) + bonus
            count += num
        else:
            target = bit
            
    if score >= g:
        ans.append(count)
    else:
        point, num, bonus = problems[target]
        delta = g - score
        add = delta // point + bool(delta % point)
        if add < num:
            ans.append(count + add)
        else:
            continue

print(min(ans))

Submission status: Accepted

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

for i in range(2**D):
	point = 0
	count = 0
	for j in range(D):
		if (i>>j)&1:
			point += 100*(j+1)*X[j][0]+X[j][1]
			count += X[j][0]
	if 	G > point:
		for k in range(D)[::-1]:
			if (i>>k)&1==0:
				if (G-point) <= 100*(k+1)*(X[k][0]-1):
					count += -((-(G-point)) // (100*(k+1)))
					break
				else:
					count = 10**5
					break
	if ans == 0 or count < ans:
		ans = count

print(ans)

Submission status: Accepted

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

problems = []
for i in range(1, d+1):
    num, bonus = map(int, input().split())
    point = i * 100
    problems.append([point, num, bonus])


ans = []
for mask in range(2**d):
    score = 0
    count = 0
    target = 0
    for bit in range(d):
        if (mask >> bit) & 1:  #全て解く
            point, num, bonus = problems[bit]
            score += (point*num) + bonus
            count += num
        else:
            target = bit

    if score >= goal:
        ans.append(count)
    else:
        point, num, bonus = problems[target]
        delta = goal - score
        add = delta//point + bool(delta%point)
        if add < num:
            ans.append(count+add)
        else:
            continue

print(min(ans))

Submission status: Accepted

Solution code:
d,g= map(int, input().split())
x = [list(map(int, input().split())) for i in range(d)]
ans2=float('inf')

for i in range(2**d):
    v=[0]*d
    ans=0
    ans1=0
    for j in range(d):
        if (i>>j)&1==1:
            ans+=(x[j][0]*100*(j+1))+x[j][1]
            ans1+=x[j][0]
            v[j]=1


    if ans<g:
        for k in range(d):
            if v[d-k-1]==0:
                if g-ans<=(x[d-k-1][0]-1)*100*(d-k):
                    w=-(-(g-ans)//(100*(d-k)))

                    ans2=min(ans2,ans1+w)
                else:
                    break
    else:
        ans2=min(ans2,ans1)
print(ans2)

Submission status: Accepted

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

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


ans = 1e9
for mask in range(1<<D):
    s = 0
    num = 0
    rest_mask = -1
    for i in range(D):
        if mask >> i & 1:
            s += 100 * (i+1) * p[i] + c[i]
            num += p[i]
        else:
            rest_mask = i
    if s < G:
        s1 = 100 * (rest_mask + 1)
        need = (G - s + s1 -1) // s1
        if need >= p[rest_mask]:
            continue
        num += need
    ans = min(ans, num)

print(ans)

Submission status: Accepted

Solution code:
import math

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 = 1e9
for mask in range(1 << D):
  s, num, rest_max = 0, 0, -1
  for i in range(D):
    if mask >> i & 1:
      s += 100 * (i+1) * p[i] + c[i]
      num += p[i] # 問題数
    else:
      rest_max = i # 完全に解いた問題以外のうち最大点数の問題

  if s < G: # Gに満たない
    s1 = 100 * (rest_max + 1)
    need = math.ceil((G - s) / s1)     
    if need >= p[rest_max]:
      continue # 完全に解く＋中途半端に解くがG点に満たない
    num += need
  
  ans = min(ans, num)
    
print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python
# coding: utf-8

# In[1]:


import heapq


# In[2]:


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


# In[3]:


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


# In[4]:


total = [100*(i+1)*p[i] + c[i] for i in range(D)]
total


# In[8]:


ans = []
for i in range(2 ** D):
#     print(i)
    point = 0
    mondaisu = 0
    nokori = []
    for j in range(D):
        if i % 2 == 1:
            point += total[j]
            mondaisu += p[j]
        else:
            heapq.heappush(nokori, (-100 * (j+1) * (p[j]-1), j))
        i //= 2
#     print(point, mondaisu, nokori)
    if point >= G:
        ans.append(mondaisu)
    else:
        po, ind = heapq.heappop(nokori)
        if point + (-po) >= G:
            ans.append(mondaisu + (G-point+100*(ind+1)-1)//(100*(ind+1)) )
#             print(G - point, 100 * (ind+1))
        


# In[9]:


ans


# In[10]:


print(min(ans))


# In[ ]:





# In[ ]:

Submission status: Accepted

Solution code:
d,g=map(int,input().split())
p=[0]
c=[0]
p_num=0
for i in range(d):
    P,C=map(int,input().split())
    p_num+=P
    p.append(P)
    c.append(C)
dp=[0]*(p_num+1)
for j in range(1,d+1):
    for k in range(1,p[j]+1):
        if k==1:
            t_dp=dp[:]
            
        if k==p[j]:
            cc=100*j*k+c[j]
        else:
            cc=100*j*k
            
        for l in range(1,p_num+1):
            if l>=k:
                dp[l]=max(dp[l],t_dp[l-k]+cc)                
for i in range(p_num+1):
    if dp[i]>=g:
        print(i)
        break

Submission status: Accepted

Solution code:
import sys

def main():
    sum=0
    ans=0
    ansc=0
    D,G = map(int,input().split())

    lis=[]
    for x in range(D):
        P,C = map(int,input().split())
        lis.append([P,C])

    op_cnt = D

    for i in range(2 ** op_cnt):
        for j in range(op_cnt):
            if((i>>j) & 1 and i!=0):
                for k in range(1, lis[j][0]+1):
                    sum+=(100*(j+1))
                    ansc+=1
                    if(k==lis[j][0]):
                        sum+=lis[j][1]
                    if(sum>=G):
                        break


        if(sum<G):
            for lef in reversed(range(0, op_cnt)):
                if(~(i>>lef) & 1 and lis[lef][0] != 1):
                    for l in range(1,lis[lef][0]+1):
                        if(sum>=G):
                            break
                        sum+=(100*(lef+1))
                        ansc+=1


        if(ans>=ansc or ans==0):
            ans=ansc

        ansc=0
        sum=0

    print(ans)
main()

Submission status: Accepted

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

def dfs(i, g):
    #print("dfs({},{})".format(i, g))
    # 終了条件
    if i == 0:
        return 10 ** 9
    # 解く問題数
    c = min(g//(i*100), L[i][0])
    n = 100 * i *c
    # 全問といたらボーナス
    if c == L[i][0]:
        n += L[i][1]
    # 点数が足りない場合はその次の問題も考える
    if n < g:
        c += dfs(i-1, g-n)
    # その次の問題以降だけでも条件を満たせるか
    return min(c, dfs(i-1, g))

print(dfs(D, G))

Submission status: Accepted

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

ans = 10**9


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

for i in range(2**D):
    t = 0
    p_ = 0
    tyu = -1
    for j in range(D):
        if i & (1 << j):
            t += p[j]*100*(j+1) + c[j]
            p_ += p[j]
        else:
            if tyu < j:
                tyu = j



    if t >= G:
        ans = min(ans, p_)
    
    else:
        if tyu != -1:
            for j in range(p[tyu]-1):
                t += 100 * (tyu+1)
                p_ += 1
                if t >= G:
                    ans = min(ans, p_)

    
print(ans)

Submission status: Accepted

Solution code:
import itertools

def main():
    D,G=map(int,input().split())
    P=[]
    C=[]
    PC = []
    for i in range(D):
        p,c=map(int,input().split())
        PC.append([100*(i+1),p,c,(100*(i+1)*p+c)/p])
        P.append(p)
        C.append(c)
    res = 100000
    for i in itertools.permutations(range(D)):
        tp = G
        tn = 0
        for j in i:
            if tp <= (j+1)*100*P[j]:
                tn += (tp+(j+1)*100-1) // ((j+1)*100)
                break
            else:
                tp -= (j+1)*100*P[j]
                tn += P[j]
                tp -= C[j]
                if tp <= 0:break
        res = min(res,tn)

    return res

print(main())

Submission status: Accepted

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

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

ans = 1e9
for mask in range(1 << D):
    s = 0
    num = 0
    rest_max = -1
    for i in range(D):
        if (mask >> i) & 1:
            s += 100 * (i+1) * p[i] + c[i]
            num += p[i]
        else:
            rest_max = i
    
    if s < G:
        s1 = 100 * (rest_max + 1)
        need = ( G - s + s1 - 1) // s1
        if need >= p[rest_max]:
            continue
        num += need
    ans = min(ans, num)

print(ans)

Submission status: Accepted

Solution code:
# https://atcoder.jp/contests/abc104/tasks/abc104_c

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

p = []  # 各点数台の問題数のリスト
c = []  # 各点数台のコンプリートボーナス

# 各点数台を、完全に解くかどうかのリスト　1問も解かないとして初期化
solve_completely_list = [False] * D

# 入力処理
for d in range(D):
    p_i, c_i = map(int, input().split())
    p.append(p_i)
    c.append(c_i)


def dfs(i, solve_completely_list, completed_amount_list):
    if i >= D:
        is_larger_than_G = False    # フラグ初期化
        # total_score計算
        total_score = 0
        completed_amount = 0
        for d in range(D):
            if solve_completely_list[d]:
                total_score += (d+1) * 100 * p[d] + c[d]
                completed_amount += p[d]


        # total_scoreがGより小さいとき
        # Gより大きくなるまで、一番大きい配点を足す
        # 一番大きい配点をp-1個足してもGより小さい場合、諦めて他の枝に移る
        if total_score < G:
            # solve_completely_list[D]がTrueのときは、(D-1) * 100を最大の配点とする
            # solve_completely_list[i]がFalseであるiのうち最大のiの配点を使う
            max_d = -1
            for d_i in reversed(range(D)):
                if solve_completely_list[d_i] == False:
                    max_d = d_i
                    break
            # 多分ありえないけど一応
            if max_d == -1:
                return

            for p_d in range(p[max_d] - 1):
                total_score += (max_d + 1) * 100
                completed_amount += 1
                if total_score >= G:
                    is_larger_than_G = True
                    break
        else:
            is_larger_than_G = True
        
        if is_larger_than_G:
            completed_amount_list.append(completed_amount)
        return
    

    # 完全に解く(100i 点の問題を pi 問解く)場合
    solve_completely_list[i] = True
    dfs(i + 1, solve_completely_list, completed_amount_list)

    # 1問も解かない場合
    solve_completely_list[i] = False
    dfs(i + 1, solve_completely_list, completed_amount_list)

completed_amount_list = []    # 回答した数のリスト
dfs(0, solve_completely_list, completed_amount_list)
print(min(completed_amount_list))

Submission status: Accepted

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

p = []
c = []
ans = []
for _ in range(D):
	p_dash,c_dash = map(int,input().split())
	p.append(p_dash)
	c.append(c_dash)

for i in range(2**D):
	l = [0]*D
	score = 0
	count = 0
	for j in range(D):
		if i & (1<<j):
			l[j] = 1

	for a,b,num in zip(l,p,range(1,D+1)):
		if a == 1:
			score += b*100*num
			score += c[num-1]
			count += b

	if score < G:
		index = D
		for bit in l[::-1]:
			index -= 1
			if bit == 0:
				break
		tmp = 0
		while True:
			tmp += 1
			if tmp > p[index]:
				break
			if score + tmp*100*(index+1) >= G:
				ans.append(count+tmp)
				break
	else:
		ans.append(count)

print(min(ans))

Submission status: Accepted

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

for i in range(d):
    p,c = map(int, input().split())
    pc.append([p,c])
ans = 10**7
for i in range(2**d):
    tmp = 0
    cnt = 0
    r = list(range(1,d+1))
    for j in range(d):
        if(i>>j)&1==1:
            tmp += pc[j][0]*100*(j+1)+pc[j][1]
            cnt += pc[j][0]
            r.remove(j+1)
    if tmp<g:
        plus = max(r)
        n = min(pc[plus-1][0],-(-(g-tmp)//(plus*100)))
        cnt +=n
        tmp += n*plus*100
    if tmp>= g:
        ans = min(ans,cnt)
print(ans)

Submission status: Accepted

Solution code:
d, g = map(int, input().split())
p = [[i*100] + list(map(int, input().split()))
     for i in range(1, d+1)]
p = list(map(lambda x: x + [x[0] * x[1] + x[2]], p))

res = 1001
for bit in range(2**d):
    score = 0
    cnt = 0
    zero = 0
    for i in range(d):
        if bit & (1 << i):
            score += p[i][3]
            cnt += p[i][1]
        else:
            zero = i
    if score >= g:
        res = min(res, cnt)
    else:
        remaining = (g - score + p[zero][0]-1) // p[zero][0]
        if remaining < p[zero][1]:
            res = min(res, cnt+remaining)

print(res)

Submission status: Accepted

Solution code:
# 以下ペースト可
D, G = [int(item) for item in input().split()]

comp_bounas_list = [[int(item) for item in input().split()] for _ in range(D)]

comp_all = []

for i in range(2**D):
    temp = []
    for j in range(D):
        if ((i >> j) & 1) == 1:
            temp.append(1)
        else:
            temp.append(0)
    comp_all.append(temp)

# print(comp_bounas_list)
# print(comp_all)

full_num_list = [item[0] for item in comp_bounas_list]

each_comp_point = []
for i, item in enumerate(comp_bounas_list):
    each_comp_point.append((i+1)*100*item[0]+item[1])

# print(full_num_list)
# print(each_comp_point)


temp_point_list = []

for each_pattern in comp_all:
    temp_num = 0
    temp_point = 0
    for j, item in enumerate(each_pattern):
            if item:
                temp_num += full_num_list[j]
                temp_point += each_comp_point[j]

    temp_point_list.append([temp_num, temp_point, each_pattern]) 

# print(temp_point_list)

# overの物を解候補にリスト化する
over_list = [item for item in temp_point_list if item[1] >= G]

# print(over_list)
# 全bitが立っている最大値はターゲットを超えているため必ず値を持つ
over_combo = min(over_list, key = lambda x:x[0])
# print(over_combo)

# underのものを解候補にリスト化する
under_combo = [item for item in temp_point_list if item[1] < G]

# print(over_combo)
# print(under_combo)


temp_res_list = []
is_search = True

for temp_combo in under_combo:
    temp_bit_list = temp_combo[2]
    temp_res_point = temp_combo[1]
    temp_res_num = temp_combo[0]
    # print(temp_combo)

    # print(temp_bit_list)
    for j, item in reversed(list(enumerate(temp_bit_list))):
        for _ in range(1, comp_bounas_list[j][0]):
            # print(temp_res_point)
            if item==0:
                temp_res_point += (j+1)*100
                temp_res_num += 1

            if temp_res_point >= G:
                temp_res_list.append([temp_res_num, temp_res_point])
                break

# print(temp_res_list)
# きっかりコンプすれば必ずターゲットを超える場合、値を持たない場合がある。
# ダミーでres_candiに全bitの立った値を入れておく
if temp_res_list != []:
    res_candi = min(temp_res_list, key=lambda x:x[0])
else:
    res_candi = temp_point_list[-1]

if over_combo[0] <= res_candi[0]:
    print(over_combo[0])
else:
    print(res_candi[0])

Submission status: Accepted

Solution code:
D, G = [int(item) for item in input().split()]

comp_bounas_list = [[int(item) for item in input().split()] for _ in range(D)]

comp_all = []

for i in range(2**D):
    temp = []
    for j in range(D):
        if ((i >> j) & 1) == 1:
            temp.append(1)
        else:
            temp.append(0)
    comp_all.append(temp)

# print(comp_bounas_list)
# print(comp_all)

full_num_list = [item[0] for item in comp_bounas_list]

each_comp_point = []
for i, item in enumerate(comp_bounas_list):
    each_comp_point.append((i+1)*100*item[0]+item[1])

# print(full_num_list)
# print(each_comp_point)


temp_point_list = []

for each_pattern in comp_all:
    temp_num = 0
    temp_point = 0
    for j, item in enumerate(each_pattern):
            if item:
                temp_num += full_num_list[j]
                temp_point += each_comp_point[j]

    temp_point_list.append([temp_num, temp_point, each_pattern]) 

# print(temp_point_list)

# overの物を解候補にリスト化する
over_list = [item for item in temp_point_list if item[1] >= G]

# print(over_list)
over_combo = min(over_list, key = lambda x:x[0])
# print(over_combo)

# underのものを解候補にリスト化する
under_combo = [item for item in temp_point_list if item[1] < G]

# print(over_combo)
# print(under_combo)


temp_res_list = []
is_search = True

for temp_combo in under_combo:
    temp_bit_list = temp_combo[2]
    temp_res_point = temp_combo[1]
    temp_res_num = temp_combo[0]
    # print(temp_combo)

    # print(temp_bit_list)
    for j, item in reversed(list(enumerate(temp_bit_list))):
        for _ in range(1, comp_bounas_list[j][0]):
            # print(temp_res_point)
            if item==0:
                temp_res_point += (j+1)*100
                temp_res_num += 1

            if temp_res_point >= G:
                temp_res_list.append([temp_res_num, temp_res_point])
                break

# print(temp_res_list)

if temp_res_list != []:
    res_candi = min(temp_res_list, key=lambda x:x[0])
else:
    res_candi = temp_point_list[-1]

if over_combo[0] <= res_candi[0]:
    print(over_combo[0])
else:
    print( res_candi[0])

Submission status: Accepted

Solution code:
d, g = [int(x) for x in input().split()]
g //= 100
problems = {}
max = 0
for i in range(d):
  # num + comp
  problems[i + 1] = [int(x) for x in input().split()]
  max += problems[i + 1][0]

dp = {} # pt -> problem count
dp[0] = 0
for (point, p) in problems.items():
  tmp = list(dp.items())
  num = p[0]
  bonus = p[1] // 100
  for i in range(0, num):
    i += 1
    pt = point * i
    if i == num:
      pt += bonus
    for (k, v) in tmp:
      idx = k + pt
      if idx in dp:
        if dp[idx] > v + i:
          dp[idx] = v + i
      else:
        dp[idx] = v + i

ans = max
for i in dp:
  if i >= g:
    if ans > dp[i]:
      ans = dp[i]

print(ans)

Submission status: Accepted

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

# 十分大きい数を用意する
ans = float("inf")

# それぞれのランクの問題を「完全に解く」 or not -> 2^D通り
for bit in range(1 << D):
    score = 0
    solve = 0
    rest = set(range(1, D + 1))

    for i in range(D):
        # (i+1)番目の問題を完全に解いた場合
        if (bit>>i) & 1:
            # スコア = 基本スコア + コンプリートボーナス
            score += PC[i][0] * (i + 1) * 100 + PC[i][1]
            solve += PC[i][0]
            # 今回解いたランクの問題を削除
            rest.discard(i + 1)

    # 目標点に満たない場合、restの大きいものから順に解く
    if score < G:
        target = max(rest)
        n = min(PC[target - 1][0], -((score-G) // (target*100)))
        score += n * target * 100
        solve += n

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

print(ans)

Submission status: Accepted

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

def num2bi(x, k):
  #10進数xを2進数k桁(string)で出力
  out=format(x, '0'+str(k)+'b')
  return out
  
n=2**D
counter=sum(pc[i][0] for i in range(D))
for i in range(n):
  a=num2bi(i, D)
  c=0
  p=0
  for j in range(D):
    if a[j]=='1':
      p+=pc[j][0]*(j+1)*100+pc[j][1]
      c+=pc[j][0]
      
  if p<G:
    j=D
    while j>0 and p<G:
      j-=1
      if a[j]=='0':
        temp=(G-p)//(100*(j+1))
        if (G-p)%(100*(j+1))>0:
          temp+=1
          
        if temp<=pc[j][0]-1:
          p+=100*(j+1)*temp
          c+=temp
        else:
          p+=100*(j+1)*(pc[j][0]-1)
          c+=(pc[j][0]-1)
          
  if p>=G:
    counter=min(counter, c)
  
print(counter)

Submission status: Accepted

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

for i in range(D):
  score=0
  l=0
  for j in range(PC[i][0]-1):
    score += 100*(i+1)
    l += 1
    if score>=G and ans>l:
      ans=l

for i in range(1,2**D):
  score = 0
  l = 0
  for j,flag in enumerate( list(format(i,"b").zfill(D))[::-1] ):
    if flag=="1":
      score += PC[j][0]*100*(j+1) + PC[j][1]
      l += PC[j][0]
    else:
      k=j
    
  j=0
  while score<G and j<PC[k][0]-1:
    score+=100*(k+1)
    l+=1
    j+=1
  if score>=G and ans>l:
    ans=l
  
print(ans)

Submission status: Accepted

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

ans = sum([i[0] for i in pc])

for i in range(2**D):
    search_index = format(i, '0' + str(D) + 'b')
    complete_answered = [i for i, c in enumerate(search_index[::-1]) if c == '1']
    incomplete_answered = list(set(range(D)) - set(complete_answered))
    answered_number = 0
    remaining_score = G
    for j in complete_answered:
        answered_number += pc[j][0]
        remaining_score -= (100 * (j + 1) * pc[j][0] + pc[j][1])
    incomplete_answered = sorted(incomplete_answered, reverse=True)
    for j in incomplete_answered:
        question_number = pc[j][0]
        while remaining_score > 0:
            answered_number += 1
            remaining_score -= 100 * (j + 1)
            question_number -= 1
            if question_number <= 0:
                remaining_score -= pc[j][1]
                break
    if answered_number < ans:
       ans = answered_number
print(ans)

Submission status: Accepted

Solution code:
d, g = map(int, input().split())
pc = []
a = 9999999
for _ in range(d):
    _p, _c = map(int, input().split())
    pc.append([_p, _c])
for i in range(2 ** d):
    tmp = []
    ans = 0
    n = 0
    for j in range(d):
        if ((i >> j) & 1):
            tmp.append(j)
    for j in tmp:
        ans += (j+1)*100*pc[j][0] + pc[j][1]
        n += pc[j][0]
    if ans >= g:
        if n < a:
            a = n
    else:
        for j in range(len(pc)):
            if not j in tmp:
                plus = 0
                for k in range(pc[j][0]):
                    plus += (j+1)*100
                    if ans + plus >= g:
                        if n + k + 1 < a:
                            ans += plus
                            n += k+1
                            a = n
                            break
print(a)