Problem:


Score : 300 points

Problem Statement

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

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

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

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

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

Constraints

1 ≤ D ≤ 10

1 ≤ p_i ≤ 100

100 ≤ c_i ≤ 10^6

100 ≤ G

All values in input are integers.

c_i and G are all multiples of 100.

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

Input

Input is given from Standard Input in the following format:

D G
p_1 c_1
:
p_D c_D

Output

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

Sample Input 1

2 700
3 500
5 800

Sample Output 1

3

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

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

Sample Input 2

2 2000
3 500
5 800

Sample Output 2

7

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

Sample Input 3

2 400
3 500
5 800

Sample Output 3

2

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

Sample Input 4

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

Sample Output 4

66

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



Sample input:
2 700
3 500
5 800


Sample output:
3

Submission status: Accepted

Solution code:
from collections import defaultdict

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

scores = []

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


result = 10 ** 9
#print(scores)
n = 2 ** d
for i in range(n):
    #print(bin(i))
    cnt = 0
    point = 0
    memo = -1
    for j in range(d):  # このループが一番のポイント
        if ((i >> j) & 1):  # 順に右にシフトさせ最下位bitのチェックを行う
            point += scores[j][0] * scores[j][1] + scores[j][2]
            cnt += scores[j][1]
        else:
            memo = j

    #print(memo)
    if point >= g:
        result = min(result, cnt)
    else:
        if memo > -1:
            for k in range(scores[memo][1] - 1):
                cnt += 1
                point += scores[memo][0]
                if point >= g:
                    result = min(result, cnt)
                    break

