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():
    g, list_of_p_and_c = read()
    result = think(g, list_of_p_and_c)
    write(result)


def read():
    d, g = read_int(2)
    list_of_p_and_c = []
    for i in range(d):
        list_of_p_and_c.append(read_int(2))
    return g, list_of_p_and_c


def read_int(n):
    return list(map(int, read_line().split(' ')))[:n]


def read_line(n=0):
    if n == 0:
        return input().rstrip()
    else:
        return input().rstrip()[:n]


def think(g, list_of_p_and_c):
    complete_bonus = []
    list_of_question_remained = []
    for p, c in list_of_p_and_c:
        list_of_question_remained.append(p)
        complete_bonus.append(c)

    return recursive_call(g, complete_bonus, list_of_question_remained, 0, 0, False, -1, {})


def recursive_call(g, complete_bonus, list_of_question_remained, questions_solved, subsum, in_halfway, what_of_halfway, cache):
    key = generate_key_for(list_of_question_remained)
    if key in cache:
        return cache[key]

    if subsum >= g:
        return questions_solved

    max_p = 100
    max_d = 10

    invalid = max_p * max_d + 1
    minimum_questions_to_be_solved = invalid

    local_list_of_question_remained = list(list_of_question_remained)

    if in_halfway:
        if list_of_question_remained[what_of_halfway] == 0:
            return invalid
        local_list_of_question_remained[what_of_halfway] -= 1
        return recursive_call(g, complete_bonus, local_list_of_question_remained, questions_solved + 1, subsum + 100 * (what_of_halfway + 1), True, what_of_halfway, cache)
    else:
        for i in range(len(list_of_question_remained)):
            if list_of_question_remained[i] == 0:
                continue  # already greedyed

            # case 1. greedy
            new_subsum = subsum + 100 * (i + 1) * list_of_question_remained[i] + complete_bonus[i]
            local_list_of_question_remained = list(list_of_question_remained)
            buf = local_list_of_question_remained[i]
            local_list_of_question_remained[i] = 0
            buf_2 = recursive_call(g, complete_bonus, local_list_of_question_remained, questions_solved + buf, new_subsum, False, -1, cache)

            minimum_questions_to_be_solved = min(minimum_questions_to_be_solved, buf_2)

            # case 2. not greedy, halfway
            new_subsum = subsum + 100 * (i + 1)
            local_list_of_question_remained = list(list_of_question_remained)
            local_list_of_question_remained[i] -= 1
            buf_2 = recursive_call(g, complete_bonus, local_list_of_question_remained, questions_solved + 1, new_subsum, True, i, cache)

            minimum_questions_to_be_solved = min(minimum_questions_to_be_solved, buf_2)

    cache[key] = minimum_questions_to_be_solved
    return minimum_questions_to_be_solved


def generate_key_for(list_of_question_remained):
    return ','.join(map(str, list_of_question_remained))


def write(result):
    print(result)


if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:

def updiv(a,b):

    if a % b == 0:
        return a // b
    else:
        return a // b + 1


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.reverse()

ans = float("inf")

for j in range(2 ** D):

    j_bin = format(j,'b')
    flags = j_bin.zfill(D)

    num = 0
    score = 0

    for k in range(D):

        if flags[k] == "1":

            num += pc[k][1]
            score += pc[k][1] * pc[k][0] * 100 + pc[k][2]

    if G > score:

        for k in range(D):

            if flags[k] == "0" and score + pc[k][1] * pc[k][0] * 100 >= G:

                plnum = updiv( G - score , pc[k][0] * 100 )
                num += plnum

                score += plnum * pc[k][0] * 100
                break

    if G <= score:

        ans = min(ans,num)
        #print (ans,num,score,flags)

print (ans)

Submission status: Accepted

Solution code:
import math
import sys
import queue
from collections import Counter
from itertools import accumulate
from fractions import gcd
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)

