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 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:
import math

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

ans = 100000000
for bit in range(1 << D):
    s = 0
    ans_ = 0
    li = 0
    for i in range(D):
        if bit & (1 << i):
            s += (i+1) * 100 * pc[i][0] + pc[i][1] 
            ans_ += pc[i][0]
        else:
          li = i  
    if s < G:
        lv = 100 * (li + 1)
        need = int(math.ceil((G - s) / lv))
        if pc[li][0] < need:
            continue
        ans_ += need
    ans = min(ans, ans_)

print(int(ans))

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
D, G = map(int, input().split(' '))
p_c_pairs = [((i+1) * 100, list(map(int, input().split(' ')))) for i in range(D)]

import math
ans = float('inf')
p_c_pairs.sort(key=lambda x: -x[0])
for d in range(1<<D):
    # print(bin(d))

    cnt = 0
    g = G
    for i in range(D):
        if 1 & (d >> i):
            score, (p, c) = p_c_pairs[i]
            g -= score * p + c
            cnt += p

    if g > 0:
        for i in range(D):
            if not (1 & (d >> i)):
                score, (p, c) = p_c_pairs[i]
                n = min(p, int(math.ceil(g/score)))
                g -= score * n
                cnt += n
                break

    # print(bin(d), g)
    if g <= 0:
        ans = min(ans, cnt)

print(ans)

Submission status: Accepted

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

for i in range(d):
    L.append([int(i) for i in input().split()])

C=[L[i][0]*(i+1)*100 for i in range(d)]

import itertools
itr=list(itertools.product([0,1],repeat=d))

