Problem:


Score : 300 points

Problem Statement

A programming competition site AtCode provides algorithmic problems.
Each problem is allocated a score based on its difficulty.
Currently, for each integer i between 1 and D (inclusive), there are p_i problems with a score of 100i points.
These p_1 + … + p_D problems are all of the problems available on AtCode.

A user of AtCode has a value called total score.
The total score of a user is the sum of the following two elements:

Base score: the sum of the scores of all problems solved by the user.

Perfect bonuses: when a user solves all problems with a score of 100i points, he/she earns the perfect bonus of c_i points, aside from the base score (1 ≤ i ≤ D).

Takahashi, who is the new user of AtCode, has not solved any problem.
His objective is to have a total score of G or more points.
At least how many problems does he need to solve for this objective?

Constraints

1 ≤ D ≤ 10

1 ≤ p_i ≤ 100

100 ≤ c_i ≤ 10^6

100 ≤ G

All values in input are integers.

c_i and G are all multiples of 100.

It is possible to have a total score of G or more points.

Input

Input is given from Standard Input in the following format:

D G
p_1 c_1
:
p_D c_D

Output

Print the minimum number of problems that needs to be solved in order to have a total score of G or more points. Note that this objective is always achievable (see Constraints).

Sample Input 1

2 700
3 500
5 800

Sample Output 1

3

In this case, there are three problems each with 100 points and five problems each with 200 points. The perfect bonus for solving all the 100-point problems is 500 points, and the perfect bonus for solving all the 200-point problems is 800 points. Takahashi's objective is to have a total score of 700 points or more.

One way to achieve this objective is to solve four 200-point problems and earn a base score of 800 points. However, if we solve three 100-point problems, we can earn the perfect bonus of 500 points in addition to the base score of 300 points, for a total score of 800 points, and we can achieve the objective with fewer problems.

Sample Input 2

2 2000
3 500
5 800

Sample Output 2

7

This case is similar to Sample Input 1, but the Takahashi's objective this time is 2000 points or more. In this case, we inevitably need to solve all five 200-point problems, and by solving two 100-point problems additionally we have the total score of 2000 points.

Sample Input 3

2 400
3 500
5 800

Sample Output 3

2

This case is again similar to Sample Input 1, but the Takahashi's objective this time is 400 points or more. In this case, we only need to solve two 200-point problems to achieve the objective.

Sample Input 4

5 25000
20 1000
40 1000
50 1000
30 1000
1 1000

Sample Output 4

66

There is only one 500-point problem, but the perfect bonus can be earned even in such a case. 



Sample input:
2 700
3 500
5 800


Sample output:
3

Submission status: Accepted

Solution code:
from math import ceil
d,g=map(int,input().split())
pc=[list(map(int,input().split())) for _ in [0]*d]
m=1000

for i in range(2**d):
    cnt=0
    s=g
    for j in range(d):
        k=(i&(2**j))>>j
        if k==1:
            s-=pc[j][0]*(j+1)*100+pc[j][1]
            cnt+=pc[j][0]
    if s<=0:
        m=min(m,cnt)
    else:
        for j in range(d-1,-1,-1):
            k=(i&(2**j))>>j
            if k==0:
                if pc[j][0]*(j+1)*100 >= s:
                    cnt+=ceil(s/((j+1)*100))
                    break
                else:
                    s-=pc[j][0]*100*(j+1)
                    cnt+=pc[j][1]
        m=min(m,cnt)
print(m)

Submission status: Accepted

Solution code:
# ABC 104

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

min_ans = 9999999999
ans = 0
sum_point = 0
dont_solved = [i for i in range(D)]

for bit in range(1<<D):
    dont_solved = [i for i in range(D)]
    ans = 0
    sum_point = 0
    for i in range(D):
        if bit & (1<<i):
            ans += p[i]
            sum_point += (100 * (i+1)) * (p[i]) + c[i]
            dont_solved.remove(i)
    if sum_point < G:
        for i in dont_solved[::-1]:
            for j in range(p[i]):
                sum_point += 100 * (i+1)
                ans += 1
                if sum_point >= G:
                    break
            else:
                continue
            break
    if ans <= min_ans:
        min_ans = ans
print(min_ans)

Submission status: Accepted

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