print(result)

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 = 1<<60
for bit in range(1<<D):
  s = 0
  num = 0
  rest_max = -1
  for i in range(D):
    if bit & (1<<i):
      s += 100*(i+1)*P[i]+C[i]
      num += P[i]
    else:
      rest_max = i
  if s < G:
    rest_max_point = 100*(rest_max+1)
    need = -(-(G-s)//rest_max_point)
    if need < P[rest_max]:
      num += need
    else:
      continue
  ans = min(ans, num)
  
print(ans)

Submission status: Accepted

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

minnum = 1e9
for i in range(0, 2**D):
    total = 0
    num = 0
    serach0 = [0] * D
    for j in range(D):
        if (i >> j) & 1:
            total += P[j]*(j+1) + C[j]
            num += P[j]
            serach0[j] = 1

    if total >= G:
        minnum = min(minnum, num)
        continue
    
    while 0 in serach0:
        idx = serach0.index(0)
        total_ = total
        num_ = num
        for _ in range(P[idx]):
            total_ += idx+1
            num_ += 1
            if total_ >= G:
                minnum = min(minnum, num_)
                break
        serach0[idx] = 1
print(minnum)

Submission status: Accepted

Solution code:
import itertools

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

ans = 10**5

for v in itertools.product([0,1],repeat=D):
    p = 0
    t = 0
    for i in range(D):
        if v[i] == 1:
            p += (i+1)*100*pc[i][0] + pc[i][1]
            t += pc[i][0]
    w = G-p
    if w > 0:
        for i in range(D):
            if v[i] == 0 and w <= (i+1)*100*(pc[i][0]-1):
                a = (i+1)*100
                tt = t+(w+a-1)//a
                ans = min(ans,tt)
    else:
        ans = min(ans,t)
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 = [], []
for p, c in PC:
  P.append(p)
  C.append(c)
  
answer = []
for i in range(2 ** D):
  tmp = 0
  cnt = 0
  for j in range(D):
    if (i >> j) & 1:
      tmp += P[j] * (j + 1) * 100 + C[j]
      cnt += P[j]
  if tmp >= G:
    answer.append(cnt)
  else:
    for j in range(D - 1, -1, -1):
      if (i >> j) & 1 == 0:
        if -(-(G - tmp) // ((j + 1) * 100)) <= P[j] - 1:
          cnt += -(-(G - tmp) // ((j + 1) * 100))
          answer.append(cnt)
        else:
          tmp += (P[j] - 1) * (j + 1) * 100
          cnt += (P[j] - 1)
          
print(min(answer))

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)
v=sum(P)

for i in range(1<<d):
	t=0
	c=0
	L=[i for i in range(d)]
	for j in range(d):
		if i&(2**j):
			L.remove(j)
			t+=(j+1)*100*P[j]+C[j]
			c+=P[j]
	if t>=g:
		v=min(v,c)
	else:
		if L:
			s=max(L)
			for k in range(P[s]-1):
				t+=100*(s+1)
				c+=1
				if g<=t:
					v=min(v,c)
					break
print(v)

Submission status: Accepted

Solution code:
d, g = map(int, input().split())
g //= 100
PC = [ list(map(int, input().split())) for _ in range(d) ]
P, C = zip(*PC)
C = [i//100 for i in C]
ans = float("inf")
for i in range(2**d):
  count = 0
  end = 0
  l = []
  for j in range(d):
    if i>>j & 1:
      count += P[j]
      end += (j+1)*P[j] + C[j]
    else:
      l += [j+1]*(P[j]-1)
  l.sort()
  while end < g and l:
    end += l.pop()
    count += 1
  if end < g:
    continue
  ans = min(ans, count)
print(ans)

Submission status: Accepted

Solution code:
import itertools

d,g = map(int,input().split())
    
arr = []
    
for i in range(d):
    arr.append(list(map(int,input().split())))
    
ans = 10**10

for i in itertools.product((0,1),repeat=d):
    score=0
    num=0
    index=0
    
    for j in range(d):
        if i[j]==1:
            score += (j+1)*100*arr[j][0] + arr[j][1]
            num +=arr[j][0]
        else:
            index = max(j,index)
    
    if g - score <=0:
        ans = min(ans,num)
    
    elif g - score <= (index+1) *100*(arr[index][0]-1):
        num+= -(-(g-score)//(100*(index+1)))
        ans =min(ans,num)

print(ans)

Submission status: Accepted

Solution code:
"""
bit全探索
"""

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 = 100000000

for i in range(2 ** D):
    a = 0
    b = 0
    for j in range(D):
        if i >> j & 1:
            a += 100 * P[j] * (j + 1) + C[j]
            b += P[j]
    for k in range(D-1, -1, -1):
        if i >> k & 1:
            continue
        if a >= G:
            break
        for l in range(P[k] - 1):
            a += 100 * (k + 1)
            b += 1
            if a >= G:
                break
    if a >= G:
        ans = min(ans, b)
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)
ans = 100000000

for i in range(2 ** D):
    a = 0
    b = 0
    for j in range(D):
        if i >> j & 1:
            a += 100 * P[j] * (j + 1) + C[j]
            b += P[j]
    for k in range(D-1, -1, -1):
        if i >> k & 1:
            continue
        if a >= G:
            break
        for l in range(P[k]):
            a += 100 * (k + 1)
            b += 1
            if a >= G:
                break
    ans = min(ans, b)
print(ans)

Submission status: Accepted

Solution code:
d,g = map(int,input().split())
    
arr = []
    
for i in range(d):
    arr.append(list(map(int,input().split())))
    
from itertools import product
from math import ceil
    
ans = 1e09
#各問題を選択するしないを01表記
for c in product([0,1],repeat=d):
    #print(c)
    #スコア
    score = 0
    #解く問題数
    num = 0
    
    ind = 0
    #まず01表記を全て
    for i in range(d):
        #もし01表記で1の場合，完答した場合の点数，問題数を加算
        if c[i] == 1:
            score += arr[i][0]*100*(i+1) + arr[i][1]
            num += arr[i][0]
        #0だった場合，
        else:
            ind = max(i,ind)
    #目標よりも点数が大きかった場合，小さい方を答えにする
    if g - score <= 0:
        ans = min(ans,num)
        #print(0,ans,num,score,ind)
    #もし目標が，点数とind番目の問題を完答してない場合との和より小さい時
    elif g - score <= (arr[ind][0]-1)*100*(ind+1):
        num += ceil((g-score)/(100*(ind+1)))
        ans = min(ans,num)
        #print(1,ans,num,score,ind)
    else:
        pass
#print(2,num,score,ind)
print(ans)

Submission status: Accepted

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

ans = 10000
for f in range(2**D):
    score_tot = 0
    q = 0
    for d in range(D):
        if f>>d&1:
            score_tot += C[d]+P[d]*(d+1)*100
            q += P[d]

    for d in range(D-1, -1, -1):
        if G <= score_tot: break
        if f>>d&1: continue
        score_d = (d+1)*100
        k = (G-score_tot-1)//score_d+1
        score_tot += min(k, P[d]) * score_d
        q += min(k, P[d])

    ans = min(ans, q)

print(ans)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
from itertools import combinations
inf = 10**9
d,g = map(int, input().split())
pc = [list(map(int, input().split())) for _ in range(d)]

def score(comp):
    res = 0
    s = 0
    for i in comp:
        s += pc[i][1]
        s += pc[i][0]*100*(i+1)
        res += pc[i][0]

    if s>=g:
        return res

    for i in range(d-1,-1,-1):
        if i in comp:
            continue

        c = 0
        while c<pc[i][0]-1 and s<g:
            c += 1
            s += 100*(i+1)
        res += c

        if s>=g:
            return res
    return inf

res = inf
for r in range(d+1):
    for c in combinations(range(d),r):
        s = score(c)
        res = min(res, s)

print(res)

Submission status: Accepted

Solution code:
D, G = map(int, input().split())
Q = list()
s = 0
for d in range(D):
    Q.append([d+1]+[int(x) for x in input().split()])
    s += Q[-1][1]
dp = [-float("inf")]*(s+1)
dp[0] = 0
for i, p, c in Q:
    for j in range(s, -1, -1):
        for k in range(1, p+1):
            if k == p:
                cc = 100*i*k+c
            else:
                cc = 100*i*k
            if k <= j:
                dp[j] = max(dp[j], dp[j-k]+cc)
for i in range(s+1):
    if dp[i] >= G:
        print(i)
        exit()

Submission status: Accepted

Solution code:

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

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

ans = float("inf")

for i in range(2 ** D):
  score = 0
  index = []
  attempt = 0

  for j in range(D):
    if ((i >> j) & 1):
      p, c = map(int, P[j])
      score += (c + p * (100 * (j+1) ))
      attempt += p
      index.append(j)

  if score >= G: # コンプリートボーナスのみでスコアを超えている場合
    ans = min(ans, attempt)
    continue

  for i in range(D)[::-1]: # 個別に計算して足していく
    if score >= G: # スコアを達成した場合は終了
      break

    if i in index: # コンプリートしてたりするやつはスキップ
      continue

    p, c = map(int, P[i])
    for j in range(p):
      score += 100 * (i+1)
      attempt += 1
      if score >= G: # スコアを達成した場合は終了
        ans = min(ans, attempt)
        break
    else:
      index.append(i)

print(ans)

Submission status: Accepted

Solution code:
from itertools import product
D, G = map(int, input().split())
P, C = map(list, zip(*[tuple(map(int, input().split())) for _ in range(D)]))
CP = [100*i*p+c for i, (p, c) in enumerate(zip(P, C), 1)]
ans = 10**9
for prod in product((True, False), repeat=D):
    I = [i for i, p in enumerate(prod) if p]
    A = sum(CP[i] for i in I)
    r = sum(P[i] for i in I)
    if A >= G:
        ans = min(ans, r)
    else:
        j = max(i for i, p in enumerate(prod) if not p)
        if G > A + 100*(j+1)*(P[j]-1):
            continue
        ans = min(ans, r + (G-A-1)//((j+1)*100)+1)
print(ans)

Submission status: Accepted

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


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], count+pc[i][0], nokori-{i+1})


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_pairs = [(i+1, list(map(int, input().split(' ')))) for i in range(D)]

import itertools, math
ans = float('inf')
nums = list(range(D))
for n in range(D+1):
    for num in itertools.combinations(nums, n):

        probs, score = 0, 0
        for i in num:
            j, (p, c) = p_c_pairs[i]
            probs += p
            score += 100 * j * p + c

        if G > score:
            i = max([i for i in nums if i not in num])
            j, (p, c) = p_c_pairs[i]
            m = min(p, int(math.ceil((G - score) / (100 * j))))
            probs += m
            score += 100 * j * m
            if m == p:
                score += c

        if G <= score:
            ans = min(ans, probs)

print(ans)

Submission status: Accepted

Solution code:
def main():
    D, G, *pc = map(int, open(0).read().split())
    p = pc[::2]
    c = pc[1::2]
    # コンプリート
    comp = [c[i] + 100 * (i + 1) * p[i] for i in range(D)]

    def dfs(G, i):
        # G 総合スコア
        # i 問題 1-based indexing
        if i <= 0:
            # 目標の 総合スコア に到達しなかった
            return 1e9 + 7
        score = 0
        num = min(G // (100 * i), p[i - 1])
        if num == p[i - 1]:
            # コンプリートする
            score = comp[i - 1]
        else:
            # コンプリートしない
            score = 100 * i * num
        if score < G:
            # 目標の 総合スコア に到達しない時 さらに問題を解く
            num += dfs(G - score, i - 1)
        # 問題を解いた、解かなかったの最小
        return min(num, dfs(G, i - 1))
    print(dfs(G, D))


main()

Submission status: Accepted

Solution code:
def main():
    D, G, *pc = map(int, open(0).read().split())
    p = pc[::2]
    c = pc[1::2]
    # コンプリート
    comp = [c[i] + 100 * (i + 1) * p[i] for i in range(D)]

    def dfs(G, i):
        # G 総合スコア
        # i 問題 1-based indexing
        if i <= 0:
            # 目標の 総合スコア に到達しなかった
            return 1e9 + 7
        score = 0
        num = min(G // (100 * i), p[i - 1])
        if num == p[i - 1]:
            # コンプリートする
            score = comp[i - 1]
        else:
            # コンプリートしない
            score = 100 * i * num
        if score < G:
            num += dfs(G - score, i - 1)
        return min(num, dfs(G, i - 1))
    print(dfs(G, D))


main()

Submission status: Accepted

Solution code:
def main():
    D, G, *pc = map(int, open(0).read().split())
    p = pc[::2]
    c = pc[1::2]
    # コンプリート
    comp = [c[i] + 100 * (i + 1) * p[i] for i in range(D)]

    def dfs(G, i):
        # G 総合スコア
        # i 問題 1-based indexing
        if i <= 0:
            # 目標の 総合スコア に到達しなかった
            return 1e9 + 7
        score = 0
        num = 0
        if G // (100 * i) < p[i - 1]:
            # コンプリートしない
            num = G // (100 * i)
            score = 100 * i * num
        else:
            # コンプリートする
            num = p[i - 1]
            score = comp[i - 1]
        if score < G:
            num += dfs(G - score, i - 1)
        return min(num, dfs(G, i - 1))
    print(dfs(G, D))


main()

Submission status: Accepted

Solution code:
def main():
    D, G, *pc = map(int, open(0).read().split())
    p = pc[::2]
    c = pc[1::2]
    ans = 1e9 + 7
    # コンプリート
    comp = [c[i] + 100 * (i + 1) * p[i] for i in range(D)]
    # 2 ** D - 1 まで
    for b in range(2 ** D):
        num = 0
        pnt = 0
        # コンプリートしない MAX
        x = None
        # 得点が高い方から
        for i in range(D - 1, -1, -1):
            # i 番目 の フラグ が 立っている
            if b >> i & 1:
                num += p[i]
                # コンプリートする
                pnt += comp[i]
            elif x is None:
                x = i
        # コンプリート オール
        # または 既に 目標の 総合スコア に到達
        if x is None or G <= pnt:
            ans = min(ans, num)
        # コンプリートしない MAX で 目標の 総合スコア に到達
        elif G < (100 * (x + 1)) * p[x] + pnt:
            ans = min(ans, num - (-(G - pnt) // (100 * (x + 1))))
    print(ans)
    return


main()

Submission status: Accepted

Solution code:
def main():
    D, G, *pc = map(int, open(0).read().split())
    p = pc[::2]
    c = pc[1::2]
    ans = 1e9 + 7
    # 2 ** D - 1 まで
    for b in range(2 ** D):
        num = 0
        pnt = 0
        # コンプリートしない MAX
        x = None
        # 得点が高い方から
        for i in range(D - 1, -1, -1):
            # i 番目 の フラグ が 立っている
            if b >> i & 1:
                num += p[i]
                # コンプリートする
                pnt += c[i] + 100 * (i + 1) * p[i]
            elif x is None:
                x = i
        # コンプリート オール
        # または 既に 目標の 総合スコア に到達
        if x is None or G <= pnt:
            ans = min(ans, num)
        # コンプリートしない MAX で 目標の 総合スコア に到達
        elif G < (100 * (x + 1)) * p[x] + pnt:
            ans = min(ans, num - (-(G - pnt) // (100 * (x + 1))))
    print(ans)
    return


main()

Submission status: Accepted

Solution code:
def main():
    D, G, *pc = map(int, open(0).read().split())
    p = pc[::2]
    c = pc[1::2]
    ans = 1e9 + 7
    # 2 ** D - 1 まで
    for b in range(2 ** D):
        num = 0
        pnt = 0
        # コンプリートしない MAX
        x = None
        # 得点が高い方から
        for i in range(D - 1, -1, -1):
            # i 番目 の フラグ が 立っている
            if b >> i & 1:
                num += p[i]
                # コンプリートする
                pnt += c[i] + 100 * (i + 1) * p[i]
            elif x is None:
                x = i
        # コンプリート オール
        # または 既に 目標の 総合スコア に到達
        if x is None or G <= pnt:
            ans = min(ans, num)
        # コンプリートしない MAX で 目標の 総合スコア に到達
        elif -(-(G - pnt) // (100 * (x + 1))) < p[x]:
            ans = min(ans, num - (-(G - pnt) // (100 * (x + 1))))
    print(ans)
    return


main()

Submission status: Accepted

Solution code:
D, G = map(int, input().split())
nums = [list(map(int, input().split())) for i in range(D)]
count = 10000

for i in range(0, 2**(D)):
    binary = "{0:0>{1}b}".format(i, D)
    tmpNum = 0
    tmpCount = 0
    for j in range(D):
        if binary[j] == '1':
            tmpCount += nums[j][0]
            tmpNum += nums[j][0] * (j+1) * 100 + nums[j][1]
        else:
            maxZeroIndex = j

    if tmpNum >= G and count > tmpCount:
        count = tmpCount
    else:
        for j in range(nums[maxZeroIndex][0]):
            tmpNum += (maxZeroIndex+1) * 100
            tmpCount += 1
            if tmpNum >= G and count > tmpCount:
                count = tmpCount

print(count)

Submission status: Accepted

Solution code:
# coding: utf-8
# Your code here!
D,G=map(int,input().split())

def saiki(n,point,ans,last):
    #print(point,ans)
    if n==D:
        if point>=G:
            lis.append(ans)
        else:
            if (G-point)<=(No[last]-1)*100*(last+1):
                lis.append(ans+(-(-(G-point)//(100*(last+1)))))
            else:
                pass#どう転んでも条件を満たさない
    else:
        saiki(n+1,point,ans,n)#足さない場合
        saiki(n+1,point+al[n],ans+No[n],last)#足す場合

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

#print(No,al)

lis=[]
saiki(0,0,0,0)

print(min(lis))

Submission status: Accepted

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

problems = [tuple(map(int, input().split())) for _ in range(D)]
ans = 10**10

for mask in range(1 << D):
    point = 0
    cnt = 0
    for i, (p, c) in enumerate(problems):
        if (mask & (1 << i)) > 0:
            cnt += p
            point += 100 * (i + 1) * p + c

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

    for i, (p, c) in enumerate(problems):
        if (mask & (1 << i)) > 0:
            continue
        ness = -(-(G - point) // (100 * (i + 1)))
        if ness <= p:
            ans = min(ans, cnt + ness)

print(ans)

Submission status: Accepted

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

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

ans = 10 ** 9

#全部解く・解かないが2のD乗通りになる
for i in range(2 ** D):
    score = 0
    time = 0
    maxj = -1
    #全部解く場合
    for j in range(D):
    #jケタ落としていき、jケタめ == 1であれば、つまりj番目の問題セットを全部解いていれば
        if ((i >> j) & 1):
            score += (j + 1) * PC[j][0] * 100 + PC[j][1]
            time += PC[j][0]
        #全てを解かなかった問題セットのうち最も大きいj
        ##全て解かない問題セットは1つでよく、最大の素点のもの=一番大きいjでよい
        else:
            maxj = max(maxj,j)
    #全てを全部解いた場合
    if maxj == -1:
      ans = min(ans, time)
    #jケタめを全て使わずにG以上のスコアとなった場合
    elif score + (maxj + 1) * (PC[maxj][0] - 1) * 100 >= G:
        #必要な最小問題数を小数点切り上げで求める
        ##残りが500点であったとき、300点問題なら2問、200点問題なら3問解けばよい
        time += max(0, math.ceil((G - score) / (maxj + 1) / 100))
        #最小のものを更新していく
        ans = min(ans, time)

print(ans)

Submission status: Accepted

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

L = []

t = 10 ** 9
m = 0

for i in range(1,D + 1):
  p,c = map(int,input().split())
  s = 0
  pc = []
  for j in range(p):
    s += i * 100
    if j == p - 1:
      s += c
      L.append([j + 1,s])
    if s >= G and j + 1 < t:
      t = j + 1
    pc.append([j + 1,s])
  PC.append(pc)

def recur(problems):
  #探索の終了
  if len(problems) == D:
    ans = 10 ** 9
    score = 0
    times = 0
    #全部使用した問題セットの合計点と回答数を記録
    for j in range(D):
      if problems[j] == 1:
        score += L[j][1]
        times += L[j][0]
    #全問全回答の例を除く
    if score >= G:
      ans = min(ans,times)
      return ans
    #残りの数以上となる回答数のうち最小のものが見つかれば更新し
    #全回答の回答数に足す
    else:
      remain = G - score
      if remain <= max([L[i][1] for i in range(D) if problems[i] == 0]):
        for k in range(D):
          if problems[k] == 0:
            for l in range(len(PC[k])):
              if remain <= PC[k][l][1] and ans >= PC[k][l][0]:
                ans = PC[k][l][0]
        ans += times
        return ans
      else:
        return 10 ** 9
  
  else:
    #問題セットを全部使う
    ret1 = recur(problems + [1])
    #使わない
    ret2 = recur(problems + [0])
    
    return min(ret1,ret2)

print(recur([]))

Submission status: Accepted

Solution code:
# ABC104C - All Green
def rec(score: int, idx: int) -> int:
    if idx == 0:  # base case
        return 1 << 30

    point, (num, bonus) = idx * 100, A[idx]
    cnt = min(score // point, num)
    cur_score = cnt * point
    if cnt == num:
        cur_score += bonus

    rest = score - cur_score
    if rest > 0:
        cnt += rec(rest, idx - 1)  # make up for the shortage

    # compare to other cases without A[idx] recursively
    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 math

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

all = set()
for x in range(0, d):
    all.add(x)

pl = list()
for i in range(0, d):
    p, c = map(int, input().split(" "))
    pl.append((i, p, c))

ans = 100000000
for n in range(0, d + 1):
    for select in itertools.combinations(pl, n):
        full_sum = 0
        full_count = 0
        full_list = set()

        for fp, fn, fc in select:
            full_sum += (fp + 1) * 100 * fn + fc
            full_count += fn
            full_list.add(fp)
        
        if full_sum >= g:
            ans = min(ans, full_count)
            # print("full: %s rest: None score: %d ans: %d" % (str(full_list), full_sum, ans))

        elif len(all - full_list) > 0:
            rest = max(all - full_list)
            rest_n, rest_p, rest_c = pl[rest]

            if g - full_sum <= (rest_n + 1) * 100 * (rest_p - 1):
                ans = min(ans, full_count + math.ceil((g - full_sum) / ((rest_n + 1) * 100)))
                # print("full: %s rest: %d score: %d ans: %d" % (str(full_list), rest_n, full_sum + rest_n * (rest_p - 1), ans))
        

print(ans)

Submission status: Accepted

Solution code:

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

if G // 100 <= D:
    print(1)
else:
    N = 0
    for i in range(D):
        pc[i].append((i+1)*100*pc[i][0]+pc[i][1])
        N += pc[i][0]
    dp = [[0, [pc[i][0] for i in range(D)]] for j in range(N)]

    for i in range(N):
        for j in reversed(range(D)):
            if i+1 >= pc[j][0]:
                for k in range(1, pc[j][0]+1):
                    if dp[i - k][1][j] == k:
                        if dp[i][0] < dp[i - k][0] + pc[j][1] + dp[i - k][1][j]*100*(j+1):
                            dp[i][0] = dp[i - k][0] + pc[j][1] + \
                                dp[i - k][1][j]*100*(j+1)
                            dp[i][1] = copy.deepcopy(dp[i-k][1])
                            dp[i][1][j] = 0

            if dp[i-1][1][j] > 0:
                if dp[i][0] < dp[i-1][0] + (j+1)*100:
                    dp[i][0] = dp[i-1][0] + (j+1)*100
                    dp[i][1] = copy.deepcopy(dp[i-1][1])
                    dp[i][1][j] -= 1

        if dp[i][0] >= G:
            print(i+1)
            break

Submission status: Accepted

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

min_count = 1001
for i in range(2 ** d):
    s = 0
    count = 0
    max_flag = 0
    for j in range(d):
        if (i >> j) & 1:
            s += 100 * (d - j) * pc[d - j - 1][0] + pc[d - j - 1][1]
            count += pc[d - j - 1][0]
        elif max_flag == 0:
            max_flag = d - j

        if s >= g:
            min_count = min(min_count, count)
            s = 0
            count = 0
            break

    for _ in range(pc[max_flag - 1][0]):
        s += 100 * max_flag
        count += 1
        if s >= g:
            min_count = min(min_count, count)
            s = 0
            count = 0
            break

print(min_count)

Submission status: Accepted

Solution code:
from math import ceil
dg=list(map(int,input().split()))
pc=[]
ans=0
for i in range(dg[0]):
    pc.append(list(map(int,input().split())))
    ans+=pc[-1][0]
pattern=2**dg[0]
for i in range(2**dg[0]):
    for j in range(dg[0]):
        p=bin(pattern+i)[3:]
        tsum=0
        tans=0
        for k in range(dg[0]):
            if k==j:
                pass
            else:
                if p[k]=="0":
                    tsum+=(1+k)*100*pc[k][0]+pc[k][1]
                    tans+=pc[k][0]
        if tsum<dg[1]:
            dtans=min(pc[j][0]-1,ceil((dg[1]-tsum)/((1+j)*100)))
            tsum+=((1+j)*100)*dtans
            tans+=dtans
        if tans<ans and tsum>=dg[1]:
            ans=tans
print(ans)

Submission status: Accepted

Solution code:
import math
D, G = map(int,input().split())
p = [0] * D
c = [0] * D
for i in range(D):
    p[i], c[i] = map(int, input().split())
ans = 10**10
for i in range(2**D):
    rest = G
    problems = 0
    for j in range(D):
        if i & 2**(D-j-1):
            problems += p[j]
            rest -= p[j] * (j+1) * 100 + c[j]
        if rest <= 0:
            break
    for j in reversed(range(D)):
        if rest <= 0:
            break
        if i & 2**(D-j-1):
            continue
        add_problems = min(p[j] - 1, math.ceil(rest//((j+1)*100)))
        problems += add_problems
        rest  -= add_problems * (j+1) * 100
    if rest <= 0:
        ans = min(ans, problems)
print(ans)

Submission status: Accepted

Solution code:
import math
D, G = map(int,input().split())
p = [0] * D
c = [0] * D
for i in range(D):
    p[i], c[i] = map(int, input().split())
ans = 10**10
for i in range(2**D):
    rest = G
    problems = 0
    for j in range(D):
        if i & 2**(D-j-1):
            problems += p[j]
            rest -= p[j] * (j+1) * 100 + c[j]
    for j in reversed(range(D)):
        if rest <= 0:
            break
        if i & 2**(D-j-1):
            continue
        add_problems = min(p[j] - 1, math.ceil(rest//((j+1)*100)))
        problems += add_problems
        rest  -= add_problems * (j+1) * 100
    if rest <= 0:
        ans = min(ans, problems)
print(ans)

Submission status: Accepted

Solution code:
import math

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

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

ans = float("inf")
for i in range(2 ** D):

  score = 0
  count = 0
  maxj = -1

  for j in range(D):
    # print(i, j, bin(i), bin(j), i >> j, ((i >> j) & 1))
    if ((i >> j) & 1):
      val, p, c = P[j]
      score += c + (val * p)
      count += p
    else:
      maxj = max(maxj, j)

  if maxj == -1:
    if score >= G:
      ans = min(ans, count)
  else:
    val, p, c = P[maxj]
    if score + val * (p - 1) >= G:
      s = max(0, math.ceil((G-score) / val ))
      ans = min(ans, count + s)

print(ans)

Submission status: Accepted

Solution code:
def get_needed_problems(bini_str):
  point = 0
  cnt = 0

  for i in range(D):
    if bini_str[i] == '1':
      cnt += PC[i][0]
      point += PC[i][0]*(i+1)*100 +PC[i][1]
  if point>=G:
    return cnt
  
  for i in range(D-1,-1,-1):
    if bini_str[i] == '0':
      for j in range(1,PC[i][0]):
        cnt += 1
        point += (i+1)*100
        if point>=G:
          return cnt
  return -1 

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):
  bini_str = bin(i)[2:].zfill(D)
  res = get_needed_problems(bini_str)
  if res != -1:
    ans = min(ans,res)
print(ans)