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:
# WIP (WA)
import sys

sys_input = sys.stdin.readline

D, G = map(int, sys_input().split())
pc_list = [tuple(map(int, sys_input().split())) for _ in range(D)]

n_solved = 10000000000
for i in range(1 << D):
    score_per_combi = 0
    combi = []
    tmp_n_solved = 0

    for j in range(D):
        if (i >> j) & 1:
            p = pc_list[j][0]
            c = pc_list[j][1]
            score_per_combi += (j + 1) * 100 * p + c
            combi.append(j)
            tmp_n_solved += p

    if tmp_n_solved == 0:
        continue
    if score_per_combi < G:
        continue

    # problems are already sorted
    # -> check if these were oversolved
    for problem_idx in combi:
        for solved_num in range(pc_list[problem_idx][0]):
            diff = None
            if solved_num == 0:
                c = pc_list[problem_idx][1]
                diff = (problem_idx + 1) * 100 + c
            else:
                diff = (problem_idx + 1) * 100
            score_per_combi -= diff
            tmp_n_solved -= 1

            if score_per_combi < G:
                tmp_n_solved += 1
                score_per_combi += diff
                break
            # Not finish innner loop -> continue outer loop
            else:
                continue
            # Finish innner loop -> break outer loop
            break

    # Check if mininum n_solved are updated
    if tmp_n_solved < n_solved:
        n_solved = tmp_n_solved

print(n_solved)

Submission status: Accepted

Solution code:
"""
https://atcoder.jp/contests/abc104/tasks/abc104_c
"""
D,G=map(int,input().split())
l = [list(map(int, input().split()))  for _ in range(D)]

minP = 10 ** 100
for i in range(2**D):
  point, tmpP = 0,0
  for j in range(D):
    if (i>>j)&1:
      point += 100*l[j][0]*(j+1) + l[j][1]
      tmpP += l[j][0]
  if point>=G:
    minP = min(minP, tmpP)
  else:
    for j in range(D-1,-1,-1):
      if (i>>j)&1:
        continue
      else:
        for _ in range(l[j][0]):
          point += (j+1)*100
          tmpP += 1
          if point>=G:
            break
      if point >= G:
        break
  minP = min(minP, tmpP)
print(minP)

Submission status: Accepted

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