def solve(g, d):
  if d == 0:
    return 10**9
  n = min(g//(100*d), pc[d][0])
  t = n * d * 100
  if n == pc[d][0]:
    t += pc[d][1]
  if t < g:
    n += solve(g-t, d-1)
  return min(n, solve(g,d-1))

print(solve(g,d))

Submission status: Accepted

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

min_solved = 1000
for i in range(2 ** d):
    i_str = "{:010b}".format(i)[::-1]
    score = 0
    solved = 0
    for j in range(d):
        if i_str[j] == "1":
            score += 100 * (j + 1) * pc[j][0] + pc[j][1]
            solved += pc[j][0]
    if score < g:
        add_i = i_str[:d].rfind("0")
        for k in range(pc[add_i][0]):
            score += 100 * (add_i + 1)
            solved += 1
            if score >= g:
                break
        else:
            continue

    if solved < min_solved:
        min_solved = solved

print(min_solved)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys


def solve(D: int, G: int, p: "List[int]", c: "List[int]"):
    cm = sum(p)
    for i in range(1<<D):
        s = 0
        ct = 0
        for j in range(D):
            if((i>>j)&1):
                s += (j+1)*100*p[j]+c[j]
                # print(s)
                ct += p[j]
    
        for j in range(D, 0, -1):
            if(s >= G): break
            if((i>>(j-1))&1): continue
            u = 100*j
            n = (G-s+u-1)//u
            s += p[j-1]*u
            ct += min(n, p[j-1])

        cm = min(cm, ct)

    print(cm)
    
    return


# Generated by 1.1.5 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    D = int(next(tokens))  # type: int
    G = int(next(tokens))  # type: int
    p = [int()] * (D)  # type: "List[int]"
    c = [int()] * (D)  # type: "List[int]"
    for i in range(D):
        p[i] = int(next(tokens))
        c[i] = int(next(tokens))
    solve(D, G, p, c)

if __name__ == '__main__':
    main()

Submission status: Accepted

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

def Base_10_to_n(X, n):
    X_dumy = X
    out = ''
    while X_dumy>0:
        out = str(X_dumy%n)+out
        X_dumy = int(X_dumy/n)
    return out

p = []
c = []
for _ in range(D):
	p_tmp, c_tmp = map(int,input().split())
	p.append(p_tmp)
	c.append(c_tmp)
t = [(i+1)*100*p[i] + c[i] for i in range(D)]

ans = float("inf")

for i in range(2**D):
	flg = list(map(int, Base_10_to_n(i,2).rjust(D,"0")))
	tmp_score = sum([t[j] for j in range(D) if flg[j] == 1])
	cnt = sum([p[j] for j in range(D) if flg[j] == 1])

	if tmp_score < G:

		rst_max_q = max([j for j in range(D) if flg[j] == 0])

		rst_q_num = 0
		while rst_q_num < p[rst_max_q]:
			tmp_score += 100*(rst_max_q+1)
			rst_q_num += 1
			cnt += 1
			if tmp_score >= G:
				break

		if tmp_score < G:
			continue

	ans = min(ans, cnt)


print(ans)

Submission status: Accepted

Solution code:
d, g = map(int, input().split())
pc = [list(map(int, input().split())) for _ in range(d)]
ans = 1001
for i in range(1<<d):
    count, score, left = 0, 0, 0
    for j in range(d):
        if (i >> j) & 1:
            score += (j+1)*100*pc[j][0] + pc[j][1]
            count += pc[j][0]
        else: left = j
    add = min(-(-max(g-score, 0)//((left+1)*100)),pc[left][0])
    count += add
    score += (left+1)*100*add
    if score >= 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 = 1001
for i in range(1<<d):
    count, score, left = 0, 0, 0
    for j in range(d):
        if (i >> j) & 1:
            score += (j+1)*100*pc[j][0] + pc[j][1]
            count += pc[j][0]
        else: left = j
    for j in range(pc[left][0]):
        if score >= g: break
        score += (left+1)*100
        count += 1
    if score >= g: ans = min(ans, count)
print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys


def solve(D: int, G: int, p: "List[int]", c: "List[int]"):

    # bit全探索
    mc = sum(p)
    for i in range(1 << D):
        s = 0
        cc = 0
        for j in range(D):
            if((i >> j) & 1):
                s += (j+1)*p[j]*100+c[j]
                cc += p[j]
        # if(s >= G):
        #     mc = min(mc, cc)
        # 以下はuwiさんの回答を参考
        for j in range(D-1, -1, -1):
            # ここはもう全部解くことが決まっている
            if((i>>j)&1):
                continue
            # 「すべて解く」のみで目的スコアに達する場合はそのまま抜けて良い　＆　前回の足して合計に達するならば出て良い
            if(s >= G):
                break
            # g: 最大のスコアの問題の一問あたりのスコア
            g = (j+1)*100
            # got: どのくらいとくか
            # g-1を足すことで、math.ceilを使わなくて良い(//で表現できる)
            got = (G-s+g-1)//g
            s += min(got, p[j])*g
            cc += min(got, p[j])
        mc = min(cc, mc)

    print(mc)

    return


# Generated by 1.1.5 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    D = int(next(tokens))  # type: int
    G = int(next(tokens))  # type: int
    p = [int()] * (D)  # type: "List[int]"
    c = [int()] * (D)  # type: "List[int]"
    for i in range(D):
        p[i] = int(next(tokens))
        c[i] = int(next(tokens))
    solve(D, G, p, c)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
import math
from fractions import gcd
# import queue
# from collections import Counter
# from itertools import accumulate
# from functools import reduce

def lcm(a, b):
    return a * b // gcd(a, b)

def combination_count(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))

def permutations_count(n, r):
    return math.factorial(n) // math.factorial(n - r)

big_prime = 1000000007

"""
# 標準入力取得
## 文字列
 =  sys.stdin.readline().rstrip()
 =  list(sys.stdin.readline().rstrip())

## 数値
 =  int(sys.stdin.readline())
 =  map(int, sys.stdin.readline().split())
 =  list(map(int, sys.stdin.readline().split()))
 =  [list(map(int,list(sys.stdin.readline().split()))) for i in range(N)]
"""

D, G =  map(int, sys.stdin.readline().split())
L =  [list(map(int,list(sys.stdin.readline().split()))) for i in range(D)][::-1]

ans = 10 ** 10

for bit in range(2 ** D):
    cnt = 0
    point = 0
    for i, l in enumerate(L):
        # print(bin(bit), i, bin(1 << i))
        if bit & (1 << i):
            q_num = l[0]
            bonus = l[1]
            point += q_num * (D - i) * 100 + bonus
            cnt += q_num

    if point >= G:
        ans = min(ans, cnt)
        continue

    for i, l in enumerate(L):
        if not bit & (1 << i):
            for _ in range(l[0]):
                point += (D - i) * 100
                cnt += 1
                if point >= G:
                    break
            else:
                continue
            break

    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)]
