Problem:


Score : 300 points

Problem Statement

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

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

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

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

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

Constraints

1 ≤ D ≤ 10

1 ≤ p_i ≤ 100

100 ≤ c_i ≤ 10^6

100 ≤ G

All values in input are integers.

c_i and G are all multiples of 100.

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

Input

Input is given from Standard Input in the following format:

D G
p_1 c_1
:
p_D c_D

Output

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

Sample Input 1

2 700
3 500
5 800

Sample Output 1

3

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

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

Sample Input 2

2 2000
3 500
5 800

Sample Output 2

7

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

Sample Input 3

2 400
3 500
5 800

Sample Output 3

2

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

Sample Input 4

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

Sample Output 4

66

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



Sample input:
2 700
3 500
5 800


Sample output:
3

Submission status: Accepted

Solution code:
d,g = map(int, input().split())
l = []
for i in range(d):
    l.append(list(map(int,input().split())))
from itertools import *
ans=10**9
for tmp in list(product([True,False], repeat=d)):
    nokori=g
    rest=[]

    solved=0
    for comp in range(d):
        if tmp[comp]:
            nokori -= l[comp][1]
            solved += l[comp][0]
            nokori -= l[comp][0]*100*(comp+1)
        else:
            for i in range(l[comp][0]):
                rest.append((comp+1) * 100)
    if nokori > 0:
        rest.sort()
        rest.reverse()

        for i in range(len(rest)):
            nokori-=rest[i]
            solved+=1
            if nokori <=0:
                break
    if ans > solved:
        ans=solved
print(ans)

Submission status: Accepted

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

def f(i,s):
    if i == 0: return 10**9
    cnt = min(s//(100 * i), p[i][0])
    score = 100*i*cnt
    if (cnt==p[i][0]):
        score += p[i][1]
    
    if (s > score):
        cnt += f(i-1,s-score)
    
    return min(cnt, f(i-1,s))

def main():
    print(f(d,g))
main()

Submission status: Accepted

Solution code:

from itertools import combinations

def read_input():
    d, g = map(int, input().split())

    points = []
    for i in range(d):
        points.append(tuple(map(int, input().split())))

    return d, g, points


def extract(x, lst):
    # xを2進数でlen(lst)桁に変換する
    bin_x = bin(x)[2:]
    bin_x = '0'* (len(lst) - len(bin_x)) + bin_x

    return [l for l, b in zip(lst, bin_x) if b == '1']


def submit():
    d, g, points = read_input()
    points = [(i*100, p, c) for i, (p, c) in enumerate(points, start=1)]

    min_count = float('inf')
    for fp in points:
        # fpを除き、完全に解く問題セットを選ぶ

        rest_points = points.copy()
        rest_points.remove(fp)
        for i in range(2 ** len(rest_points)):
            # コンプする問題を抽出
            comps = extract(i, rest_points)
            solved = 0
            get_points = 0
            for c in comps:
                solved += c[1]
                get_points += c[0] * c[1] + c[2]

            if g > get_points:
                rest = g - get_points
                if rest > fp[0] * fp[1] + fp[2]:
                    # fpだけではgは満たせないので失敗
                    continue
                else:
                    if rest > fp[0] * fp[1]:
                        # ボーナス込みで満たせる
                        solved += fp[1]
                    elif rest % fp[0]:
                        solved += rest // fp[0] + 1
                    else:
                        solved += rest // fp[0]
            
            if min_count > solved:
                min_count = solved

    print(min_count)


if __name__ == "__main__":
    submit()

Submission status: Accepted

Solution code:
def dfs(i, sum, count, nokori):
    global ans
    if i == d:
        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] +
            pc[i][0], 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())

P = {}
C = {}
for i in range(D):
    P[i], C[i] = map(int, input().split())

ans = float('inf')

for j in range(2**D):
    total_tmp = 0
    count = 0
    not_done = []
    for k in range(D):
#         print(bin(j))
        if (j>>k)&1:
            total_tmp += P[k]*100*(k+1)
            total_tmp += C[k]
            count += P[k]