mod = 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)]
"""

if __name__ == "__main__":
    D, G = map(int, sys.stdin.readline().split())
    L = [list(map(int,list(sys.stdin.readline().split()))) for i in range(D)]
    ans = 10 ** 10
    for bit in range(1 << D):
        total = 0
        num = 0

        for i in range(D):
            if bit & (1 << i):
                total += L[i][1] + L[i][0] * 100 * (i + 1)
                num += L[i][0]

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

        for i in range(D - 1, -1, -1):

            if bit & (1 << i): continue

            for _ in range(L[i][0]):
                total += (i + 1) * 100
                num += 1
                if total >= G:
                    ans = min(ans, num)
                    break

    print(ans)

Submission status: Accepted

Solution code:
import math

D, G = map(int, input().split())
ans = 10**7
problems = [tuple(map(int, input().split())) for _ in range(D)]
for num in range(2**D):
  solve = 0
  point = 0
  last = -1
  for i in range(D):
    if num>>i&1:
      point += problems[i][1] + (i+1)*100*problems[i][0]
      solve += problems[i][0]
    else:
      last = i
  if last == -1:
    ans = min(ans, solve)
  else:
    rest = G - point
    if rest <= 0:
      ans = min(ans, solve)
    else:
      if rest <= (last+1)*100*problems[last][0]:
        ans = min(ans, solve+math.ceil(rest/((last+1)*100)))
print(ans)

Submission status: Accepted

Solution code:
n, need = map(int, input().split())
a = [list(map(int, input().split())) for _ in range(n)]

ret = float('inf')
for mask in range(1 << n):
    total = 0
    count = 0
    for bit in range(n):
        if (mask >> bit) & 1:
            num, bonus = a[bit]
            points = (bit + 1) * 100
            total += points * num + bonus
            count += num
    for bit in range(n - 1, -1, -1):
        if (mask >> bit) & 1 == 0:
            num = a[bit][0]
            points = (bit + 1) * 100
            for i in range(num):
                if total >= need:
                    break
                total += points
                count += 1
    if total >= need:
        ret = min(ret, count)

print(ret)

Submission status: Accepted

Solution code:
def main():
    D, G = map(int, input().split())
    pc = []
    min_ct = 0
    for i in range(D):
        p, c = map(int, input().split())
        pc.append([p, c])
        min_ct += p

    bonus = [set()]
    for i in range(D):
        temp = []
        for st in bonus:
            temp.append(st | {i})
        bonus += temp
    # print(bonus)

    for comp in bonus:
        pt = sum([pc[i][0]*100*(i+1)+pc[i][1] for i in comp])
        ct = sum([pc[i][0] for i in comp])
        j = 0
        # print(comp, pt, j)
        for i in range(D-1, -1, -1):
            if i not in comp:
                while j < pc[i][0] and pt < G:
                    pt += 100 * (i+1)
                    j += 1
                break
        # print(comp, pt, j)
        if pt >= G:
            min_ct = min(min_ct, ct+j)

    return min_ct

if __name__ == '__main__':
    print(main())

Submission status: Accepted

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

sums = [100*(i+1)*l[i][0]+l[i][1] for i in range(d)]

ans = 1001
for bit in range(1<<d):
    cnt = 0
    sum = 0
    nokori = []

    for i in range(d):

        if bit & (1<<i):
            sum += sums[i]
            cnt += l[i][0]
        else:
            nokori.append([100*(i+1), -(l[i][0]-1)])

    if sum < g:
        nokori.sort(reverse=True)
        for j in range(-nokori[0][1]):
            sum += nokori[0][0]
            cnt += 1
            if sum >= g:
                    break

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

print(ans)

Submission status: Accepted

Solution code:
# ビット演算を使おう

D, G = map(int, input().split())
pc = [tuple(map(int,input().split())) for i in range(D)]
import math
ans = 10**5
for i in range(2**D):
    # 使い切る部分が１、選ばない部分が０
    b = str(bin(i))[2:].zfill(D)
    

    cnt = 0
    point = 0
    first_zero_idx = 0
    flag = False
    #print(b)
    for j in range(len(b)):
        # 解ききる問題の点とボーナスの和
        if b[j] == "1":
            point += (D-j)*100*pc[D-1-j][0] + pc[D-1-j][1]
            cnt += pc[D-1-j][0]
        else:
            if not flag:
                first_zero_idx = j
                flag = True
    if flag:
        # 残りのうち最も得点の高い問題を解いたときにボーダーを超えるかどうか
        if point < G and G - point <= (pc[D-1-first_zero_idx][0]-1)*100*(D-first_zero_idx):
            #print(b, point, cnt)
            tmp = math.ceil((G - point) / (100*(D-first_zero_idx)))
            cnt += tmp
            point += tmp*100*(D-first_zero_idx)
    if point >= G:
        ans = min(ans, cnt)
        #print("---",b, point, cnt, tmp, first_zero_idx)
        
print(ans)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10000)
D, G = list(map(int, input().split(' ')))
left = {}
bonus = {}
for i in range(1, D+1):
    left[i], bonus[i] = list(map(int, input().split(' ')))
 
big = 9999999
 
probably_ans = big
memo = {}
def hogehoge(depth, index, pt, left, bonus, probably_ans):
    key = (depth, index, pt, str(left))
    if key in memo:
        return memo[key]
    if pt >= G:
        return depth
    if depth >= probably_ans or index > D:  # 遅いかも
        return big
    
    # 一つも引かない
    probably_ans = min(probably_ans, hogehoge(depth, index + 1, pt, left, bonus, probably_ans))
    
    # 全部引いて index reset
    for k in range(0, D - index + 1):
        if left[index + k]:
            temp = left[index + k]
            left[index + k] = 0
            probably_ans = min(probably_ans, hogehoge(depth+temp, 1, pt + (index + k) * 100 * temp + bonus[index + k], left, bonus, probably_ans))
            left[index + k] = temp

    # 歯抜け状態から行けそうならクリア
    if left[index]:
        if pt + index * 100 * left[index] + bonus[index] >= G:
            for i in range(1, left[index] + 1):
                left[index] = left[index] - i
                new_pt = pt + index * 100 * i + bonus[index] * (left[index] == 0)
                if (new_pt >= G):
                    probably_ans = min(probably_ans, hogehoge(depth+i, index+1, new_pt, left, bonus, probably_ans))
                left[index] = left[index] + i
    memo[key] = probably_ans
    return probably_ans
    
print(hogehoge(0, 1, 0, left, bonus, probably_ans))

Submission status: Accepted

Solution code:
d, g = map(int, input().split())
pc = [list(map(int, input().split())) for _ in range(d)]
ret = 1000000
for b in range(1 << d):
    s, n = 0, 0
    for i in range(d):
        if (b & (1 << i)) != 0:
            p = i * 100 + 100
            s += pc[i][0] * p + pc[i][1]
            n += pc[i][0]
    for i in range(d - 1, -1, -1):
        if (b & (1 << i)) == 0 and s < g:
            p = i * 100 + 100
            m = min((g - s + p - 1) // p, pc[i][0])
            s += m * p
            n += m
    if s >= g:
        ret = min(ret, n)
print(ret)

Submission status: Accepted

Solution code:
import heapq

n, need = map(int, input().split())
a = [list(map(int, input().split())) for _ in range(n)]

ret = float('inf')
for mask in range(1 << n):
    total = 0
    count = 0
    pq = []
    for bit in range(n):
        num, bonus = a[bit]
        points = (bit + 1) * 100
        if (mask >> bit) & 1:
            total += points * num + bonus
            count += num
        else:
            for i in range(num):
                heapq.heappush(pq, -points)
    while total < need and pq:
        total -= heapq.heappop(pq)
        count += 1
    if total >= need:
        ret = min(ret, count)

print(ret)

Submission status: Accepted

Solution code:
import sys
from collections import deque
import copy

sys.setrecursionlimit(4100000)


def inputs(num_of_input):
    ins = [input() for i in range(num_of_input)]
    return ins


def solve(D, G, inputs):
    problems = list(map(string_to_int, inputs))
    binary_max = 2 ** len(problems)

    min_num = -1
    for pattern in range(0, binary_max):
        binary_pattern = bin(pattern)[2:]
        while len(binary_pattern) != D:
            binary_pattern = '0' + binary_pattern

        incompleted_problem = -1
        count_num = 0
        count_score = 0

        for i in reversed(range(len(binary_pattern))):
            if binary_pattern[i] == '1':
                count_num += problems[i][0]
                count_score += (100 * (i+1)) * problems[i][0] + problems[i][1]
            elif incompleted_problem == -1 and binary_pattern[i] == '0':
                incompleted_problem = i

        if incompleted_problem != -1:
            for _ in range(problems[incompleted_problem][0]):
                if count_score >= G:
                    break
                count_num += 1
                count_score += 100 * (incompleted_problem+1)
        if count_score >= G and (min_num == -1 or count_num < min_num):
            min_num = count_num
    return min_num


def string_to_int(string):
    return list(map(int, string.split()))


if __name__ == "__main__":
    [D, G] = string_to_int(input())
    ret = solve(D, G, inputs(D))
    print(ret)

Submission status: Accepted

Solution code:
def dfs(i, total, count, left):
    global ans
    if i == d:
        if total < g:
            target = max(left)
            n = min(pc[target - 1][0], -(-(g - total) // (target * 100)))
            count += n
            total += n * target * 100

        if total >= g:
            ans = min(ans, count)

    else:
        dfs(i+1, total, count, left)
        dfs(i + 1, total + pc[i][0] * (i + 1) * 100 + pc[i][1], \
        count + pc[i][0], left - {i + 1})

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

ans = float("inf")

dfs(0,0,0,set(range(1,d+1)))
print(ans)

Submission status: Accepted

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

ans = float("inf")

for bit in range(1 << d):
    total = 0
    count = 0
    left = set(range(1, d+1))

    for i in range(d):
        if bit & (1 << i):
            total += pc[i][0] * 100 * (i+1) + pc[i][1]
            count += pc[i][0]
            left.discard(i+1)
            #使ったものとして記憶

    if g > total:
        target = max(left)
        n = min(pc[target - 1][0], -(-(g - total) // (target * 100)))#切り上げ
        count += n
        total += n * target * 100
    #この下とはつながっていない

    if g <= total:
        ans = min(ans, count)

print(ans)

Submission status: Accepted

Solution code:
import sys
from math import ceil
INPUT = lambda: sys.stdin.readline().rstrip()
MAP = lambda: map(int, INPUT().split())
LIST = lambda: list(map(int, INPUT().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')

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


def dfs(g, i):
    if i <= 0: return INF
    n = min(ceil(g/(100*i)), PC[i-1][0])
    s = 100 * i * n
    if n == PC[i-1][0]: s += PC[i-1][1]
    if g > s: n += dfs(g-s, i-1)

    return min(n, dfs(g, i-1))


def main():
    print(dfs(G, D))


if __name__ == '__main__':
    main()

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)
  
out = 1000
for i in range(2**D):
  total = 0
  count = 0
  for j in range(D):
    p, c = P[j], C[j]
    if i & (1 << j):
      count += p
      total += p * 100 * (j + 1) + c
    else:
      k = j
      
  if total >= G:
    out = min(out, count) 
    continue
    
  p = P[k]
  for j in range(p):
    count += 1
    total += 100 * (k + 1)
    if total >= G:
      out = min(out, count)
      break

print(out)

Submission status: Accepted

Solution code:
import heapq

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

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

counts = []
for i in range(2**D):
    Bin = str(bin(i))[2:].zfill(D)
    score = 0
    count = 0
    index = -1
    for j, c in enumerate(Bin):
        if int(c):
            score += problems[j][3]
            count += problems[j][1]
        else:
            index = j
    if score >= G:
        heapq.heappush(counts, count)
    elif index != -1:
        div, mod = divmod((G - score), problems[index][0])
        if mod != 0:
            div += 1
        if div < problems[index][1]:
            count += div
            heapq.heappush(counts, count)

print(heapq.heappop(counts))

Submission status: Accepted

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

ans = 1000
for i in range(2 ** 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, _ = 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:
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())
# 各配点について全問解いた時のポイント
fsp = [p[i]*100*(i+1)+c[i] for i in range(D)]

# print(fsp)

min_pro = 100000000

def dfs(solve):
    global min_pro
    max_rest = -1
    if len(solve) == D:
        sum_point = 0
        sum_pro = 0
        for i in range(D):
            if solve[i] == "1":
                sum_point += fsp[i]
                sum_pro += p[i]
            else:
                max_rest = i
        #print(solve, sum_point, max_rest,math.ceil((G - sum_point) / ((max_rest+1)*100)))
        if sum_point < G:
            if math.ceil((G - sum_point) / ((max_rest+1)*100)) < p[max_rest]:
                sum_pro += math.ceil((G - sum_point) / ((max_rest+1)*100))
            else:
                sum_pro += 100000
        if min_pro > sum_pro:
            min_pro = sum_pro


        #pps[counter] = [sum_point, sum_pro, solve]
        #counter += 1
        return 0

    dfs(solve+"0")
    dfs(solve+"1")
    return 0

dfs("0")
dfs("1")

print(min_pro)
print("\n")

Submission status: Accepted

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

num = []
# 完全に解くか解かないかを選ぶ
for i in range(2**D):
    score = 0
    num_tmp = 0  # 解いた問題数
    not_comp = []  # 解いていないもの
    for j in range(D):
        if i >> j & 1:
            score += p[j] * 100 * (j + 1) + c[j]
            num_tmp += p[j]
        else:
            not_comp.append(j)

    for j in not_comp[::-1]:
        if score < G:
            num_j = min(p[j] - 1, (G - score) // (100 * (j + 1)))
            score += num_j * 100 * (j + 1)
            num_tmp += num_j

    if score >= G:
        num.append(num_tmp)

ans = min(num)
print(ans)

Submission status: Accepted

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

num = []
# 完全に解くか解かないかを選ぶ
for i in range(2**D):
    score = 0
    num_tmp = 0  # 解いた問題数
    not_comp = []  # 解いていないもの
    for j in range(D):
        if i >> j & 1:
            score += p[j] * 100 * (j + 1) + c[j]
            num_tmp += p[j]
        else:
            not_comp.append(j)

    for j in not_comp[::-1]:
        if score < G:
            num_j = min(p[j] - 1, (G - score - 1) // (100 * (j + 1)) + 1)
            score += num_j * 100 * (j + 1)
            num_tmp += num_j

    if score >= G:
        num.append(num_tmp)

ans = min(num)
print(ans)

Submission status: Accepted

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

question = 0

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

question = []

for x in range(2**D):
    # print(bin(x))
    questioni = 0
    not_comp = []
    score = 0
    for y in range(D):
        # print( bin(1<<y&x) )
        if 1 << y & x:
            score += c[y] + p[y]*100*(y+1)
            questioni += p[y]
        else:
            not_comp.append(y)
    for y in not_comp[::-1]:
        for z in range(p[y]-1):
            if score < G:
                score += 100*(y+1)
                questioni += 1
            else:
                break
    if score >= G:
        question.append(questioni)

print(min(question))

Submission status: Accepted

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

l = list(itertools.product(range(2), repeat=D))

comp = []
for i in range(len(l)-1):
    score = 0
    count = 0
    m = -100
    for j in range(D):
        if l[i][j] == 1:
            score += (j+1) * 100 * p[j] + c[j]
            count += p[j]
        elif l[i][j] == 0:
            m = max(m, j)
    tmp = [score, count]
    comp.append(tmp)
    for j in range(p[m]-1):
        score += (m+1) * 100 * 1
        count += 1
        tmp = [score, count]
        comp.append(tmp)

score = 0
count = 0
for i in range(D):
    score += (i+1) * 100 * p[i] + c[i]
    count += p[i]
tmp = [score, count]
comp.append(tmp)    

#print(comp)

ans = []
for i in range(len(comp)):
    if comp[i][0] >= G:
        ans.append(comp[i][1])

ans = min(ans)
print(ans)

Submission status: Accepted

Solution code:
def main():
    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 = float('inf')
    for i in range(1 << D):
        cnt = 0
        score = 0
        tmp = 0
        for j in range(D):
            if (i >> j) & 1:
                score += c[j] + 100 * (j + 1) * p[j]
                cnt += p[j]
            else:
                tmp = j
                
        if score < G:
            for k in range(1,p[tmp]):
                score += 100 * (tmp + 1)
                cnt += 1
                if score >= G:
                    break
        
        if score >= G:
            ans = min(ans,cnt)
    
    print(ans)


main()

Submission status: Accepted

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

score = 0
p = []
c = []
for i in range(d):
    p_tmp, c_tmp = [int(i) for i in input().split()]
    p.append(p_tmp)
    c.append(c_tmp)

num = []
for i in range(2**d):
    num_tmp = 0
    score = 0
    not_comp = []
    for j in range(d):
        if i >> j & 1:
            score += p[j] * 100 * (j+1) + c[j]
            num_tmp += p[j]
        else:
            not_comp.append(j)

    for j in not_comp[::-1]:
        if score < g:
            num_j = min(p[j]-1, (g-score-1)//(100*(j+1))+1)
            score += num_j * 100*(j+1)
            num_tmp += num_j
    if score >= g:
        num.append(num_tmp)

ans = min(num)
print(ans)

Submission status: Accepted

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

score = 0
p = []
c = []
for i in range(d):
    p_tmp, c_tmp = [int(i) for i in input().split()]
    p.append(p_tmp)
    c.append(c_tmp)

num = []
for i in range(2**d):
    num_tmp = 0
    score = 0
    not_comp = []
    for j in range(d):
        if i >> j & 1:
            score += p[j] * 100 * (j+1) + c[j]
            num_tmp += p[j]
        else:
            not_comp.append(j)

    for j in not_comp[::-1]:
        for k in range(p[j]-1):
            if score < g:
                score += 100 * (j+1)
                num_tmp += 1
            else:
                break
        else:
            continue
        break
    if score >= g:
        num.append(num_tmp)

ans = min(num)
print(ans)

Submission status: Accepted

Solution code:
D, G = map(int, input().split())
PC = [0] + [tuple(map(int, input().split())) for _ in range(D)]
SHORT_OF_SCORE = 10**9


def solve(p, g):
    if p == 0:
        return SHORT_OF_SCORE

    # 問題pを解く場合
    case_solve_p = min(g//(p*100), PC[p][0])
    reward = 100 * p * case_solve_p + \
        (PC[p][1] if case_solve_p == PC[p][0] else 0)

    if reward < g:
        case_solve_p += solve(p-1, g-reward)

    # 問題pを解かない場合
    case_not_solve_p = solve(p-1, g)
    return min(case_solve_p, solve(p-1, g))


print(solve(D, G))

Submission status: Accepted

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

cnts = []
bonuses = []
for i in range(D):
    a, b = [int(_) for _ in input().split()]
    cnts.append(a)
    bonuses.append(b)

# bonus で全探索
ans = 1e12
for i in range(2 ** D + 1):
    j = i
    bidx = []
    cnt = 0
    point = 0
    for j in range(D):
        if (i >> j) & 1:
            bidx.append(j)
            point += bonuses[j] + cnts[j] * 100 * (j + 1)
            cnt += cnts[j]

    for j in range(D - 1, -1, -1):
        if point >= G: break
        if j in bidx: continue
        for k in range(1, cnts[j] + 1):
            if point >= G: break
            point += (j + 1) * 100
            cnt += 1
    ans = min(cnt, ans)
print(ans)

Submission status: Accepted

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

solve_lis = []
for i in range(2**d):
    solve = 0
    point = 0
    way = True
    for j in range(d-1, -1, -1):
        if ((i >> j) & 1):
            solve += p[j]
            point += p[j] * 100 * (j + 1) + c[j]
        elif way == True:
            index = j
            way = False
    for k in range(p[index]):
        if k > 0:
            solve += 1
            point += 100 * (index + 1)
        if point >= g:
             solve_lis.append(solve)
    
print(min(solve_lis))

Submission status: Accepted

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

def all_green(t,s):
    if t == -1:
        return float('inf')
    num = min(PC[t][0],s//(100*(t+1)))
    k = num * 100 * (t+1)
    if num == PC[t][0]:
        k += PC[t][1]
    if k < s:
        num += all_green(t-1,s-k)
    return min(num,all_green(t-1,s))
print(all_green(D-1,G))

Submission status: Accepted

Solution code:
d, g = map(int, input().split())
dic = {}
ans = 9999999
for i in range(1, d+1):
    dic[i] = list(map(int, input().split()))

for i in range(2**d):
    total = 0
    count = 0
    select_list = list(range(1, d+1))
    for j in range(d):
        if (i >> j) & 1:
            num = dic[j+1][0]
            total += 100*(j+1)*num + dic[j+1][1]
            count += dic[j+1][0]
            select_list.remove(j+1)

    if total >= g:
        if count < ans:
            ans = count
            continue
        else:
            continue

    else:
        select = max(select_list)
        select_num = dic[select][0]
        for _ in range(select_num):
            total += 100*select
            count += 1

            if total >= g:
                if count < ans:
                    ans = count
                    break
                else:
                    break

print(ans)

Submission status: Accepted

Solution code:
from operator import itemgetter

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

def com(d, s, ans):
    if d == D:
        ans.append(s)
        return ans
    a = s[:]
    a.append(1)
    ans = com(d+1, a, ans)
    b = s[:]
    b.append(0)
    ans = com(d+1, b, ans)
    return ans

L = com(0, [], [])
ans = 10000
for l in L:
    point = 0
    probs = 0
    uncom = []
    for i, com in enumerate(l):
        if com == 0:
            uncom.append(i)
        else:
            p, c = PC[i]
            point += (i+1)*100*p + c
            probs += p
    #print(probs, l)
    if point >= G:
        ans = min(ans, probs)
        continue
    uncom.sort(reverse=True)
    re = G - point
    for un in uncom:
        p, c = PC[un]
        #print(re, probs, p)
        if (un+1)*100*(p-1) >= re:
            rem = 1 if re % ((un+1)*100) > 0 else 0
            probs += re // ((un+1)*100) + rem
            re = 0
            break
        re -= (un+1)*100*(p-1)
        probs += p-1
    #print(probs)
    if re > 0:
        continue
    ans = min(ans, probs)
print(ans)