r=1000
from itertools import product
for X in product(range(2),repeat=D):
    g,a=0,0
    for i,x in enumerate(X):
        if x:
            g+=pc[i][1]+pc[i][0]*(i+1)*100
            a+=pc[i][0]
    for i in range(D-1,-1,-1):
        if X[i]==1:
            continue
        if g>=G:
            break
        n=min(pc[i][0]-1,-((g-G)//((i+1)*100)))
        a+=n
        g+=n*(i+1)*100
    if g>=G:
        r=min(r,a)
print(r)

Submission status: Accepted

Solution code:
INF = float('inf')
d, g = map(int, input().split())
data = []
calced = set()
for i in range(d):
  p, c = map(int, input().split())
  data.append([p, c, (i + 1) * 100, (i + 1) * 100 * p + c])
def f(data, total, targets):
  if total <= 0:
    return 0
  result = INF
  for i in range(len(targets)):
    p, c, score, subtotal = data[targets[i]]
    t = (total + score - 1) // score
    if t < p and t < result:
      result = t
    nt = tuple(targets[0:i] + targets[i + 1:])
    if nt not in calced:
      calced.add(nt)
      t = p + f(data, total - subtotal, nt)
      if t < result:
        result = t
  calced.add(targets)
  return result
print(f(data, g, tuple(range(len(data)))))

Submission status: Accepted

Solution code:
import math
d,g=map(int,input().split())
pc=[[int(i)for i in input().split()]for _ in range(d)]
a=1000
for i in range(2**d):
    c=0
    s=0
    m=0
    for j in range(d):
        if (i>>j)&1:
            s+=(j+1)*100*pc[j][0]+pc[j][1]
            c+=pc[j][0]
        else:
            m=j
    if s>=g:
        a=min(a,c)
    elif (m+1)*100*(pc[m][0]-1)+s>=g:
        a=min(a,c+math.ceil((g-s)/((m+1)*100)))
print(a)

Submission status: Accepted

Solution code:
# https://atcoder.jp/contests/abc104/submissions/7167759

INF = float('inf')
D, G = map(int, input().split())
problems = [] * D
bonus = [] * D
ans = 0
for _ in range(D):
    p, c = map(int, input().split())
    problems.append(p)
    bonus.append(c)

ans = INF
for bit in range(1 << D):
    total_problem = 0
    total_score = 0
    # --------------
    # bit全探索
    # --------------
    for i in range(D):
        if bit & (1 << i):
            s = (i + 1) * 100
            total_score += s * problems[i] + bonus[i]
            total_problem += problems[i]

    for i in range(D - 1, -1, -1):
        if G <= total_score:
            break
        if bit & (1 << i):
            continue

        s = (i + 1) * 100
        required_score = G - total_score
        required_problem = (required_score + s - 1) // s
        total_score += min(required_problem, problems[i]) * s
        total_problem += min(required_problem, problems[i])

    if G <= total_score:
        ans = min(ans, total_problem)

print(ans)

Submission status: Accepted

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

ans = 10 ** 9
for i in range(1 << D):
    score = 0
    solved = 0
    for j in range(D):
        p, c = scores[j]
        if i & (1 << j):
            solved += p
            score += p * 100 * (j + 1) + c
        else:
            k = j

    if score >= G:
        ans = min(ans, solved)
        continue

    p, c = scores[k]
    for j in range(p):
        solved += 1
        score += 100 * (k + 1)
        if score >= G:
            ans = min(ans, solved)
            break

print(ans)

Submission status: Accepted

Solution code:
# https://atcoder.jp/contests/abc104/tasks/abc104_c
# C - All Green
import itertools

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

# 完全にとく or 途中までとく or 全くとかない パターンがある
# 各問題ごとに、完全にとくかどうかの組み合わせ
p_gen = itertools.product([0, 1], repeat=D)

cost_list = []
for pattern in p_gen:
    cost = 0
    point = 0
    for i, solve_flag in enumerate(pattern):
        point += ((i+1) * 100 * pc_list[i][0] + pc_list[i][1]) * solve_flag
        cost += pc_list[i][0] * solve_flag

    if point >= G:
        # 解けた場合
        cost_list.append(cost)
    else:
        # 解けない場合は、完全にといていない問題のうち次に配点が高いもので埋める
        # ただし、完全にとくことはできないので、各問題で使えるのはp-1問まで
        kouho_list = [i for i, solve_flag in enumerate(pattern) if solve_flag == 0]
        kouho_list = sorted(kouho_list, reverse=True)
        is_over = False
        for i in kouho_list:
            for _ in range(1, pc_list[i][0]):
                point += (i+1) * 100
                cost += 1
                if point >= G:
                    is_over = True
                    break
            if is_over:
                break
        if is_over:
            cost_list.append(cost)

ans = min(cost_list)
print(ans)

Submission status: Accepted

Solution code:
import sys

stdin = sys.stdin

ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline()

D, G = na()
p = []
c = []

for i in range(D):
    x, y = na()
    p.append(x)
    c.append(y)

ans = 9999999999999
for i in range(1<<D):
    score = 0
    ct = 0
    for j in range(D):
        if i >> j & 1:
            score += (p[j] * (j+1) * 100 + c[j])
            ct += p[j]
    for j in range(D-1, -1, -1):
        if i >> j & 1: continue
        if score >= G: break
        g = (j + 1) * 100
        got = (G - score) // g
        score += min(got, p[j]) * g
        ct += min(got, p[j])
    ans = min(ans, ct)
print(ans)

Submission status: Accepted

Solution code:
import sys

stdin = sys.stdin

ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline()

D, G = na()
p = []
c = []

for i in range(D):
    x, y = na()
    p.append(x)
    c.append(y)

ans = 9999999999999
for i in range(1<<D):
    score = 0
    ct = 0
    for j in range(D):
        if i >> j & 1:
            score += (p[j] * (j+1) * 100 + c[j])
            ct += p[j]
    for j in range(D-1, -1, -1):
        if i >> j & 1: continue
        if score >= G: break
        g = (j + 1) * 100
        got = (G - score + g - 1) // g
        score += min(got, p[j]) * g
        ct += min(got, p[j])
    ans = min(ans, ct)
print(ans)

Submission status: Accepted

Solution code:

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)
##############################

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

ans = float('inf')
for i in range(1<<D):
    total = 0
    num = 0
    for j in range(D):
        if ((i >> j) & 1):
            total += C[j] + 100*P[j]*(j+1)
            num += P[j]

    if total >= G:
        ans = min(ans, num)
    else:
        for j in range(D-1, -1, -1):
            if ((i >> j) & 1):
                continue

            for k in range(P[j]-1):
                if total >= G:
                    break
                total += 100*(j+1)
                num += 1

        if total >= G:
            ans = min(ans, num)

print(ans)

Submission status: Accepted

Solution code:

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)
##############################

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