#             print(total_tmp)
        else:
            not_done.append(k)
    ## Gを超えたら、最小のカウント数
    if total_tmp >= G:
        ans = min(ans, count)
    ## Gを超えなかったら、まだカウントしていない最大の問題から順に足していく
    else:
#         print(sorted(not_done, reverse=True))
        for y in sorted(not_done, reverse=True):
            for x in range(P[y]):
                count += 1
                total_tmp += 100*(y+1)
#                 print(count)
                if total_tmp >= G:
#                     print(total_tmp)
                    ans = min(ans, count)
                    break
        
print(ans)

Submission status: Accepted

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

for i in range(d):
  p_i, c_i = input().split()
  p.append(int(p_i))
  c.append(int(c_i))

ans = float("inf")

for bit in range(2 ** d):
  count = 0
  sum = 0
  nokori = set(range(1, d + 1))


  for i in range(d):
    if ((bit >> i) & 1):
      sum += p[i] * (i + 1) * 100 + c[i]
      count += p[i]
      nokori.discard(i + 1)

  if sum < g:
    use = max(nokori)
    n = min(p[use - 1], -(-(g - sum) // (use * 100)))
    count += n
    sum += n * use * 100

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

print(ans)

Submission status: Accepted

Solution code:
import sys

def main():
    input = sys.stdin.readline
    D, G = map(int, input().split())
    P = [tuple(map(int, input().split())) for i in range(D)]

    #x問解いて獲得できるスコアの最大値を求める
    def calc_max_score(x):
        max_score = 0
        for compl in range(1<<D):
            s = 0
            p = x
            solved = [False] * D
            for i in range(D):
                if compl & 1:
                    p -= P[i][0]
                    if p < 0: break
                    s += P[i][0] * (i+1) * 100 + P[i][1]
                    solved[i] = True
                compl >>= 1
            if p < 0: continue
            for i in range(D-1, -1, -1):
                if solved[i] == False:
                    count = min(P[i][0], p)
                    p -= count
                    s += count * (i+1) * 100
                if p <= 0: break
            max_score = max(max_score, s)
        return max_score

    under = 0
    r = 1000 * 10 + 10**7
    while r - under > 1:
        m = (under + r) // 2
        if calc_max_score(m) >= G: r = m
        else: under = m
    print(r)

if __name__ == '__main__':
    main()

Submission status: Accepted

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

for i in range(2 ** d):
    count = 0
    sum = 0
    nokori = set(range(1, d + 1))
    
    for j in range(d):
        if ((i >> j) & 1):
            sum += pc[j][0] * (j + 1) * 100 + pc[j][1]
            count += pc[j][0]
            nokori.discard(j + 1)
            
    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)
print(ans)

Submission status: Accepted

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

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

ans=10**10
for bit in range(2**D):
    score=G
    problems=0
    SET=set([i for i in range(D)])

    for g in range(D):
        if (bit>>g)&1:
            score-=(g+1)*p[g]+c[g]
            problems+=p[g]
            SET.remove(g)
    
    if score<=0:
        ans=min(ans,problems)
    else:
        #SETが空集合になる時は全ての問題を解いた時であり、全ての問題を解けば必ずscoreは負になるので
        #「ValueError: max() arg is an empty sequence」は防げる。
        MAX=max(SET)
        for _ in range(p[MAX]):
            score-=(MAX+1)
            problems+=1
            if score<=0:
                ans=min(ans,problems)    
                break
print(ans)

Submission status: Accepted

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

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

ans=10**10
for bit in range(2**D):
    score=G
    problems=0
    SET=set([i for i in range(D)])

    for g in range(bit):
        if (bit>>g)&1:
            score-=(g+1)*p[g]+c[g]
            problems+=p[g]
            SET.remove(g)
    
    if score<=0:
        ans=min(ans,problems)
    else:
        #SETが空集合になる時は全ての問題を解いた時であり、全ての問題を解けば必ずscoreは負になるので
        #「ValueError: max() arg is an empty sequence」は防げる。
        MAX=max(SET)
        for _ in range(p[MAX]):
            score-=(MAX+1)
            problems+=1
            if score<=0:
                ans=min(ans,problems)    
                break
print(ans)

Submission status: Accepted

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

pc_dic = {i+1: tuple(map(int, input().split())) for i in range(D)}

complete_solving = {i: pc_dic[i][0]*100*i + pc_dic[i][1] for i in pc_dic}

min_count = 10**9 + 7
for i in range(2**D):
    count = 0
    score = 0
    partially_solve = 0
    for j in range(D):
        if i >> j & 1:
            count += pc_dic[j+1][0]
            score += complete_solving[j+1]
        else:
            partially_solve = j+1
    if score < G:
        if score + complete_solving[partially_solve] - partially_solve*100 < G:
            continue
        count += (G-score+100*partially_solve-1)//(100*partially_solve)
    min_count = min(min_count, count)

print(min_count)

Submission status: Accepted

Solution code:
import numpy as np
D, G=list(map(int, input().split()))
p_c = []
for _ in range(D):
    p_c.append( list(map(int, input().split())) )

min_num = -1
for i in range( 2**D ):
    incomp = -1
    temp_score = 0
    temp_num   = 0
    for j in range(D):
        if i>>j & 1:
            temp_score += 100*(j+1)*p_c[j][0] + p_c[j][1]
            temp_num   += p_c[j][0]

    num=0
    if temp_score < G:
        diff = G-temp_score
        for j in reversed( range(D) ):
            if not i>>j & 1:
                while 100*(j+1)*num<diff:
                    num += 1
                if num < p_c[j][0]:
                    temp_num += num
                else:
                    temp_num = np.inf
                break

    if min_num < 0 or min_num > temp_num:
        min_num = temp_num
print(min_num)

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())
#
s = [0] * (2**d)
n = [0] * (2**d)
m =[]
for j in range(2**d):
    for k in range(d):
        if 1 & (j>>k):
            s[j] += 100*(d - k)*p[d - k - 1] + c[d - k - 1]
            n[j] += p[d - k - 1]
    for l in range(p[(str(format(j,'b').zfill(d))).rfind('0')]):
        if s[j] < g:
            s[j] += 100 * ((str(format(j,'b').zfill(d))).rfind('0') + 1)
            n[j] += 1
        else:
            break
    if s[j] >= g:
        m.append(n[j])