# remainは、まだ解いていない問題
def dfs(i, sum, count, remain):
    global answer
    #iがD-1まででどの問題を全部解くかどうかが決定されている
    if i == D:
        # sumがGに達していない場合、remainの中で最大のものを使う　
        if sum < G:
            use = max(remain)
            n = min(PC[use-1][0], -(-(G-sum)//(use*100)))
            count += n
            sum += 100*use*n
        if sum >= G:
            answer = min(answer, count)
    # この問題を解くかどうか２つの場合で、次の問題に渡して再帰関数を使う
    else:
        dfs(i+1, sum, count, remain)
        dfs(i+1, sum + 100*(i+1)*PC[i][0] + PC[i][1], count + PC[i][0], remain-{i+1})
        
answer = float('inf')
dfs(0, 0, 0, set(range(1, D+1)))
print(answer)

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 = 10 ** 9
for bit in range(2 ** d):
    cnt = 0
    score = 0

    # ボーナス分の足し込み
    for i in range(d - 1, -1, -1):
        if bit >> i & 1 == 1:
            cnt += p[i]
            score += p[i] * (i + 1) * 100 + c[i]
    
    if score >= g:
        ans = min(ans, cnt)
    else:
        for i in range(d - 1, -1, -1):
            if bit >> i & 1 == 1:
                continue
            
            for j in range(p[i]):
                if score >= g:
                    break

                cnt += 1
                score += (i + 1) * 100
            
        if score >= g:
            ans = min(ans, cnt)

print(ans)

Submission status: Accepted

Solution code:
from math import ceil


def log(s):
    # print("| " + str(s), file=sys.stderr)
    pass


def output(x):
    print(x, flush=True)


def input_ints():
    return map(int, input().split())


cache = dict()


def solve(goal, count, meta):
    if (goal <= 0):
        return count

    s = frozenset([m[1] for m in meta])
    if s in cache:
        return cache[s]

    min_count = 999999999

    for m in meta:
        meta2 = list(meta)
        meta2.remove(m)
        c = solve(goal - m[3], count + m[0], meta2)
        if c < min_count:
            min_count = c

    for m in reversed(meta):
        if goal - m[0] * m[1] > 0:
            continue
        c = count + ceil(goal / m[1])
        if c < min_count:
            min_count = c
        break

    cache[s] = min_count

    return min_count


def main():
    d, goal = tuple(input_ints())

    meta = list()
    for i in range(d):
        problems, bonus = tuple(input_ints())
        score = (i + 1) * 100
        meta.append((problems, score, bonus, score * problems + bonus))

    count = solve(goal, 0, meta)
    print(count)


main()

Submission status: Accepted

Solution code:
def main():
    from math import ceil
    D, G = (int(i) for i in input().split())
    pc = [[int(i) for i in input().split()] for j in range(D)]
    ans = float('inf')
    for bit in range(1<<D):
        completed = []
        tmp = 0
        cur = 0
        for i in range(D):
            if bit & (1<<i):
                completed.append(i)
        for c in completed:
            tmp += (100*(c+1)*pc[c][0] + pc[c][1])
            cur += pc[c][0]
        for d in range(D)[::-1]:
            if d in completed:
                continue
            less = ceil((max(G - tmp,0))/(100 * (d+1)))
            if pc[d][0] < less:
                continue
            tmp += 100*(d+1)*less
            cur += less
            break
        if tmp >= G:
            ans = min(ans,cur)
    print(ans)
if __name__ == '__main__':
    main()

Submission status: Accepted

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

ans = float("inf")
for i in range(2**D):
    comp_list = [0]*D
    tmp_num = 0
    tmp_score = 0
    for j in range(D):
        if (i >> j) & 1:
            comp_list[j] = 1
            tmp_num += P[j]
            tmp_score += P[j]*(j+1)*100 + C[j]
    if tmp_score >= G:
        if tmp_num < ans:
            ans = tmp_num
    else:
        list_notcomp= [k for k in range(D) if comp_list[k] == 0]
        if len(list_notcomp) != 0:
            if math.ceil((G - tmp_score) / (100*(max(list_notcomp) + 1))) < P[max(list_notcomp)]:
                tmp_num += math.ceil((G - tmp_score) / (100*(max(list_notcomp) + 1)))
                if tmp_num < ans:
                    ans = tmp_num
print(ans)

Submission status: Accepted

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

# より少ない問題数で目標を達成したとき、
# 0以上のコンプリートした問題群と、コンプリートしていない1種類の問題が存在する。
# コンプリートした問題群のパターンを全探索する。
ans = 1001
for i in range(1<<D):
  q = 0
  s = 0
  for j in range(D):
    if (i>>j)&1 == 1:
      q += P[j]
      s += 100*(j+1)*P[j] + C[j]
  #print(i,j,q,s)
  # コンプリートした問題群だけで目標を達成した場合
  if i == (1<<D)-1 or s >= G:
    ans = min(ans,q)
  # コンプリートした問題群だけで目標を達成しなかった場合
  # 残りの問題のうち、最も点数が高い問題を、コンプリートしない程度に解く
  else:
    for k in range(D-1,-1,-1):
      if (i>>k)&1 == 0:
        break
    q1 = 0
    while (s < G and q1 < P[k]-1):
      s += 100*(k+1)
      q1 += 1
    #print(i,j,q,s,k,q1)
    if s >= G:
      ans = min(ans,q+q1)
print(ans)

Submission status: Accepted

Solution code:
D,G=map(int,input().split())
li=[list(map(int,input().split())) for i in range(D)]
min_n=float('inf')
for i in range(2**D):
    s=0
    n=0
    for b in range(D):
        if (i >> b) & 0b1 == 1:
            s += li[b][0] * (b+1) * 100 + li[b][1]
            n += li[b][0]
    if s < G:
        for b in range(D):
            if ~(i >> (D-b-1)) & 0b1 == 1:
                if (D-b)*100 * li[D-b-1][0] < G-s:
                    n = float('inf')
                    break
                else:
                    n += -(-(G-s) // ((D-b)*100))
                    break
    min_n = min(min_n,n)
print(min_n)

Submission status: Accepted

Solution code:

import sys
input = sys.stdin.readline
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
# A = [ int(input()) for _ in range(N) ]
##############################

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

ans = INF
for i in range(1 << D):
    score = 0
    count = 0
    for j in range(D):
        if ((i >> j) & 1):
            score += (j+1)*P[j]*100+C[j]
            count += P[j]
        else:
            basic = j

    remain = G-score
    if remain <= 0:
        ans = min(ans, count)
        continue

#    print(remain, count, ans)

    # まだ残ってる場合、もっとも高いやつから
    if (remain - ( (P[basic]-1)*(basic+1)*100)) > 0:
        # 全部使っても駄目
        continue

    p = P[basic]
    while p > 1 and remain > 0:
        remain -= (basic+1)*100
        p -= 1
        count += 1

    if remain <= 0:
        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)]
res = 1<<29
for bit in range(1<<D):
  ans = 0
  num = 0
  for j in range(D):
    if bit&(1<<j):
      ans += pc[j][0]*(j+1)*100+pc[j][1]
      num += pc[j][0]
  if ans >=G:
    res = min(num,res)
  else:
    for j in range(D-1,-1,-1):
      if bit&(1<<j):
        continue
      else:
        for i in range(pc[j][0]):
          if ans>=G:
            break
          ans += 100*(j+1)
          num +=1
    res = min(num,res)
print(res)

Submission status: Accepted

Solution code:
D,G = [int(x) for x in input().split()]
pc = []
for i in range(D):
  p,c = [int(x) for x in input().split()]
  pc.append([p,c])
res = 1<<29
for bit in range(1<<D):
  ans = 0
  num = 0
  for j in range(D):
    if bit&(1<<j):
      ans += pc[j][0]*(j+1)*100+pc[j][1]
      num += pc[j][0]
  if ans >=G:
    res = min(num,res)
  else:
    for j in range(D-1,-1,-1):
      if bit&(1<<j):
        continue
      else:
        for i in range(pc[j][0]):
          if ans>=G:
            break
          ans += 100*(j+1)
          num +=1
    res = min(num,res)
print(res)

Submission status: Accepted

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

min_count = 10 ** 100

for i in range(2 ** D):
    point,cnt = 0, 0
    for j in range(D):
        if i >> j & 1:
            point += pc[j][0] * 100 * (j + 1) + pc[j][1]
            cnt += pc[j][0]
    if point >= G:
        min_count = min(min_count, cnt)
    else:
        for j in range(D-1, -1, -1):
            if i >> j & 1:
                continue
            else:
                for _ in range(pc[j][0]):
                    point += (j+1) * 100
                    cnt += 1
                    if point >= G:
                        break
            if point >= G:
                break
    min_count = min(min_count, cnt)
print(min_count)

Submission status: Accepted

Solution code:
### ABC104C - All Green
def rec(score: int, idx: int) -> int:
    if idx == 0:
        return float("inf")
    point, (num, bonus) = idx * 100, A[idx]
    cnt = min(score // point, num)
    cur_score = cnt * point + bonus if cnt == num else cnt * point
    rest = score - cur_score
    if rest > 0:
        cnt += rec(rest, idx - 1)
    return min(cnt, rec(score, idx - 1))


def main():
    global A
    D, G = map(int, input().split())
    A = [(0, 0)] + [tuple(map(int, input().split())) for _ in range(D)]
    ans = rec(G, D)
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import itertools
import sys

input = sys.stdin.readline


class AtCoder:
    def main(self):
        D, G = map(int, input().split())

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

        ans = 10 * 100
        for i in range(D + 1):
            for comb in itertools.combinations(range(1, D + 1), i):
                score = 0
                ac = 0

                for index in comb:
                    score += c[index] + p[index] * index * 100
                    ac += p[index]

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

                for j in range(1, D + 1)[::-1]:
                    if j in comb:
                        continue

                    if score >= G:
                        break

                    for _ in range(1, p[j]):
                        score += (j * 100)
                        ac += 1

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

                            break
        print(ans)


# Run main
if __name__ == '__main__':
    AtCoder().main()

Submission status: Accepted

Solution code:
from collections import defaultdict

def getlist():
	return list(map(int, input().split()))

#初期化
D, G = getlist()
G = G // 100
bit = []
for i in range(D):
	p, c = getlist()
	bit.append([i + 1, p, c // 100])

#bit全探索
ans = float("inf")

for i in range(1 << D):
    score = 0
    lest = []
    val = 0
    for j in range(D):
        if ((i >> j) & 1) == 1:
            lest.extend([bit[j][0]] * bit[j][1])
        else:
        	score += bit[j][0] * bit[j][1] + bit[j][2]
        	val += bit[j][1]
    lest = sorted(lest)
    lest = lest[::-1]
    for j in lest:
    	if score >= G:
    		break
    	else:
    		val += 1
    		score += j
    ans = min(ans, val)

print(ans)

Submission status: Accepted

Solution code:
d,g = map(int,input().split())
ary = [list(map(int,input().split())) for _ in range(d)]
s = set(i for i in range(d))
ans = float("Inf")
for i in range(2**d):
    a = []
    total,count = 0,0
    for j in range(d):
        if i >> j & 1:
            a.append(j)
    for x in a:
        total += 100*(x+1)*ary[x][0]+ary[x][1]
        count += ary[x][0]
    if total >= g:
        ans = min(ans,count)
        continue
    for y in sorted(s - set(a),reverse=True):
        if total + 100*(y+1)*(ary[y][0]-1) >= g:
            count += -(-(g-total) // (100*(y+1)))
            ans = min(ans,count)
            break
        total += 100*(y+1)*(ary[y][0]-1)
        count += ary[y][0]-1
    if total >= g:
        ans = min(ans,count)
print(ans)

Submission status: Accepted

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

    n = len(pc)
    ans = float("inf")

    for i in range(2**n):
        point, cnt = 0, 0
        for j in range(n):
            if (i>>j) & 1:
                point += (j+1)*100*pc[j][0] + pc[j][1]
                cnt += pc[j][0]
        if point >= g:
            ans = min(ans, cnt)
        # print(cnt, point)
        else:
            for j in range(n-1, -1, -1):
                if (i >> j) & 1:
                    continue
                else:
                    for k in range(pc[j][0]):
                        if point >= g:
                            ans = min(ans, cnt)
                            break
                        point += (j+1)*100
                        cnt += 1
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:

def dfs(i, sum, count, nokori):
  global ans
  if i == D:    
    # G 点に満たなければ nokori のうち一番大きいものを解く
    if sum < G:
      use = max(nokori)
      n = min(PC[use-1][0], -(-(G-sum)//(use*100)))
      count += n
      sum += n*use*100
    if sum >= G:
      ans = min(ans, count)
  else:
    # 総合スコア、解いた問題数、まだ解いてない問題を更新
    dfs(i+1, sum, count, nokori)
    dfs(i+1, sum+PC[i][0]*(i+1)*100+PC[i][1],
       count+PC[i][0], nokori-{i+1})

D, G = map(int, input().split())
PC = [list(map(int, input().split())) for i in range(D)]
ans = float("inf")
    
dfs(0,0,0,set(range(1, D+1)))    
print(ans)

Submission status: Accepted

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

p, c = zip(*PC)

min_count = 10**18
for i in range(1<<D):
    h = -1
    point = 0
    count = 0
    for j in range(D):
        if (i>>j)%2:
            point += 100*(j+1)*p[j] + c[j]
            count += p[j]
        else:
            h = j
    if h > -1 and G > point:
        x = -(-(G-point)//(100*(h+1)))
        if x > p[h]:
            continue
        count += x
    min_count = min(min_count, count)

print(min_count)

Submission status: Accepted

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

cs = [100*(i+1)*p + c for i, (p, c) in enumerate(pc)]
ans = float("inf")

for i in range(1<<D):
    flag = [False] * D
    score = 0
    num = 0
    for j in range(D):
        # 100jを解ききる
        if (i >> j) & 1:
            flag[j] = True
            score += cs[j]
            num += pc[j][0]

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

    last = -1
    for j in range(D)[::-1]:
        if not flag[j]:
            last = j
            break

    for _ in range(pc[j][0]-1):
        score += 100*(j+1)
        num += 1
        if score >= G:
            ans = min(ans, num)
            break

print(ans)

Submission status: Accepted

Solution code:
'''
1.全完する問題をbit全探索で選ぶ
2.残った問題に対して、1問辺り点が高い順に解いてく
'''

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

n=len(PC)
ans=float('inf')
for i in range(2**n):
  point,cnt=0,0
  for j in range(n): # 全完する問題選択
    if i>>j & 1:
      point+=(j+1)*100*PC[j][0] + PC[j][1]
      cnt+=PC[j][0]
  if point>=g:
    ans=min(ans,cnt)
  else:
    for j in range(n-1,-1,-1): # 1問の点が高い問題解いてく
      if i>>j & 1: # すでに全完してたら飛ばす
        continue
      else:
        for k in range(PC[j][0]):
          if point>=g:
            ans=min(ans,cnt)
            break
          point+=(j+1)*100
          cnt+=1
print(ans)

Submission status: Accepted

Solution code:
D, G = map(int, input().split())
dic = [0]*(D+1)
for i in range(D):
  p, c = map(int, input().split())
  dic[i+1] = (p,c)
ans = 10**9
for i in range(2**D):
  ls = []
  x = i
  v = 0
  count = 0
  for j in range(D):
    if x%2==1:
      ls += [j+1]
    x = x>>1
  for h in ls:
    p, c = dic[h]
    v += p*h*100 + c
    count += p
  if G>v:
    for j in range(D, 0, -1):
      if not j in ls:
        break
    else:
      continue
    m = dic[j][0]
    while m>1:
      v += j*100
      count += 1
      m -= 1
      if v>=G:
        break
    else:
      continue
  if count<ans:
    ans = count
print(ans)

Submission status: Accepted

Solution code:
import itertools
D,G = map(int,input().split())
S = []
for _ in range(D):
    S.append(list(map(int,input().split())))
cmin = 10**4
for x in itertools.product((0,1),repeat=D):
    cnt = 0
    s = 0
    for i in range(D):
        if x[i]==1:
            p,c = S[i][0],S[i][1]
            s += 100*(i+1)*p+c
#     print("s={},x={}".format(s,x))
    if s>=G:
        ind = x.index(1)
        s1 = 0
        for i in range(ind+1,D):
            if x[i]==1:
                s1 += 100*(i+1)*S[i][0]+S[i][1]
                cnt += S[i][0]
        if s1>=G:
            continue
        t = 0
        while t<S[ind][0]:
            s1 += 100*(ind+1)
            cnt += 1
            if s1>=G:
                break
            t += 1
        cmin = min(cmin,cnt)
#         print("cmin={},x={}".format(cmin,x))
print(cmin)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
D,G = map(int, input().split())
L = []
for i in range(D):
    L.append([int(x) for x in input().split()])
    
for i in range(D):
    L[i].append(L[i][0]*(i+1)*100+L[i][1])
    
ans_list = []
for i in range(2**D):
    temp = bin(i)
    score = 0
    cnt = 0
    used = []
    for j in range(len(temp)-2):
        if temp[-1-j] == "1":
            score += L[j][2]
            used.append(j)
            cnt += L[j][0]
    num = D-1
    while num in used:
        num -= 1
    for j in range(L[num][0]-1):
        if score < G:
            score += (num+1)*100
            cnt += 1
    if score >= G:
        ans_list.append(cnt)
    
print(min(ans_list))

Submission status: Accepted

Solution code:
d,g = list(map(int,input().split()))
a = [list(map(int,input().split())) for _ in range(d)]
s = set(range(d))
ans = float("Inf")
x = []
for i in zip(*a):
    x.append(list(i))
c = []
for i in range(2**d):
    b = []
    for j in range(d):
        if i>>j & 1:
            b.append(j)
    c.append(b)
for i in c:
    d = 0
    count = 0
    for j in i:
        d += (100*(j+1)) * a[j][0] + a[j][1]
        count += a[j][0]
    if d < g:
        for x in sorted(s - set(i),reverse=True):
            for y in range(a[x][0]):
                if d >= g:
                    break
                d += 100*(x+1)
                count += 1
    if d < g:continue
    ans = min(ans,count)
print(ans)

Submission status: Accepted

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

def ceil(a, b):
    if a%b == 0:
        return a//b
    else:
        return a//b + 1

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

    ans = int(1e9)
    for i in range(2**D):
        tmp = 0
        rest = []
        count = 0
        for j in range(D):
            if i&1:# コンプリートする問題
                tmp += (j+1) * pc[j][0] + pc[j][1]//100
                count += pc[j][0]
            else:
                rest.append((j+1, pc[j][0]))
            i >>= 1
        rest = sorted(rest, reverse=True)
        rest_point = G - tmp
        if rest_point <= 0:# すでに足りている
            ans = min(ans, count)
        elif len(rest) > 0:# 不足分を補う必要がある
            plus = ceil(rest_point, rest[0][0])
            if plus < rest[0][1]:# p-1問以内ですむ
                ans = min(ans, count + plus)
        else:# すべて使っても足りない
            pass
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import copy
d,g=map(int,input().split())
pc=[]
for _ in range(d):
	x,y=map(int,input().split())
	pc.append([x,y])
pcc=copy.deepcopy(pc)
def two(x):
	p=bin(x)
	return "0"*10+p[2:]
q=[]
for i in range(2**d):
	pcc=copy.deepcopy(pc)
	ans=0
	cnt=0
	k=[]
	for j in range(d):
		if two(i)[-j-1]=="1":
			ans+=100*pc[j][0]*(j+1)+pc[j][1]
			cnt+=pc[j][0]
		else:
			k.append(j)
	p=1
	if ans<g:
		while ans<g:
			if p>len(k):
				cnt+=10**15
				break
			if pcc[k[-p]][0]<=1:
				p+=1
			if p>len(k):
				cnt+=10**15
				break
			ans+=(k[-p]+1)*100
			pcc[k[-p]][0]-=1
			cnt+=1
	q.append(cnt)
print(min(q))

Submission status: Accepted

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

for _ in range(d):
    P,C = map(int, input().split( ))
    p.append(P)
    c.append(C)
ans = sum(p)

for i in range(2**d):
    comp = []
    non_comp = []
    cnt = [0]*(d+1)
    sm = 0

    for j in range(1,d+1):
        if i>>(j-1) & 1 == 0:
            comp.append(j)
        else:
            non_comp.append(j)
        non_comp.reverse()
    for j in comp:
        sm += p[j]*j*100 + c[j]
        cnt[j] = p[j]
    for j in non_comp:
        if sm >= g:
            break
        cnt[j] = min(p[j]-1, (g - sm)//(j*100) + 1)
        sm += cnt[j]*j*100
        if sm - j*100>=g:
            cnt[j] -= 1
    tot = sum(cnt)
    if sm >=g:
        ans = min(ans, tot)
        #print(cnt)

print(ans)

Submission status: Accepted

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

ans = 10**9
for i in range(2**D):
    s, num, rest = 0, 0, -1
    for j in range(D):
        if i >> j & 1:
            s += 100 * (j+1) * p[j] + c[j]
            num += p[j]
        else:
            rest = j
    if s < G:
        s1 = 100 * (rest + 1)
        need = ceil((G - s) / s1)
        if need >= p[rest]:
            continue
        num += need
    ans = min(ans, num)

print(ans)

Submission status: Accepted

Solution code:
# ABC104c
import sys
import math
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 6)

d, g = map(int, input().split())
p = [list(map(int, input().split())) for _ in range(d)]
toku = [False]*d
# 全完を2^D通り探索


def dfs(i, su, cnt):
    #print(i, su, cnt)
    if (i >= d):
        if (su >= g):  # 目標点を超えている場合
            return cnt
        # 超えていない場合は、全完していない問題のうち一番点数が高い物を解いていこう
        for j in range(d - 1, -1, -1):
            if (toku[j]):
                continue
            tokuzo = min(p[j][0], math.ceil((g - su) / (100 * (j + 1))))
            if (su + 100 * (j + 1) * tokuzo >= g):
                return cnt + tokuzo
            return 99999

    # i問目を全完する場合としない場合
    toku[i] = True
    suru = dfs(i + 1, su + (i + 1) * p[i][0]
               * 100 + p[i][1], cnt + p[i][0])
    toku[i] = False
    sinai = dfs(i + 1, su, cnt)
    # print(i, suru, sinai)
    return min(suru, sinai)


print(dfs(0, 0, 0))

Submission status: Accepted

Solution code:
import math
def solve():
  d,g = (int(i) for i in input().split())
  query = []
  ans = 10**15
  for i in range(d):
    p,c = (int(i) for i in input().split())
    query.append((p,c,(i+1)*100))
  for i in range(2**d):
    ct = 0
    point = 0
    use = [False]*d
    for j in range(d):
      if (i>>j)&1 == 1:
        use[j] = True

    for m in range(d):
      if use[m]:
        tp,tc,ti = query[m]
        ct += tp
        point += ti*tp+tc
        
    if point >= g:
      ans = min(ans,ct)
    else:
        for l in range(d):
          if use[d-l-1]:
            continue
          else:
            tp,tc,ti = query[d-l-1]
            twant = math.ceil((g-point)/ti)
            if tp >= twant:
              point += twant*ti
              ct += twant

            if point >= g:
              ans = min(ans,ct)
              break


            

  print(ans)
    
    
solve()

Submission status: Accepted

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

E=[]
for i in range(2**D):
  tmp=0
  cnt=0
  for j in range(D):
    if (i>>(D-j-1))&1:
      tmp+=(j+1)*100*PC[j][0]+PC[j][1]
      cnt+=PC[j][0]
  E.append([cnt,tmp])
#print(E)

for i in range(2**D):
  if E[i][1]<G:
    tmp=0
    cnt=0
    for j in range(D-1,-1,-1):
      if (i>>(D-j-1))&1==0:
        for k in range(PC[j][0]):
          tmp+=100*(j+1)
          cnt+=1
          if E[i][1]+tmp>=G:
            break
      else:
        continue
      break
    E[i][0]+=cnt
    E[i][1]+=tmp
#print(E)

E.sort()
#print(E)

for i in E:
  if i[1]>=G:
    print(i[0])
    break

Submission status: Accepted

Solution code:
d, g = map(int, input().split())
pc = [list(map(int, input().split())) for _ in range(d)]
m = 10000
for i in range(2**d):
    cur = bin(i)[2:].zfill(d)
    s = 0
    c = 0
    nu = []
    for i in range(d):
        if cur[i] == '0':
            nu.append(i)
        else:
            s += (i+1) * 100 * pc[i][0] + pc[i][1]
            c += pc[i][0]
    if g > s:
        if g - s <= (nu[-1]+1) * 100 * pc[nu[-1]][0]:
            c += (g-s-1)//((nu[-1]+1)*100)+1
            m = min(c, m)
    else:
        m = min(c, m)
print(m)

Submission status: Accepted

Solution code:
d,g = map(int,input().split())
pc = [list(map(int,input().split())) for i in range(d)]
m = 10000
for i in range(2**d):
  cur = bin(i)[2:]
  cur = '0' * (d-len(cur)) + cur
  s = 0
  c = 0
  nu = [] #not use
  for i in range(d):
    if cur[i] == '0':
      nu.append(i)
    else:
      s += (i+1) * 100 * pc[i][0] + pc[i][1]
      c += pc[i][0]
  if s < g:
    if g - s <= (nu[-1]+1) * 100 * pc[nu[-1]][0]:
      c += (g-s-1)//((nu[-1]+1)*100) + 1
      m = min(c,m)
  else:
    m = min(c,m)
print(int(m))