ans = float('inf')
for i in range(1<<D):
    total = 0
    num = 0
    for j in range(D):
        if ((i >> j) & 1):
            total += C[j] + 100*P[j]*(j+1)
            num += P[j]

#    print(total, num)
    if total >= G:
        ans = min(ans, num)
    else:
        for j in range(D-1, -1, -1):
            if ((i >> j) & 1):
                continue

#            print('i=', i)
#            print('j=',j)
#            print('-', total, num)
            for k in range(P[j]-1):
                if total >= G:
                    break
#                print('?', total, num)
#                print('k=', k)
                total += 100*(j+1)
                num += 1
#                print('?', total, num)

#        print('Z', total, num, ans)
#        print('----')
        if total >= G:
#            print('x', total, num, ans)
            ans = min(ans, num)

print(ans)

Submission status: Accepted

Solution code:


import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)
##############################

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

ans = float('inf')
for i in range(1<<D):
    total = 0
    num = 0
    for j in range(D):
        if ((i >> j) & 1):
            total += C[j] + 100*P[j]*(j+1)
            num += P[j]

    if total >= G:
        ans = min(ans, num)
    else:
        for j in range(D-1, -1, -1):
            if ((i >> j) & 1):
                continue

            for k in range(P[j]):
                if total >= G:
                    break