def calc(key,g):
    cnt=0
    sco=0
    for i in range(d):
        if key[i]==1:
            cnt+=L[i][0]
            sco+=L[i][0]*(i+1)*100+L[i][1]
    rem=g-sco
    #print(rem)
    if rem<=0:
        return cnt
    for i in range(d-1,-1,-1):
        if key[i]==0:
            if rem-L[i][0]*(i+1)*100<=0:
                return cnt+((rem-1)//((i+1)*100))+1
            else:
                rem-=L[i][0]*(i+1)*100
                cnt+=L[i][0]
    return 10**7

ans=10**7
for key in itr:
    #print(key,calc(key,g),ans)
    ans=min(calc(key,g),ans)
print(ans)

Submission status: Accepted

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

ans = 10**3+1
for i in range(2**d):
    tmp = 0
    tmp_ans = 0
    t = [0]*d
    for j in range(d):
        if (i>>j)&1:
            tmp += 100*(j+1)*p[j] + c[j]
            tmp_ans += p[j]
            t[j] = 1
    if tmp < g:
        for k in range(d-1,-1,-1):
            if t[k] == 0:
                if tmp+100*(k+1)*(p[k]-1) < g:
                    tmp_ans += 10**3+1
                else:
                    if (g-tmp)%(100*(k+1)) == 0:
                        tmp_ans += (g-tmp)//(100*(k+1))
                    else:
                        tmp_ans += (g-tmp)//(100*(k+1))+1
                break
    ans = min(tmp_ans,ans)

print(ans)

Submission status: Accepted

Solution code:
# C - All Green

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

ans = 10**18
for i in range(1<<D):
    tmp = 0
    cnt = 0
    for j in range(D):
        if (i>>j)&1:
            p, c = P[j]
            tmp += p * (j+1) * 100 + c
            cnt += p
    if tmp >= G:
        ans = min(ans, cnt)
    else:
        xor_i = i^((1<<D)-1)
        for k in range(D)[::-1]:
            if (xor_i)>>k&1:
                p, c = P[k]
                for _ in range(p):
                    tmp += (k+1) * 100
                    cnt += 1
                    if tmp >= G:
                        ans = min(ans, cnt)
                        break
                else:
                    break
                break

print(ans)

Submission status: Accepted

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

from itertools import product
from itertools import compress


D, G = map(int, input().split())
data = []
for _ in range(D):
    data.append(tuple(map(int, input().split())))

res = []
for bit in product(*((0,1),)*D):
    S = 0
    cnt = 0
    for i, a in enumerate(data):
        p, c = a
        S += (100*(i+1)*p + c)*(bit[i]==0)
        cnt += p*(bit[i]==0)
    if S >= G:
        res.append(cnt)
    else:
        for i, d in enumerate(reversed(bit)):
            if d:
                break
        for k in range(1,data[D-i-1][0]+1):
            cnt += 1
            if S + 100*(D-i)*k >= G:
                res.append(cnt)
                break


print(min(res))

Submission status: Accepted

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

# まだ解いてない配点を nokori として持つ
ans = float("inf")


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


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

Submission status: Accepted

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

ans = 10000
for i in range(2**D):
    count = 0
    no = []
    s = 0
    for j in range(D):
        if (i >> j) & 1:
            count += pc[j][0]
            s += 100*(j+1)*pc[j][0] + pc[j][1]
        else:
            no.append(j)
    if s >= G:
        ans = min(ans, count)
    else:
        for j in no:
            t = s + 100*(j+1)*(pc[j][0] -1)
            if t >= G:
                ans = min(ans, count + math.ceil((G-s) /(100*(j+1))))
print(ans)

Submission status: Accepted

Solution code:
D,G=map(int,input().split())
p=[list(map(int,input().split())) for _ in range(D)]
c=0
d=0
for i in range(D):
  d+=p[i][0]
dp=[[0]*(d+1)for i in range(D)]
for i in range(D):
  for j in range(p[i][0]+1):
    if i==0:
      if j==p[i][0]:
        dp[i][j]+=p[i][1]
      dp[i][j]+=100*j
    else:
      for k in range(c+1):
        if j==p[i][0]:
          dp[i][k+j]=max(dp[i][k+j],dp[i-1][k]+100*j*(i+1)+p[i][1])
        else:
          dp[i][k+j]=max(dp[i][k+j],dp[i-1][k]+100*j*(i+1))
  c+=p[i][0]
for i in range(d+1):
  if dp[D-1][i]>=G:
    print(i)
    break

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
d, g = map(int,input().split())
p = [list(map(int, input().split())) for _ in range(d)]
# 点数の大きい順にソート
p.reverse()

ans = float('inf')

for i in range(1 << d):
    total = 0
    count = 0
    # ボーナスあり
    for j in range(d):
        if (i >> j) & 1:
            total += 100*(d-j)*p[j][0] + p[j][1]
            count += p[j][0]
    if total >= g:
        ans = min(ans, count)
        continue
    # ボーナスなし
    for j in range(d):
        if not (i >> j) & 1:
            for k in range(p[j][0]):
                total += 100*(d-j)
                count += 1
                if total >= g:
                    ans = min(ans, count)
                    break
            break

print(ans)

Submission status: Accepted

Solution code:
from itertools import product
from math import ceil
d, g = map(int, input().split())
pc = [list(map(int, input().split())) for i in range(d)]

ans = 10**9
for bit in product([0, 1], repeat=d):
    score = 0
    probs = 0
    for i, b in enumerate(bit):
        p, c = pc[i]
        if b==1:
            probs+=p
            score+=100*(i+1)*p
            score+=c
    if score >= g:
        ans = min(ans, probs)
    else:
        # greedyに足す
        for i, b in list(enumerate(bit))[::-1]:
            p, c = pc[i]
            if b==1:
                continue
            if score+100*(i+1)*p >= g:
                a = ceil((g-score)/(100*(i+1)))
                probs += a
                score += (100*(i+1))*a
                if a == p: score += c
                break
            else:
                probs += p
                score += (100*(i+1))*p+c
                if score >= g: break
        if score >= g:
            ans = min(ans, probs)
print(ans)

Submission status: Accepted

Solution code:
import bisect


def main():
  D, G = list(map(int, input().split()))
  P = []
  for i in range(1, D+1):
    P.append(tuple(map(int, input().split())))

  # print(D, G, P)
  minp = float('inf')
  for bit in range(1 << D):
    total = 0
    num_p = 0
    bset = set()
    for i in range(D):
      mask = 1 << i
      if bit & mask:
        total += P[i][1] + 100*(i+1)*P[i][0]
        num_p += P[i][0]
        bset.add(i)

    # print(f'bset:{bset}, num_p:{num_p}')

    res = G - total
    if res <= 0:
      if num_p < minp:
        minp = num_p
      continue

    for i in reversed(sorted(set([i for i in range(D)]) - bset)):
      maxv = 100*(i+1) * (P[i][0]-1)

      if res <= maxv:
        num_take = max(min(bisect.bisect(list(range(0, maxv+100*(i+1), 100*(i+1))), res)-1, P[i][0]-1), 1)
        # print(i, list(range(0, maxv, 100*(i+1))))
        # print(f'res:{res} so solve {100*(i+1)} * {num_take}')
        num_p += num_take
        res -= 100*(i+1)*num_take
        if num_p < minp:
          minp = num_p
        break

      res -= maxv
      # print(f'solve {i+1} * {P[i][0]-1}')
      num_p += (P[i][0]-1)

  print(minp)


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

Submission status: Accepted

Solution code:
def resolve():
    """ recursive function"""

    def func(i, sum, cnt, rem):
        nonlocal ans
        if i == D:
            if sum < G:
                use = max(rem)
                n = min(lst[use - 1][0], -(-(G - sum) // ((use) * 100)))
                sum += n * use * 100
                cnt += n
            if sum >= G:
                ans = min(ans, cnt)
        else:
            func(i + 1, sum, cnt, rem)
            func(
                i + 1,
                sum + lst[i][0] * (i + 1) * 100 + lst[i][1],
                cnt + lst[i][0],
                rem - {i + 1})

    D, G = map(int, input().split())
    lst = [list(map(int, input().split())) for x in range(D)]
    ans = float('inf')

    func(0, 0, 0, set(range(1, D + 1)))
    print(ans)

if __name__ == "__main__":
    resolve()

Submission status: Accepted

Solution code:
#! env python
# -*- coding: utf-8 -*-

from collections import defaultdict
import sys, heapq, bisect, math, itertools, string, queue, datetime

# atcoder.main
# Date: 2020/06/20
# Filename: main 
# Author: acto_mini

sys.setrecursionlimit(10 ** 8)
INF = float('inf')

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

for bit in range(1 << D):
    count = 0
    sum = 0
    left_over = set(range(1, D + 1))

    for i in range(D):
        if bit & (1 << i):
            sum += PC[i][0] * (i + 1) * 100 + PC[i][1]
            count += PC[i][0]
            left_over.discard(i + 1)

    if sum < G:
        use = max(left_over)
        n = min(PC[use - 1][0], -(-(G - sum) // (use * 100)))
        count += n
        sum += n * use * 100

    if sum >= G:
        ans = min(ans, count)

print(ans)

Submission status: Accepted

Solution code:
# ABC 104 C - All Green(my answer for bit)

D, G = map(int, input().split())
p, c = [], []
ans = float('inf')
for _ in range(D):
    a, b = map(int, input().split())
    p.append(a)
    c.append(b)

for bit in range(1 << D):  # bitで完答した問題を列挙
    score = 0
    cnt = 0
    comp = set(range(D))
    for i in range(D):  # 完答した問題のscoreを全て加算
        if bit & (1 << i):
            score += p[i] * 100 * (i + 1) + c[i]
            cnt += p[i]
            comp.discard(i)
    if score < G:  # scoreがGに満たなければ中途半端に解答する
        incomp = max(comp)
        # -が2つあるのは//で切り上げで計算するため．-がないと切り下げ
        # https://python.ms/division/#３つのやり方
        incomp_num = min(p[incomp],
                         -(-(G - score) // (100 * (incomp + 1))))  
        score += (incomp + 1) * incomp_num * 100
        cnt += incomp_num
    if score >= G:  # scoreが目標点G以上なら計算回数cntを記録
        ans = min(ans, cnt)
print(ans)

Submission status: Accepted

Solution code:
def solve(bit):
    ret = 0
    score = 0
    done = set()
    for i in range(D):
        if bit[i]:
            done.add(i)
            ret += L[i][0]
            score += ((i + 1) * 100) * L[i][0] + L[i][1]
    j = D - 1
    cnt = 0
    while score < G:
        while j in done:
            j -= 1
        ret += 1
        cnt += 1
        score += (j + 1) * 100
        if cnt == L[j][0]:
            done.add(j)
            score += L[j][1]
            cnt = 0
    return ret

D, G = map(int, input().split())
L = [list(map(int, input().split())) for _ in range(D)]
ans = float('inf')
for i in range(1 << D):
    bit = [0] * D
    for j in range(D):
        if i >> j & 1:
            bit[j] = 1
    ans = min(ans, solve(bit))
print(ans)

Submission status: Accepted

Solution code:
# ABC 104 C - All Green(my answer for bit)

D, G = map(int, input().split())
p, c = [], []
ans = float('inf')
for _ in range(D):
    a, b = map(int, input().split())
    p.append(a)
    c.append(b)

for bit in range(1 << D):  # bitで完答した問題を列挙
    score = 0
    cnt = 0
    comp = set(range(D))
    for i in range(D):  # 完答した問題のscoreを全て加算
        if bit & (1 << i):
            score += p[i] * 100 * (i + 1) + c[i]
            cnt += p[i]
            comp.discard(i)
    if score < G:  # scoreがGに満たなければ中途半端に解答する
        incomp = max(comp)
        incomp_num = min(p[incomp],
                         -(-(G - score) // (100 * (incomp + 1))))
        score += (incomp + 1) * incomp_num * 100
        cnt += incomp_num
    if score >= G:  # scoreが目標点G以上なら計算回数cntを記録
        ans = min(ans, cnt)
print(ans)

Submission status: Accepted

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

D,G = map(int,readline().split())
P = [0] * D
C = [0] * D
for i in range(D):
  P[i],C[i] = map(int,readline().split())

# 全部解く問題をどれにするか、全探索

ans = 10 ** 9
for i in range(2 ** D):
#  print("bin(i)",bin(i)[2:].zfill(2))
  score = 0
  solve = 0
  for j in range(D):
    if (i >> j) & 1:
      score += P[j] * (j + 1) * 100 + C[j]
      solve += P[j]
#  print("score",score,"solve",solve)
  rest = G - score
#  print("score",score,"rest",rest)

  # 残りの点数を、高いほうから埋めていく
  if rest <= 0:
    if ans > solve:
      ans = solve
    continue
  for j in range(D - 1,-1,-1):
    if (i >> j) & 1 == 0:
      if (P[j] - 1) * (j + 1) * 100 == rest:
        solve += (P[j] - 1)
        rest = 0
        break
      if (P[j] - 1) * (j + 1) * 100 < rest:
        rest -= (P[j] - 1) * (j + 1) * 100
        solve += (P[j] - 1)
      else:
        p = (j + 1) * 100
#        print("p",p,"(rest + p - 1) // p",(rest + p - 1) // p)
        solve += (rest + p - 1) // p
        rest = 0
        break
  if rest > 0:
    continue
  if solve < ans:
    ans = solve
#  print("ans",ans)
    
print(ans)

Submission status: Accepted

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


def dfs(i, sum, count, nokori):
    global ans
    if i == d:#全ての最後の問題セットにたどり着いたら,　全ての葉を確認
        if sum < g:
            use = max(nokori)#選んでいない種類で最大のスコアの問題を選ぶ
            #-(-(g-sum)//(use*100)) <- (g-sum)//(use*100)
            n = min(pc[use-1][0], -(-(g-sum)//(use*100)))#その難易度の問題の数 または 残りの必要スコア/その難易度の問題1問の点数　の最小値をとる->余計に問題を解かない＆問題数を超えてとかない
            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})#全て解いた番号をセットから抜いて、合計&countを更新

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())
probs = []
for i in range(d):
    p,c = map(int,input().split())
    probs.append([p,c])

probs.reverse()

#compするかどうかは2^10全通りに対して残ったやつからコンプしないように高い順にとってくのが最適
def tobin(x, n):
    return format(x, 'b').zfill(n)

ans = 1e9
for i in range(2**d):
    s = tobin(i,d)
    comp = [c=="1" for c in s]
    tmp = 0
    cos = 0
    for j in range(d):
        if comp[j]:
            tmp += probs[j][0]*(d-j)*100+probs[j][1]
            cos += probs[j][0]

    for j in range(d):
        if comp[j]:
            continue
        else:
            if tmp < g:
                mc = (probs[j][0]-1)*(d-j)*100

                if mc + tmp >= g:
                    rest = g-tmp
                    cos += (g-tmp)//((d-j)*100)
                    if (g-tmp)%((d-j)*100) == 0:
                        break
                    else:
                        cos += 1
                        break
                else:
                    cos += probs[j][0]
                    tmp += mc
            else:
                break
    if ans > cos:
        ans = cos

print(ans)

Submission status: Accepted

Solution code:
import sys, re
from math import ceil, floor, sqrt, pi, factorial, gcd
from copy import deepcopy
from collections import Counter, deque
from heapq import heapify, heappop, heappush
from itertools import accumulate, product, combinations, combinations_with_replacement
from bisect import bisect, bisect_left
from functools import reduce
from decimal import Decimal, getcontext
# input = sys.stdin.readline 
def i_input(): return int(input())
def i_map(): return map(int, input().split())
def i_list(): return list(i_map())
def i_row(N): return [i_input() for _ in range(N)]
def i_row_list(N): return [i_list() for _ in range(N)]
def s_input(): return input()
def s_map(): return input().split()
def s_list(): return list(s_map())
def s_row(N): return [s_input for _ in range(N)]
def s_row_list(N): return [s_list() for _ in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
def lcm(a, b): return a * b // gcd(a, b)
sys.setrecursionlimit(10 ** 6)
INF = float('inf')
MOD = 10 ** 9 + 7
num_list = []


def main():
    d, g = i_map()
    num_list = i_row_list(d)

    min_count = INF
    for bit in list(product([0,1], repeat=d)):
        tmp_score = 0
        tmp_count = 0
        max_i = -1
        for i in range(d):
            if bit[i] == 0:
                max_i = max(max_i, i)
                continue
            tmp_score += num_list[i][0] * 100 * (i+1) + num_list[i][1]
            tmp_count += num_list[i][0]
        if tmp_score < g:
            for _ in range(num_list[max_i][0]):
                tmp_score += 100 * (max_i+1)
                tmp_count += 1
                if tmp_score >= g:
                    break
        if tmp_score >= g:
            min_count = min(min_count, tmp_count)
        
    print(min_count)

if __name__ == '__main__':
    main()

Submission status: Accepted

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

sc=0
l=[]
for i in range(2**d):
  bag=[0]*d
  #print("pattern {}: ".format(i), end="")
  for j in range(d):
    if ((i>>j) & 1):
      bag[j]=100*(j+1)
  else:
    #print(bag)
    sc=0
    inc=0
    #完全に解く問題のスコアのみ加算
    for ii in range(d):
      #0はスキップ
      if bag[ii] == 0:
        continue
      sc+=bag[ii]*pc[ii][0]+pc[ii][1]
      inc+=pc[ii][0]
      if sc>=g:
        l.append(inc)
        break
      
    for index,ii in enumerate(reversed(bag)):
      #さっき加算したのでスキップ
      if ii != 0:
        continue
      #中途半端に解く問題のスコアを加算
      else:
        for _ in range(1,pc[index][0]):
          sc+=100*(d-index)
          inc+=1
          if sc>=g:
            l.append(inc)
            #中途半端は一度のみなので加算したらループを抜ける
        break

print(min(l))

Submission status: Accepted

Solution code:
d,g = map(int,input().split())
pc = []
for i in range(d):
    p,c = map(int,input().split())
    pc.append((p,c))
minimum = 2000
for i in range(2**d):
    count = 0
    remain = g
    for j in range(d):
        if i >> j & 1:
            count += pc[j][0]
            remain -= (j+1)*100*pc[j][0]
            remain -= pc[j][1]
    highest = d*100
    while remain > 0 and highest >= 100:
        if not i >> (highest//100-1) & 1:
            if highest * pc[highest//100-1][0] >= remain:
                count += -(-remain//highest)
                remain -= -(-remain//highest)*highest
            else:
                count += pc[highest//100-1][0]
                remain -= pc[highest//100-1][0]*highest
        highest -= 100
    if remain <= 0:
        minimum = min(minimum,count)
print(minimum)

Submission status: Accepted

Solution code:
def IL(): return list(map(int, input().split()))
d, g = IL()
p = [0] * d
c = [0] * d
cpl = [False] * d
ans = 10000
for i in range(d):
    p[i], c[i] = IL()
for i in range(2 ** d):
    cnt = 0
    score = 0
    cpl = [False] * d
    for j in range(d):
        if i >> j & 1:
            cpl[j] = True
    for j in range(d): #コンプ
        if cpl[j]:
            cnt += p[j]
            score += 100 * (j + 1) * p[j] + c[j]
    if score >= g:
        if cnt < ans:
            ans = cnt
        continue
    for j in reversed(range(d)): #非コンプ
        if not cpl[j]:
            for k in range(p[j] - 1):
                cnt += 1
                score += 100 * (j + 1)
                if score >= g:
                    if cnt < ans:
                        ans = cnt
                    break
            else:
                continue
            break
print(ans)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
D, G = map(int, input().split())
p = []
c = []
for i in range(D):
    p_i,c_i = map(int, input().split())
    p.append(p_i)
    c.append(c_i)

min_problem = sum(p)
# コンプリートする・しないでbinary
for bit in range(2**D):
    base_score = 0
    base_problem = 0
    non_completed_index = []
    for shift in range(D):
        if (bit>>shift)&1:
            base_score += c[shift]
            base_score += 100*(shift+1)*p[shift]
            base_problem += p[shift]
        else:
            non_completed_index.append(shift)

    if base_score >= G:
        if base_problem < min_problem:
            min_problem = base_problem
    else:
        add_score = 0
        add_problem = 0
        # 上から順に埋めていく
        non_completed_index = non_completed_index[::-1]
        for idx in non_completed_index:
            max_add_score_idx = 100*(idx+1)*(p[idx]-1)
            if base_score+add_score+max_add_score_idx >= G:
                # 埋め終了
                if (G-base_score-add_score) % (100*(idx+1)) == 0:
                    idx_problem = int((G-base_score-add_score)/(100*(idx+1)))
                else:
                    idx_problem = int((G-base_score-add_score)/(100*(idx+1)))+1
                if idx_problem+add_problem+base_problem < min_problem:
                    min_problem = idx_problem+add_problem+base_problem
                break
            else:
                add_score += max_add_score_idx
                add_problem += p[idx]-1


print(min_problem)

Submission status: Accepted

Solution code:
D, G = map(int, input().split())
P = [tuple(map(int, input().split())) for _ in range(D)]
ans = float('inf')
for bit in range(1 << D):
    score = 0
    count = 0
    rest = -1
    for i, pc in enumerate(P):
        p, c = pc
        if bit >> i & 1:
            score += 100 * (i + 1) * p + c
            count += p
        else:
            rest = i
    if score < G:
        s1 = 100 * (rest + 1)
        need = (G - score + s1 - 1) // s1
        if need >= P[rest][0]:
            continue
        count += need
    ans = min(ans, count)
print(ans)

Submission status: Accepted

Solution code:
n, m = map(int,input().split())

a = []
for i in range(n):
    a.append(list(map(int,input().split())))

ans = 1000000000000000
for i in range(2 ** n):
    check = 0
    ac = 0
    tmp = 0
    for j in range(n):
        if (i >> j) & 1:
            check += a[j][0] * 100 * (j + 1) + a[j][1]
            tmp += a[j][0]
        
        if check >= m:
            ans = min(ans, tmp)

        else:
            for k in reversed(range(n)):
                if not (i >> k) & 1:
                    ac = -(-(m - check) // ((k + 1) * 100))
                    if ac < a[k][0]:
                        ans = min(ans, ac + tmp)

print(ans)

Submission status: Accepted

Solution code:
d, g = map(int, input().split())
p = [0 for _ in range(d)]
c = [0 for _ in range(d)]
for i in range(d):
    p[i], c[i] = map(int, input().split())
ans = -1
for pat in range(2**d):
    score = 0
    now = 0
    l = []
    for i in range(d):
        if pat & (2 ** i):
            l.append(i)
            score += 100*(i+1)*p[i]+c[i]
            now += p[i]
    if score < g:
        maxidx = None
        for i in range(d-1, -1, -1):
            if not i in l:
                maxidx = i
                break
        if maxidx == None:
            continue
        if score+100*(maxidx+1)*(p[maxidx]-1) < g:
            continue
        for i in range(p[maxidx]-1):
            score += 100*(maxidx+1)
            now += 1
            if score >= g:
                break
    if ans == -1 or ans > now:
        ans = now
print(ans)

Submission status: Accepted

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

res = 1 << 29
for bit in range(1 << D):
    score, num = 0, 0
    for i in range(D):
        if bit >> i & 1: # bit & (i << i)
            score += c[i] + p[i] * 100 * (i + 1)
            num += p[i]
    if score >= G:
        res = min(res, num)
    else:
        for j in range(D - 1, -1, -1):
            if bit >> j & 1: # bit & (i << i)
                continue
            for k in range(p[j]):
                if score >= G:
                    break
                score += 100 * (j + 1)
                num += 1
        res = min(res, num)
print(res)

Submission status: Accepted

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

from itertools import product
res = 1 << 29
for v in product([0, 1], repeat=D):
    score, num = 0, 0
    for i in range(D):
        if v[i] == 1:
            score += c[i] + p[i] * 100 * (i + 1)
            num += p[i]
    if score >= G:
        res = min(res, num)
    else:
        for j in range(D - 1, -1, -1):
            if v[j] == 1:
                continue
            for k in range(p[j]):
                if score >= G:
                    break
                score += 100 * (j + 1)
                num += 1
        res = min(res, num)
print(res)

Submission status: Accepted

Solution code:
import sys
import math
from collections import deque

sys.setrecursionlimit(1000000)
MOD = 10 ** 9 + 7
input = lambda: sys.stdin.readline().strip()
NI = lambda: int(input())
NMI = lambda: map(int, input().split())
NLI = lambda: list(NMI())
SI = lambda: input()


def main():
	D, G = NMI()
	problems = [NLI() for _ in range(D)]
	n = D
	ans = 10**10
	for case in range(2 ** n):
		res = 0
		point = 0
		maxbit = 0
		for i in range(n):
			if (case >> i) & 1:
				res += problems[i][0]
				point += problems[i][1] + problems[i][0] * (i+1) * 100
			else:
				maxbit = max(maxbit, i)
				pass

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

		for i in range(problems[maxbit][0]):
			point += (maxbit+1) * 100
			res += 1
			if point >= G:
				ans = min(ans, res)
				break

	print(ans)


if __name__ == "__main__":
	main()