#
ans = min(m)
print(ans)

Submission status: Accepted

Solution code:
D, G, *L = map(int, open(0).read().split())
inf = []
for m in zip(*[iter(L)]*2):
  inf.append(m)

ans = float('inf')
for i in range(2**D):
  m = 0
  cnt = 0
  log = []
  for j in range(D):
    if i%2==0:
      m += 100*(j+1)*inf[j][0]+inf[j][1]
      cnt += inf[j][0]
    else:
      log.append(j)
    i>>=1
  while m<G:
    if log==[]:
      break
    h = log.pop()
    s = 100*(h+1)
    x = (G-m)//s if (G-m)%s==0 else (G-m)//s+1
    c = min(inf[h][0]-1, x)
    m += c*s
    cnt += c
  else:
    ans = min(ans,cnt)
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())

# 再帰的に問題数を求める
def dfs(n, d, g):
    """
    d以下の問題でg点以上取るために必要な最小の問題数を返す

    Parameters
    ----------
    n : int
        dより大きいレベルを解いた数
    d : int
        レベル
    g : int
        点数
    m : int
        dレベルを解く場合の問題数
    q : int
        p問解いた場合に得られる点数

    Returns
    -------
    g点取るための問題数
    """
    # d < 1でgに満たない場合
    if d < 1:
        return float('inf')

    # 解くべき問題数(piまたはg点取るのに必要な最小の問題数)
    m = min(-(-g // (100 * d)), p[d-1])

    # m問解いた時に得られる点数
    q = 100 * m * d + c[d-1] if m == p[d-1] else 100 * m * d

    
    if q >= g:  # g点以上取れる
        return min(n + m, dfs(n, d - 1, g))
    else:       # g点に満たない
        return min(dfs(n + m, d - 1, g - q), dfs(n, d - 1, g))

print(dfs(0, D, G))

Submission status: Accepted

Solution code:
# 入力
D, G = map(int, input().split())
ps = [0] * D
cs = [0] * D

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

# 再帰的に問題数を求める
def dfs(n, d, g):
    """
    d以下の問題でg点以上取るために必要な最小の問題数を返す

    Parameters
    ----------
    n : int
        dより大きいレベルを解いた数
    d : int
        レベル
    g : int
        点数
    m : int
        dレベルを解く場合の問題数
    p : int
        p問解いた場合に得られる点数

    Returns
    -------
    g点取るための問題数
    """
    # d < 1でgに満たない場合
    if d < 1:
        return float('inf')

    # 解くべき問題数(piまたはg点取るのに必要な最小の問題数)
    m = min(-(-g // (100 * d)), ps[d-1])

    # m問解いた時に得られる点数
    p = 100 * m * d + cs[d-1] if m == ps[d-1] else 100 * m * d

    
    if p >= g:  # g点以上取れる
        return min(n+m, dfs(n, d-1, g))
    else:       #g点に満たない
        return min(dfs(n + m, d - 1, g - p), dfs(n, d -1, g))

print(dfs(0, D, G))

Submission status: Accepted

Solution code:
# 入力
D, G = map(int, input().split())
ps = [0] * D
cs = [0] * D

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

ans = 0

def dfs(n, d, g):
    """
    d以下の問題でg点以上取るために必要な最小の問題数を返す

    Parameters
    ----------
    n : int
        dより大きいレベルを解いた数
    d : int
        レベル
    g : int
        点数

    Returns
    -------
    g点取るための問題数
    """
    if d < 1:
        return float('inf')
    m = min(-(-g // (100 * d)), ps[d-1])
    p = 100 * m * d + cs[d-1] if m == ps[d-1] else 100 * m * d
    if p >= g:
        return min(n+m, dfs(n, d-1, g))
    else:
        return min(dfs(n + m, d - 1, g - p), dfs(n, d -1, g))
print(dfs(ans, D, G))

Submission status: Accepted

Solution code:
num = list(map(int,input().split()))
num_list = []
min = 0

for i in range(num[0]):
  temp = list(map(int,input().split()))
  num_list.append(temp)
  min = min + temp[0]
  
for i in range(2**num[0]):
  temp = 0
  count = 0
  max = -1
  for j in range(num[0]):
    if((i >> j)&1):
      temp = temp + 100*(j+1)*num_list[j][0] + num_list[j][1]
      count = count + num_list[j][0]
    elif (not ((i >> j)&1)) and j>max:
      max = j
      
  k = 0
  while temp < num[1]:
    temp = temp + 100*(max+1)
    count = count + 1
    k = k + 1
    if k == num_list[max][0]:
      count = -1
      break
  
  if (count>0) and (count<min):
    min = count
    min_j = i
  
print(min)

Submission status: Accepted

Solution code:
import math

def main3():
    ans = float("inf")
    d, g = map(int, input().split())
    pc = [list(map(int, input().split())) for _ in range(d)]

    for bit in range(1 << d):
        count = 0
        sum = 0
        remain = set(range(d))
        for i in range(d):
            if bit & (1 << i):
                sum += (i + 1) * 100 * pc[i][0] + pc[i][1]
                count += pc[i][0]
                remain -= {i}
        if sum < g:
            q = max(remain)
            n = min(pc[q][0] - 1, math.ceil((g - sum) / (100 * (q + 1))))
            count += n
            sum += 100 * (q + 1) * n
        if sum >= g:
            ans = min(ans, count)
    print(ans)

if __name__ == '__main__':
    main3()

Submission status: Accepted

Solution code:
import math

def dfs(i, sum, count, remain, d, g, pc):
    global ans
    if i == d:
        if sum < g:
            q = max(remain)
            n = min(pc[q][0] - 1, math.ceil((g - sum) / (100 * (q + 1))))
            #n = min(pc[q][0], -(-(g - sum) // ((q + 1) * 100)))
            count += n
            sum += 100 * (q + 1) * n
        if sum >= g:
            ans = min(ans, count)
    else:
        dfs(i + 1, sum, count, remain, d, g, pc)
        dfs(i + 1, sum + (i + 1) * 100 * pc[i][0] + pc[i][1], count + pc[i][0], remain - {i}, d, g, pc)

def main2():
    global ans
    ans = float("inf")
    d, g = map(int, input().split())
    pc = [list(map(int, input().split())) for _ in range(d)]
    dfs(0, 0, 0, set(range(d)), d, g, pc)
    print(ans)

if __name__ == '__main__':
    main2()

Submission status: Accepted

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

ans = 10**18

for i in range(2**D):
    problem = 0
    score = 0
    comp = []
    noncomp = []
    
    for j in range(D):
        if i>>j & 1:
            comp.append(j)
        else:
            noncomp.append(j)
            
    for j in comp:
        problem += P[j]
        score += C[j]+100*(j+1)*P[j]
        
    flag = False
    if score >= G:
        flag = True
        
    if not flag:
        for j in noncomp[::-1]:
            for k in range(P[j]-1):
                problem += 1
                score += 100*(j+1)
                if score >= G:
                    flag = True
                    break
                    
            if flag:
                break
                
    if flag:
        ans = min(ans,problem)

print(ans)

Submission status: Accepted

Solution code:
D, G = map(int, input().split())
G //= 100
A = [[] for i in range(D)]
S = 0
MP = 0
for i in range(D):
  p, c = map(int, input().split())
  L = [(i + 1) * j for j in range(p + 1)]
  L[p] += c//100
  A[i] = L[:]
  S += L[p]
  MP += p
L1 = [[0 for i in range(MP + 1)] for j in range(D)]
for i in range(D):
  for j in range(len(A[i])):
    for k in range(MP+1):
      if j + k <= MP:
        L1[i][j+k] = max(L1[i][j+k], L1[i-1][k] + A[i][j])
L2 = [max(L1[i][j] for i in range(D)) for j in range(MP+1)]
idx = 0
while L2[idx] < G:
  idx += 1
print(idx)

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)

ans = 1e9
for mask in range(2**D):
  score = 0
  num = 0
  rest_max = -1

  for i in range(D):
    if (mask >> i) & 1:
      score += 100 * (i+1) * P[i] + C[i]
      num += P[i]
    else:
      rest_max = i

  if score < G:
    scr1 = 100 * (rest_max + 1)
    need = (G - score + scr1 - 1) // scr1
    if need >= P[rest_max]:
      continue
    num += need

  ans = min(ans, num)

print(ans)

Submission status: Accepted

Solution code:
def main():
    d,g = map(int, input().split())
    P,C = [], []
    for i in range(d):
        p,c = map(int, input().split())
        P.append(p)
        C.append(c)

    ans = 1000
    for i in range(2**d):
        sum = 0
        tmp = 0
        bin_array = list(format(i, 'b').rjust(d,'0'))
        for j in range(d):
            if bin_array[j] == '1':
                sum += 100*(j+1)*P[j]+C[j]
                tmp += P[j]
        for j in range(d):
            if bin_array[d-j-1] == '0':
                for k in range(P[d-j-1]-1):
                    if sum >= g:
                        break
                    sum += 100*(d-j)
                    tmp += 1
        if sum >= g:
            ans = min(ans,tmp)
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from itertools import product

# コンプリートする問題は2**D通りあるが、最大でも1024通りなので全探索する
# 点数が足りない場合は配点が高い問題から解いていく

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

combination = list(product(*[[0, 1]]*d))

ans = float('inf')
for comb in combination:
    # 先ずは、コンプリートする問題の点数を計算する
    score, cnt = 0, 0
    for i, c in enumerate(comb):
        if c == 1:
            score += P[i]*100*(i+1) + C[i]
            cnt += P[i]
            
    if score >= g:  # 目標点数に到達
        ans = min(ans, cnt)
        
    else:  # 目標点数に未到達
        # 解いていない問題のうち、最も点数が高い問題を解く
        NoSolved = [i for i, c in enumerate(comb) if c == 0]
        i = NoSolved[-1]
        for _ in range(P[i]):
            score += (i+1)*100
            cnt += 1
            if score >= g:
                ans = min(ans, cnt)
                break
        else:  # 目標点数に達しなかった
            pass
print(ans)

Submission status: Accepted

Solution code:
d,g= map(int, input().split())
p= [list(map(int, input().split())) for i in range(d)]
ans=10**9+7

for i in range(2**d):
    q=[0]*d
    cnt=0
    count=0
    for j in range(d):
        if (i>>j)&1:
            cnt+=p[j][0]*((j+1)*100)+p[j][1]
            count+=p[j][0]
            q[j]=1
    if cnt>=g:
        ans=min(count,ans)
    else:
        for k in range(d):
            if q[d-1-k]==0:
                v=-((g - cnt) // -((d-k) * 100))
                if v<p[d-1-k][0]:
                    ans=min(count+v,ans)
                    break
                else:
                    break

print(ans)

Submission status: Accepted

Solution code:
S = input().split(" ")
D = int(S[0])
G = int(S[1])

DATA = []
for i in range(D):
    DATA.append([int(s) for s in input().split(" ")])

def calculate(d, _g, data):
    counts = []
    for i in range(2 ** len(data)):
        arr = []
        bonusIndexes = []
        notBonusIndexes = []
        bonusSum = 0
        bonusCounts = 0
        for j in range(len(data)):
            s = i >> j & 1
            arr.insert(0,s)
            _j = len(data)-1 - j
            if s == 1:
                bonusIndexes.append(_j)
                bonusSum = bonusSum + (_j + 1) * 100 * data[_j][0] + data[_j][1]
                bonusCounts = bonusCounts + data[_j][0]
            else:
                notBonusIndexes.append(_j)

        g = _g

        if bonusSum >= g:
            # 该情况下奖金能满足
            counts.append(bonusCounts)
        else:
            g = g - bonusSum
            # 该情况下，奖金不能满足，还要去找奖金拿不到的情况
            # 只需要考虑目前单价最大的情况
            notBonusMaxIndex = max(notBonusIndexes)
            notBonusMaxIndexNum = data[notBonusMaxIndex][0]
            notBonuxMaxIndexPrice = (notBonusMaxIndex + 1) * 100
            for n in range(1, notBonusMaxIndexNum):
                g = g - notBonuxMaxIndexPrice
                bonusCounts = bonusCounts + 1
                if g <= 0:
                    break

            if g <= 0:
                counts.append(bonusCounts)
            else:
                pass
    return counts


result = calculate(D, G, DATA)

print(min(result))

Submission status: Accepted

Solution code:
D, G = map(int, input().split())
p = []
c = []
for _ in range(D):
    p_i, c_i = map(int, input().split())
    p.append(p_i)
    c.append(c_i)
ans = sum(p)
for i in range(pow(2, D) - 1):
    status = bin(i)[2:].zfill(D)
    all_index = [j for j, k in enumerate(status) if k == str(1)]
    not_all_index = [j for j, k in enumerate(status) if k == str(0)]
    score = 0
    nums = 0
    for j in all_index:
        score += 100 * (j + 1) * p[j] + c[j]
        nums += p[j]
    if score < G:
        flag = 0
        for n in not_all_index[::-1]:
            if flag == 1:
                break
            for m in range(1, p[n]):
                score += 100 * (n + 1)
                nums += 1
                if score >= G:
                    flag = 1
                    break
    if score >= G:
        ans = min(nums, ans)
print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
# -*- coding: utf-8 -*-
"""
Created on Wed Feb 19 13:18:23 2020

@author: morihiranaoki
"""

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

def reverse(depth, limit, stack, all_stack):
    if depth == limit + 1:
        return stack, all_stack

    for i in range(2):
        stack.append(i)
        reverse(depth+1, limit, stack, all_stack)[0]
        if len(stack) == limit:
            all_stack.append(list(stack))
            #print(stack)
        del stack[-1]
    return stack, all_stack

Each_Full = [[pc[i][0], pc[i][0]*100*(i+1) + pc[i][1]] for i in range(D)]
_, AllStack = reverse(1, D, [], [])

chosen_Scores = [sum([Each_Full[i][1] for i in range(D) if AllStack[j][i] == 1]) for j in range(len(AllStack))]
chosen_Costs = [sum([Each_Full[i][0] for i in range(D) if AllStack[j][i] == 1]) for j in range(len(AllStack))]

for j in range(len(AllStack)):
    if chosen_Scores[j] >= G:
        continue
    else:
        kari = 0
        for i,factor in enumerate(AllStack[j]):
            if factor == 0:
                kari = i
        for i in range(pc[kari][0]):
            chosen_Scores[j] += (kari+1)*100
            chosen_Costs[j] += 1
            if chosen_Scores[j] >= G:
                break
        else:
            chosen_Costs[j] = 99999

print(min(chosen_Costs))

Submission status: Accepted

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

def f(p,c):
    if p==0:
        return 10**9
    m=min(c//(p*100),PC[p][0])
    s=100*p*m
    if m==PC[p][0]:
        s+=PC[p][1]
    if s<c:
        m+=f(p-1,c-s)
    return min(m,f(p-1,c))

print(f(D,G))

Submission status: Accepted

Solution code:
def main():
    d, g = [int(e) for e in input().split()]
    P, C = zip(*[[int(e) for e in input().split()] for i in range(d)])

    A = []
    for b in [format(i, '0{}b'.format(d)) for i in range(2**d)]:
        count = 0
        score = 0
        for ci, c in enumerate(b):
            if c == '1':
                count += P[-ci - 1]
                score += P[-ci - 1]*(d - ci)*100 + C[-ci - 1]

        if score >= g:
            A.append(count)
            continue

        for i in range(P[-b.index('0') - 1]):
            count += 1
            score += 100*(d - b.index('0'))
            if score >= g:
                A.append(count)
                break

    print(min(A))

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import numpy as np
from functools import reduce
from operator import add,sub,mul,truediv
from fractions import gcd

d,g = map(int,input().split())

p = []
c = []

for _ in range(d):
    a,b = map(int,input().split())
    p.append(a)
    c.append(b)


ans = 1000000000

#print(p)
#print(c)
for bit in range(1 << d):
    score = 0
    num = 0
    x = []
    for i in range(d):
        if (bit >>i)&1 == 0:
            x.append(i+1)
        else:
#            print(i)
#            print(p[i])
            score  = score + p[i]*(i+1)*100+c[i]
            num = num + p[i]
    
#    print(bin(bit))
#    print(x[::-1])

    flag = False
    for j in x[::-1]:
        for _ in range(p[j-1]):
            if score >= g:
                flag = True
                break
            score  = score + j*100
            num = num +1
#            print(score)
#            print(num)
        
#        print(num)
        if flag :
            break
        
#    print(score)
#    print(num)
#    print("num:{}".format(num))
    ans= min(ans,num)
#    print("$$$$$$$$$$$$$$$$$$$$$")

print(ans)

Submission status: Accepted

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

ans = 10**9

for bit in range(1 << D):
  t = 0
  count = 0

  for i in range(D):
    if bit & (1 << i):
        t += P[i][0] * (100*(i+1)) + P[i][1]
        count += P[i][0]

  if t >= G:
    if ans > count:
      ans = count
  else:
    for i in reversed(range(D)):
      if bit & (1 << i):
        continue
      for p in range(P[i][0]):
        t += (i+1)*100
        count += 1

        if t >= G:
          if ans > count:
            ans = count

print(ans)

Submission status: Accepted

Solution code:
from sys import stdin
import math
d,g = map(int,stdin.readline().rstrip().split())
PC = [list(map(int,stdin.readline().rstrip().split())) for _ in range(d)]
mi = 10**10
for i in range(2**d):
    point = 0
    count = 0
    not_all = []
    for j in range(d):
        if (i >> j) & 1:
            point += (j+1)*PC[j][0]*100+PC[j][1]
            count += PC[j][0]
        else:
            not_all.append(j)
    if point < g:
        #すべて取り出す以外の問題番号のうち最大のもの
        saidai = not_all[-1]
        need = math.ceil((g-point)/((saidai+1)*100))
        if need >= PC[saidai][0]:
            continue
        else:
            count += need
    mi = min(mi,count)
print(mi)