#                print(k, total, num)
                total += 100*(j+1)
                num += 1

#        print('x', k, total, num, ans)
        ans = min(ans, num)

print(ans)

Submission status: Accepted

Solution code:
import itertools
from operator import itemgetter

D,G = map(int,input().split())
pc = []

for i in range(D):
    p,c = list(map(int,input().split())) 
    tmp = (i+1) * 100 * p + c #合計得点
    pc.append([p,c,tmp])

A = [0,1]
mintimes = 10000

for i in itertools.product(A,repeat=D):
    score = 0
    times = 0
    lest = []
    
    for j,v in enumerate(i):
        if v != 0:
            score += pc[j][2]
            times += pc[j][0]
        else:
            lest.append(j)
    
    if score >= G:
        #更新する
        mintimes = min(times,mintimes)
    else:
        objective = G - score

        part = []
        for k in lest: 
            part.append([pc[k][0],100*(k+1)])
        
        part2 = sorted(part,key=itemgetter(1),reverse = True)

        for m in part2:
            if objective > (m[0]-1) * m[1]:
                objective -= (m[0]-1) * m[1]
                times += (m[0]-1)
            else:
                tmp3 = objective // m[1]
                if objective % m[1] != 0:
                    tmp3 += 1
                times += tmp3
                mintimes = min(mintimes,times)
                break

print(mintimes)

Submission status: Accepted

Solution code:
import sys
from pprint import pprint

import math

d, g = map(int, sys.stdin.readline().strip().split(" "))

p = []
c = []
for _ in range(d):
    p_i, c_i = map(int, sys.stdin.readline().strip().split(" "))
    p.append(p_i)
    c.append(c_i)

ans = 10 ** 9
for i in range(2**d):
    use = [0] * d
    for j in range(d):
        if ((i >> j) & 1):
            use[d - 1 - j] = 1
    # pprint(use)
    score = 0
    tmp_ans = 0
    max_i = -1
    for i, use_i in enumerate(use):
        if use_i:
            tmp_ans += p[i]
            score += p[i] * (i+1) * 100 + c[i]
        else:
            max_i = i
    # print("tmp_ans: ", tmp_ans, " score:", score, " max_i:", max_i)
    if score < g  and max_i > -1:
        num = math.ceil((g - score) / ((max_i+1) * 100))
        # print("num:", num)
        if num < p[max_i]:
            tmp_ans += num
            score += num * ((max_i+1) * 100)
    # print(tmp_ans, score)
    if score >= g:
        ans = min(ans, tmp_ans)
        
print(ans)

Submission status: Accepted

Solution code:
import numpy as np
d, g = map(int, input().strip().split(' '))
p = [0] * d
c = [0] * d
num = []
for i in range(d):
  p[i], c[i] = map(int, input().strip().split(' '))
for j in range( 2**d ):
  csum = 0; n = 0; jpl = []
  for i in range(d):
    if j >= 2**(d-i-1):
      jp = 1
      j = j - 2**(d-i-1)
    else:
      jp = 0
      jpl.append(i)
    csum = csum + ( 100 * (i+1) * p[i] + c[i] ) * jp
    n = n + p[i] * jp
  if csum < g and jpl != []:
    i = max(jpl)
    remain = int(np.ceil( ( g - csum ) / ( 100 * (i+1) ) ))
    if remain < p[i]:
      n = n + remain
      num.append(n)
    else:
      pass
  else:
    num.append(n)
print(min(num))

Submission status: Accepted

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

ans = 2000

for i in range(2 ** D):
    tmp = 0
    max_ = -1
    count = 0
    for j in range(D):
        if (i >> j) & 1 == 1:
            tmp += pc[j][0] * 100 * (j + 1) + pc[j][1]
            count += pc[j][0]
        else:
            max_ = j
    if tmp < G:
        if max_ >= 0:
            for j in range(pc[max_][0]):
                tmp += 100 * (max_ + 1)
                count += 1
                if tmp >= G:
                    break
    if tmp >= G:
        ans = min(ans, count)

print(ans)

Submission status: Accepted

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

def main():
    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)
    min_n = 100*D
    for i in range(2**D):
        s = 0
        n = 0
        max_zero_index = -1
        for j in range(D):
            if (i >> j) & 1:
                s += (j+1)*100*P[j] + C[j]
                n += P[j]
            else:
                max_zero_index = max(max_zero_index, j)
        if max_zero_index != -1:
            tmp = P[max_zero_index]
            while s < G and tmp > 0:
                tmp -= 1
                n += 1
                s += (max_zero_index+1)*100
        if s >= G:
            min_n = min(min_n, n)
    print(min_n)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import itertools
import math
d, g = map(int, input().split())
l = []
cl = []
for i, _ in enumerate(range(d)):
    p, c = map(int, input().split())
    l.append([p, c])
    cl.append(p * 100 * (i + 1) + c)

ans = float("INF")
for flags in itertools.product([0, 1], repeat=d):
    q = []
    cost = g
    cnt = 0
    for i, flag in enumerate(flags):
        if flag:
            cost -= cl[i]
            cnt += l[i][0]
        else:
            q.append(i)

    q.reverse()
    if cost > 0:
        for i in q:
            if math.ceil(cost / (100 * (i + 1))) <= l[i][0]:
                cnt += math.ceil(cost / (100 * (i + 1)))
                break
        else:
            cnt = float("INF")
    ans = min(ans, cnt)
print(ans)

Submission status: Accepted

Solution code:
import math
d, g = map(int, input().split())
pc = [list(map(int, input().split())) for _ in range(d)]
n = sum([pc[i][0] for i in range(d)])
ans = float('inf')


for i in range(2 ** d):
    score = 0
    num = 0
    max_num = 0
    for j in range(d):
        if (i>>j) & 1:
            score += 100*(j+1)*pc[j][0] + pc[j][1]
            num += pc[j][0]
            
        else:
            max_num = max(max_num, j+1)
            
    if score < g:
        add_n = math.ceil((g-score)/(100*(max_num)))
        if add_n < pc[max_num-1][0]:
            num += add_n
            score += add_n * (100*(max_num+1))

    if score >= g:
        ans = min(ans, num)

print(ans)

Submission status: Accepted

Solution code:
import math
d, g = map(int, input().split())
pc = [list(map(int, input().split())) for _ in range(d)]
n = sum([pc[i][0] for i in range(d)])
prob = []
comp = [0 for _ in range(len(pc))]
for i in range(len(pc)):
    prob += [100*(i+1)] * (pc[i][0])
for i in range(len(pc)):
    comp[i] = pc[i][0]
ans = float('inf')

for i in range(2 ** d):
    score = 0
    num = 0
    max_num = 0
    for j in range(d):
        #print("score:", score, "num:", num, "j:", j, "i:", i)
        if (i>>j) & 1:
            score += 100*(j+1)*pc[j][0] + pc[j][1]
            num += pc[j][0]
            
        else:
            max_num = max(max_num, j+1)
            #if max_num == j+1:
                #max_num -= 1 
    if score < g:
        add_n = math.ceil((g-score)/(100*(max_num)))
        #if i == 24:
            #print(num, add_n, score, max_num)
        #print("add_n:", add_n, max_num)
        if add_n < pc[max_num-1][0]:
            num += add_n
            score += add_n * (100*(max_num+1))

    #print(score, num)
    if score >= g:
        ans = min(ans, num)
        #print(num,i)

print(ans)

Submission status: Accepted

Solution code:
#参考: https://betrue12.hateblo.jp/entry/2018/08/05/230358
D,G=map(int,input().split())
p,c=[],[]

for i in range(D):
    inp=input().split()
    p.append(int(inp[0]))
    c.append(int(inp[1]))

ans=1000000000
for i in range(2**D):
    num,sum=0,0
    index=[]
    for j in range(D):
        if (i>>j)&1:
            sum+=100*(j+1)*p[j]+c[j]
            num+=p[j]
            index.append(j)
            #print(i,j+1)
    if sum >= G:
        #print(num)
        ans=min(num,ans)
    else:
        for ii in reversed(range(0,D)):
            if not ii in index:
                for jj in range(p[ii]):
                    sum+=100*(ii+1)
                    num+=1
                    if sum >= G:
                        #print(num)
                        #debug(index)
                        ans=min(num,ans)
                        break

print(ans)

Submission status: Accepted

Solution code:
#PDF解説
D, G = [int(dg) for dg in input().split()]
P, PC = [], []
for d in range(D):
  p, c = [int(pc) for pc in input().split()]
  P.append(p)
  PC.append(100*(d+1)*p + c)

HMP = []
for i in range(2**D):
  i2 = format(i, "b")
  i2 = "0"*(D-len(i2)) + i2
  score = 0
  howmany_problems = 0
  for j in range(D):
    score += PC[j] * int(i2[j])
    howmany_problems += P[j] * int(i2[j])
    
  if score >= G:
    HMP.append(howmany_problems)
  else: # score < G:
    for k in range(D-1, -1, -1):
      if i2[k] == "0":
        break
    pk = P[k]
    for x in range(1, pk):
      score += 100 * (k+1)
      if score >= G:
        HMP.append(howmany_problems + x)
        break

ans = min(HMP)
print(ans)

Submission status: Accepted

Solution code:
#### import ####
import sys
import math
from collections import defaultdict

#### 設定 ####
sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

#### 定数 ####
mod = 10**9 + 7

#### 読み込み ####
def I(): return int(input())
def II(): return map(int, input().split())
def III(): return list(map(int, input().split()))
def Line(N):
    read_all = [tuple(map(int, input().split())) for _ in range(N)]
    return map(list,zip(*read_all))

#################

D,G = II()
p,c = Line(D)

def dfs(point,p):
    if point<=0:
        return 0
    else:
        ret = []
        for i in range(D):
            if p[i]==0:
                continue
            q,mod = divmod(point,(i+1)*100)
            if mod ==0:
                num = q
            else:
                num = q+1
            if num <= p[i]:
                ret.append(num)
            else:
                temp = p[i]
                p[i] = 0
                ret.append(dfs(point-100*(i+1)*temp-c[i],p)+temp)
                p[i] = temp
        return min(ret)

print(dfs(G,p))