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:
import math
D, G = list(map(int, input().split()))
p, c, s = [0]*D, [0]*D, [0]*D

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

slv = [[0], [1]]
for i in range(D-1):
    slv = list(map(lambda x: x+[0], slv)) + list(map(lambda x: x+[1], slv))
memo = []
ans = 10**10 # 比較対象
for si in slv:
    score, cnt = 0, 0
    for i, toku in enumerate(si):
        if toku ==1:
            cnt += p[i]
            score += c[i] + p[i]*100*(i+1)
    if score >= G and cnt <= ans:
        ans = cnt
    memo.append((score, cnt, si))

leqG = []
for m in memo:
    if m[0] < G:
        leqG.append(m)

ans_cand = 10**10
for l in leqG:
    for i, t in enumerate(l[2][::-1]):
        index = len(l[2])-i-1
        if t == 0:
            if l[0]+p[index]*(index+1)*100 >= G:
                ans_tmp = l[1] + min(math.ceil((G-l[0])/((index+1)*100)), p[index])
                ans_cand = min(ans_cand, ans_tmp)
            break
print(min(ans, ans_cand))

Submission status: Accepted

Solution code:
from math import ceil
D,G=map(int,input().split())
P=[]
C=[]
R=[]
for i in range(D):
    p,c=map(int,input().split())
    P.append(p)
    C.append(c)
    R.append((i+1)*100*p+c)
bit=2**D
ans=10**19
for i in range(bit):
    i=bin(i)[2:].zfill(D)
    su=0
    num=0
    k=-1
    for j in range(D):
        k=int(i[j])
        su+=k*R[j]
        num+=k*P[j]
        if k==0:
            t=j
    if G<=su:
        ans=min(ans,num)
        continue
    if k==-1:
        continue
    if  ceil((G-su)/((t+1)*100))<P[t]:
        ans=min(ans,num+ceil((G-su)/((t+1)*100)))
print(ans)

Submission status: Accepted

Solution code:
#coding utf-8
DG = input().split()
D = int(DG[0])
G = int(DG[1])
p = [0 for i in range(D)]
c = [0 for i in range(D)]
for i in range(D):
  pc = input().split()
  p[i] = int(pc[0])
  c[i] = int(pc[1])

x = 2**D
ans = 10000
for i in range(x):
  Gt = 0
  tmp = 0
  y = bin(i)[2:]
  y ="0"*(D-len(y))+y
  for j in range(D):
    if y[j:j+1] =="1":
      Gt +=(j+1)*p[j]*100 +c[j]
      tmp += p[j]
  if G>Gt:
    for j in reversed(range(0,D)):
      if G<=Gt:
        break
      if y[j:j+1] =="0":
        for k in range(p[j]):
          Gt += (j+1)*100
          tmp +=1
          if G <=Gt:
            break
  if tmp<ans and G<=Gt:
    ans = tmp
  
print(ans)

Submission status: Accepted

Solution code:
D, G = map(int, input().split())
PC = [list(map(int, input().split())) for i in range(D)]
PC_new = sorted([(PC[i][0]*100*(i+1) + PC[i][1], PC[i][0]) for i in range(D)],
                key=lambda x: x[1], reverse=True)

ans = 99999999
for i in range(1<<D):
    ct = 0
    score = 0
    for j in range(D):
        if i>>j&1:
            score += PC[j][1]
            score += PC[j][0] * (j+1) * 100
            ct += PC[j][0]
    for j in range(D-1, -1, -1):
        if i>>j&1: continue
        if score >= G: break
        g = (j+1)*100
        got = (G-score+g-1)//g
        score += min(got, PC[j][0]) * g
        ct += min(got, PC[j][0])
    ans = min(ans, ct)
print(ans)

Submission status: Accepted

Solution code:
import math

D,G = map(int,input().split(" "))
G //= 100
p = []
c = []
for x in range(D):
    a,b = map(int,input().split(" "))
    p.append(a)
    c.append(b//100)

h = [sum(p)]

for x in range(2**D):
    o = [(x//(2**y))%2 for y in range(D)]
    if not(0 in o):
        continue
    g = sum([p[y]*(y+1)+c[y] for y in range(D) if o[y]])
    if g >= G:
        h.append(sum([p[y] for y in range(D) if o[y]]))
        continue
    s = max([y for y in range(D) if not(o[y])])
    if g + (s+1)*(p[s]-1) >= G:
        h.append(sum([p[y] for y in range(D) if o[y]])+math.ceil((G-g)/(s+1)))

print(min(h))

Submission status: Accepted

Solution code:
from itertools import product

D, G = map(int, input().split())
probs = []
for _ in range(D):
    p, c = map(int, input().split())
    probs.append((p, c))
ans = 10**9
for choise in product([True, False], repeat=D):
    score = 0
    solved_probs = 0
    max_score_rem_id = 0
    for i, solve in enumerate(choise):
        if solve:
            score += probs[i][0]*(100*(i+1)) + probs[i][1]
            solved_probs += probs[i][0]
        else:
            max_score_rem_id = i
    if score < G:
        remain = G - score
        to_be_solved = (remain - 100) // (100*(max_score_rem_id+1)) + 1
        if to_be_solved < probs[max_score_rem_id][0]:
            solved_probs += to_be_solved
        else:
            continue
    ans = min(ans, solved_probs)
print(ans)

Submission status: Accepted

Solution code:
ans=1000000000
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)
def search(i,sm,cnt,mx):
    global ans,d,g,p,c
    if(i==d):
        if(sm<g):
            for i in range(p[mx]-1):
                sm+=100*(mx+1)
                cnt+=1
                if(sm>=g):
                    ans=min(ans,cnt)
                    break
        else:
            ans=min(ans,cnt)
        return;
    search(i+1,sm,cnt,i)
    search(i+1,sm+(i+1)*100*p[i]+c[i],cnt+p[i],mx)

search(0,0,0,0)
print(ans)

Submission status: Accepted

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

s = 100 * 11
for i in range(2 ** D):
    ans = 0
    num = 0
    zero = 0
    for j in range(D):
        if (i >> j) & 1:
            ans += 100*(j+1)*pc[j][0] + pc[j][1]
            num += pc[j][0]
        else:
            zero = j
    if G > ans:
        cand = ceil((G-ans)/(100 * (zero+1)))
        if cand > pc[zero][0]:
            continue
        else:
            num += cand
    if num < s:
        s = num
print(s)

Submission status: Accepted

Solution code:
import math
d,g = map(int, input().split())
l = []
ans = 10**5

for i in range(d):
    l.append(list(map(int, input().split())))

for i in range(2 ** d):
    count = 0
    score = 0
    remain = -1
    for j in range(d):
        if (i >> j) & 1: # j: コンプリートしない問題
            count += l[j][0]
            score += l[j][1] + l[j][0] * 100 * (j+1)
        else:
            remain = j
    if score >= g:
        ans = min(ans, count)
    else:# remain: コンプリートしない問題でもっとも点数の高い問題
        s1 = 100 * (remain+1)
        need_n = math.ceil((g - score) / s1)
        if need_n >= l[remain][0]:
            continue
        count += need_n
        ans = min(ans, count)

print(ans)

Submission status: Accepted

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

def solve(d, g):
    if d <= 0:
        return 1e5

    n = min(g // (d * 100), P[d])
    score = (d * 100) * n
    if n == P[d]:
        score += C[d]

    if score < g:
        n += solve(d - 1, g - score)

    return min(n, solve(d - 1, g))

print(solve(D, G))

Submission status: Accepted

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

ans = 10**5
for i in range(2**d):
    count = 0
    score = 0
    for j in range(d):
        if i >> j & 1:
            count += pc[j][0]
            score += pc[j][1] + pc[j][0] * (j+1) * 100
    if score >= g:
        ans = min(ans, count)
        continue
    lest_i = d-1 
    while i >> lest_i & 1:
        lest_i -= 1

    lest_num = math.ceil((g - score) / ((lest_i + 1) * 100))
    if lest_num < pc[lest_i][0]:
        count += lest_num
        ans = min(ans, count)
print(ans)

Submission status: Accepted

Solution code:
INF = 10**15
def solve(D, G, p, c):
    best = INF
    for mask in range(2**D):
        num = 0
        score = 0
        for i in range(D):
            if (2**i) & mask:
                num += p[i]
                score += 100*(i+1)*p[i] + c[i]
        for i in range(D-1, -1, -1):
            if ((2**i) & mask) == 0:
                if score < G:
                    diff = G - score
                    q = 100*(i+1)
                    num_solve = min(p[i], (diff+q-1)//q)
                    num += num_solve
                    score += q*num_solve
        if score >= G:
            best = min(best, num)
    return best

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())
print(solve(D, G, p, c))

Submission status: Accepted

Solution code:
d,g=map(int,input().split())
g//=100
l=[]
ans=1000
for i in range(1,d+1):
  p,c=map(int,input().split())
  c//=100
  l+=[[p,c,i*p,i*p+c]]
for i in range(2**d):
  score=0
  a=0
  b=1
  c=0
  if not i:
    b=d
  while i:
    if i%2>0:
      score+=l[a][3]
      c+=l[a][0]
    else:
      b=a+1
    a+=1
    i//=2
  if score>=g:
    ans=min(ans,c)
  elif score+l[b-1][2]>=g:
    ans=min(ans,c+(g-score)//b+((g-score)%b>0))
print(ans)

Submission status: Accepted

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

def dfs(G,i):
    if i <= 0:
        return float('inf')
    n = min(ceil(G/(100*i)),list[i-1][0])
    s = 100*i*n
    if n == list[i-1][0]:
        s += list[i-1][1]
    if G > s:
        n += dfs(G-s,i-1)
    return min(n,dfs(G,i-1))

print(dfs(G,D))

Submission status: Accepted

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


def convert(n):
    Bin = []
    while n != 0:
        a = n % 2
        n //= 2
        Bin.insert(0, a)
    if not Bin:
        Bin.append(0)
    return Bin


Min = 10**8
for i in range(0, 2**D):
    Bin = [str(s) for s in convert(i)]
    Bin = ''.join(Bin).zfill(D)
    idx = 0
    ct = 0
    score = 0
    for j in Bin:
        if j == '1':
            p, c = pc[idx]
            ct += p
            score += 100*(idx+1)*p+c
        if score >= G:
            Min = ct if ct < Min else Min
            break
        idx += 1
    if score < G:
        Bin = Bin[::-1]
        idx = 0
        for j in Bin:
            if j == '0':
                p, c = pc[idx]
                for k in range(p-1):
                    ct += 1
                    score += 100*(D-idx)
                    if score >= G:
                        Min = ct if ct < Min else Min
                        break
                score -= 100*(D-idx)*(p-1)
                ct -= (p-1)
            if score >= G:
                break
            idx += 1

print(Min)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(pow(10, 6))

d, g = map(int, input().split())
pc = []
for _ in range(d):
  pc.append(tuple(map(int, input().split())))

def dfs(i, ll):
  if i != d:
    solve = dfs(i+1, ll + [1])
    nsolve = dfs(i+1, ll + [0])
    return min(solve, nsolve)
  else:
    total = sum((100 * (j + 1) * p + c) * l for j, ((p, c), l) in enumerate(zip(pc, ll)))
    if total >= g:
      return sum(p * l for (p, _), l in zip(pc, ll))
    else:
      rem = g - total
      remc = pow(10, 6)
      for j, ((p, c), l) in reversed(tuple(enumerate(zip(pc, ll)))):
        if l == 0:
          if rem > 100 * (j + 1) * (p - 1):
            break
          else:
            remc = rem // (100 * (j + 1)) + (1 if rem % (100 * (j + 1)) else 0)
            break
      return sum(p * l for (p, _), l in zip(pc, ll)) + remc

print(dfs(0, []))

Submission status: Accepted

Solution code:
def main():
	D, G = map(int, input().split())
	p = [0]*(D+1)
	c = [0]*(D+1)
	ans = 10**9
	for i in range(D):
		p[i], c[i] = map(int, input().split())

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

	print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import math
INF = 10**10

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

def solve(i, partial, cnt, pts):
	if i == len(pc):
		if partial != -1 and pts < G:
			nokori = math.ceil((G - pts) / (100 * (1 + partial)))
			if nokori < pc[partial][0]:
				return cnt + nokori
		elif pts >= G:
			return cnt
		return INF

	ans = []
	ans.append(solve(i + 1, partial, cnt + pc[i][0], pts + 100 * (1 + i) * pc[i][0] + pc[i][1]))
	ans.append(solve(i + 1, partial, cnt, pts))

	if partial == -1:
		ans.append(solve(i + 1, i, cnt, pts))

	return min(ans)

print(solve(0, -1, 0, 0))

Submission status: Accepted

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

ans = 10**10
#bitallsearch
for i in range(2 ** d):
    bit = format(i, "b").zfill(d)
    count = 0
    point = 0
    for j, dot in enumerate(bit):
        if dot == "1":
            count += comp_points[j][0]
            point += comp_points[j][1]
    #add shortage form high point not comp_points
    for b in range(d-1, -1, -1):
        flag = False
        if point >= g:
            ans = min(ans, count)
            break
        if bit[b] == "0":
            flag = True
            for p in range(P[b] - 1):
                count += 1
                point += (b+1) * 100
                if point >= g:
                    ans = min(ans, count)
                    break
        if (point < g) & flag:
            break

print(ans)

Submission status: Accepted

Solution code:
from math import ceil

D, G = [int(t) for t in input().split()]
p = []
c = []
for i in range(D):
    p_, c_ = [int(t) for t in input().split()]
    p.append(p_)
    c.append(c_)

def solve(G, i):
    """100i点以下の問題だけでGを達成する最小問題数"""
    if i <= 0:
        return float('inf')
    #最も配転が高い問題で総合点を超えることができるか確認
    n = min(ceil(G / (100 * i)), p[i - 1])
    s = 100 * i * n
    #もし総合展を超えることができるときの問題数がボーナス点に達するならば足す
    if n == p[i - 1]:
        s += c[i - 1]
    if G > s:
        n += solve(G - s, i - 1)
    return min(n, solve(G, i - 1))

print(solve(G, D))

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 = 10*100
for i in range(2**D):
  rest = G
  cnt = 0
  maxdgt = -1
  for j in range(D):
    if i & 1<<j:
      rest -= P[j]*(j+1)*100+C[j]
      cnt += P[j]
    else:
      maxdgt = j
  if rest <= 0:
    ans = min(ans, cnt)
  elif rest > (P[maxdgt]-1)*(maxdgt+1)*100:
    continue
  else:
    ans = min(ans, cnt+(rest/100-1)//(maxdgt+1)+1)
print(int(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 = 10*100
for i in range(2**D):
  rest = G
  cnt = 0
  maxdgt = -1
  for j in range(D):
    if i>>j & 1:
      rest -= P[j]*(j+1)*100+C[j]
      cnt += P[j]
    else:
      maxdgt = j
  if rest <= 0:
    ans = min(ans, cnt)
  elif rest > (P[maxdgt]-1)*(maxdgt+1)*100:
    continue
  else:
    ans = min(ans, cnt+(rest/100-1)//(maxdgt+1)+1)
print(int(ans))

Submission status: Accepted

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

problems = []
ans = 0

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

for mask in range(1 << d):
    solved_amount = 0
    my_score = 0
    for i in range(d):
        score, occ, bonus = problems[i]
        if mask & (1 << i) > 0:
            solved_amount += occ
            my_score += score * occ + bonus

    for x in range(d-1, -1, -1):
        if my_score >= g:
            break

        if (mask & (1 << x)) > 0:
            continue
        score, occ, bonus = problems[x]
        for _ in range(occ):
            solved_amount += 1
            my_score += score
            if my_score >= g:
                break

    if my_score >= g:
        ans = min(ans, solved_amount)

print(ans)

Submission status: Accepted

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

probs = []
ans = 0

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

for mask in range(1 << D):  # dビット左にずらす、2**dの値となる
    solved = 0   # 問題数？
    my_score = 0
    for i in range(D):
        score, occ, bonus = probs[i]  # scoreは100の倍数の値, occは問題数,
        if mask & (1 << i) > 0:
            solved += occ
            my_score += score * occ + bonus  # 全問解いた場合の点数

    for x in range(D - 1, -1, -1):
        if my_score >= G:
            break
        if (mask & (1 << x)) > 0:
            continue
        score, occ, bounDs = probs[x]
        for _ in range(occ):  # 問題数, 一問ずつ足していく感じ
            solved += 1
            my_score += score
            if my_score >= G:
                break
    if my_score >= G:
        ans = min(ans, solved)

print(ans)

Submission status: Accepted

Solution code:
D, G = map(int,input().split())
p,c = {},{}
for i in range(1,D+1):
  pi,ci = map(int,input().split())
  p[i] = pi
  c[i] = ci
ans = sum(p.values())

for i in range(2**D):
  cmp = {i:False for i in range(1,D+1)}
  score = 0
  ans_tmp = 0
  for j in range(D):
    if (i >> j) & 1:
      cmp[j+1] = True
      score += (j+1)*100*p[j+1]+c[j+1]
      ans_tmp += p[j+1]
  keys = [k for k,v in cmp.items() if v == False]
  if G > score and len(keys) > 0:
    if (G-score) // (max(keys)*100) <= p[max(keys)]:
      ans_tmp += (G-score) // (max(keys)*100)
      if (G-score) % (max(keys)*100) != 0:
        ans_tmp += 1 
    else:
      ans_tmp = sum(p.values())
  ans = min(ans, ans_tmp)
        
print(ans)

Submission status: Accepted

Solution code:
import math
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)

answer = sum(P)
for i in range(2**D):
    point = 0
    x = -1
    now_answer = 0
    for j in range(D):
        if i >> j & 1:
            point += P[j] * (j+1) * 100 + C[j]
            now_answer += P[j]
        else:
            x = j

    if G <= point:
        answer = min(now_answer, answer)
    else:
        n = math.ceil((G - point) / ((x+1) * 100))
        if n < P[x]:
            now_answer += n
            answer = min(now_answer, answer)

print(answer)

Submission status: Accepted

Solution code:
# coding: utf-8
# Your code here!

D,G = map(int,input().split()) # D問題数,G目標点
lst = [list(map(int,input().split()))for i in range(D)]
ans = float('inf')
for i in range(1 << D): # 全探索
    tmp = 0
    count = 0
    bit = ""
    for j in range(len(lst)):
        bit+=str((i >> j)&1)
        if ((i >> j) & 1) == 1:
            tmp = tmp + lst[j][1] + ((j + 1) * 100 * lst[j][0])
            count+=lst[j][0]
    #print("tmp",tmp)
    if tmp < G : #or tmp >= G
        #print(bit)
        for n,k in enumerate(list(bit)):
            if k == "0":
                for p in range(lst[len(bit) - n - 1][0]):
                    t = p * 100 * (n+1)
                    #print("p",p,t,tmp,G,count)
                    if t + tmp >= G:
                        ans = min(ans,p+count)
    
    #if tmp >= G :
    else:
        ans = min(ans,count)
    #print(ans,tmp,count)
print(int(ans))

Submission status: Accepted

Solution code:
def makebit(n, d):
	lst = []
	m = n
	for i in range(0, d):
		lst.append(m%2==1)
		m = m / 2
	return lst
D, G = map(int, raw_input().split())
plist = []
clist = []
for i in range(0, D):
	p, c = map(int, raw_input().split())
	plist.append(p)
	clist.append(c)
n = 1
for i in range(0, D):
	n = n * 2
lst = []
for i in range(0, n):
	lst.append(makebit(i, D))
min = 10000
for i in range(0, n):
	sum = 0
	cnt = 0
	for j in range(0, D):
		if lst[i][j]:
			sum += (j+1)*100*plist[j] + clist[j]
			cnt += plist[j]
	for j in range(0, D):
		if not lst[i][-1-j]:
			if sum + (D-j)*100*(plist[-1-j]-1) < G:
				sum += (D-j)*100*(plist[-1-j]-1)
				cnt += plist[-1-j] - 1
			elif sum < G:
				for k in range(0, plist[-1-j]-1):
					sum += (D-j)*100
					cnt += 1
					if G <= sum: break
		if G <= sum: break
	if cnt < min and G <= sum:
		min = cnt
print min

Submission status: Accepted

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

ans = 1000
for i in range(1 << d):
  score = 0
  num = 0
  remain_max = -1
  for j in range(d):
    if i >> j & 1:
      score += p[j][0] * 100 * (j + 1) + p[j][1]
      num += p[j][0]
    else:
      remain_max = j
  if score < g:
    remain = 100 * (remain_max + 1)
    need = -(-(g - score) // remain)
    if need >= p[remain_max][0]:
      continue
    num += need
  ans = min(ans, num)
print(ans)

Submission status: Accepted

Solution code:
# AC
import math

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

min_n_solved = 1000000000
for p_combi in range(1 << D):
    tmp_score = 0
    n_solved = 0
    selected_p_idxs = []  # Selected indexes of problems
    for digit in range(D):
        if (p_combi >> digit) & 1:
            # p_i: p_c_list[digit][0]
            # c_i: p_c_list[digit][1]
            tmp_score += \
                100 * (digit+1) * p_c_list[digit][0] + p_c_list[digit][1]
            n_solved += p_c_list[digit][0]
            selected_p_idxs.append(digit)
    score_diff = tmp_score - G
    # print('1:', n_solved, 'score_diff:', score_diff)
    if score_diff >= 0:
        # Fine-tuning to reduce "n_solved" problems over solved
        # "selected_p_idxs" were already sorted by probrems
        # from low points to high
        p_idx_lowest = selected_p_idxs[0]
        score_per_p = 100 * (p_idx_lowest + 1)
        # if score_diff - bonus_point > 0
        n_oversolved = None
        score_diff_wo_bonus = score_diff - p_c_list[p_idx_lowest][1]
        if score_diff_wo_bonus > 0:
            n_oversolved = round(score_diff_wo_bonus / score_per_p)
            if n_oversolved < p_c_list[p_idx_lowest][0]:
                n_solved -= n_oversolved
        # print('2:', n_solved)
    else:
        not_selected_p_idxs = \
            [p_idx for p_idx in range(D) if p_idx not in selected_p_idxs]
        not_selected_p_idxs = sorted(not_selected_p_idxs, reverse=True)
        # Select a problem index
        # which have highest point in not_selected_p_idxes
        not_selected_p_idx_highest = not_selected_p_idxs[0]
        num_p = p_c_list[not_selected_p_idx_highest][0]
        addable_score = \
            100 * num_p * (not_selected_p_idx_highest + 1)
        if score_diff + addable_score > 0:
            score_per_p = 100 * (not_selected_p_idx_highest + 1)
            n_undersolved = math.ceil(abs(score_diff) / score_per_p)
            if n_undersolved < num_p:
                n_solved += n_undersolved
            # print('3:', n_solved)
    if n_solved > 0 and score_diff >= 0:
        min_n_solved = min(n_solved, min_n_solved)

print(min_n_solved)

Submission status: Accepted

Solution code:
# Not working correctly
import math


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

min_n_solved = 1000000000
for p_combi in range(1 << D):
    tmp_score = 0
    n_solved = 0
    selected_p_idxs = []  # Selected indexes of problems
    for digit in range(D):
        if (p_combi >> digit) & 1:
            # p_i: p_c_list[digit][0]
            # c_i: p_c_list[digit][1]
            tmp_score += \
                100 * (digit+1) * p_c_list[digit][0] + p_c_list[digit][1]
            n_solved += p_c_list[digit][0]
            selected_p_idxs.append(digit)
    score_diff = tmp_score - G
    # print('1:', n_solved, 'score_diff:', score_diff)
    if score_diff >= 0:
        # Fine-tuning to reduce "n_solved" problems over solved
        # "selected_p_idxs" already sorted by probrems from low points to high
        p_idx_lowest = selected_p_idxs[0]
        score_per_p = 100 * (p_idx_lowest + 1)
        # if score_diff - bonus_point > 0
        n_oversolved = None
        score_diff_wo_bonus = score_diff - p_c_list[p_idx_lowest][1]
        if score_diff_wo_bonus > 0:
            n_oversolved = round(score_diff_wo_bonus / score_per_p)
            if n_oversolved < p_c_list[p_idx_lowest][0]:
                n_solved -= n_oversolved
        # print('2:', n_solved)
    else:
        not_selected_p_idxs = \
            [p_idx for p_idx in range(D) if p_idx not in selected_p_idxs]
        not_selected_p_idxs = sorted(not_selected_p_idxs, reverse=True)
        # Add n_solved where problems are searched oredred by points DESC
        not_selected_p_idx_highest = not_selected_p_idxs[0]
        addable_score = 100 * p_c_list[not_selected_p_idx_highest][0] * (not_selected_p_idx_highest+1)
        if score_diff + addable_score > 0:
            score_per_p = 100 * (not_selected_p_idx_highest + 1)
            n_undersolved = math.ceil(abs(score_diff) / score_per_p)
            if n_undersolved < p_c_list[not_selected_p_idx_highest][0]:
                n_solved += n_undersolved
            # print('3:', n_solved)
    if n_solved > 0 and score_diff >=0:
        min_n_solved = min(n_solved, min_n_solved)

print(min_n_solved)

Submission status: Accepted

Solution code:
import math

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

ans=100000
for i in range(2**D):
    s=bin(i)[2:].zfill(D)
    x=[int(s[i]) for i in range(D)]
    q,score=0,G
    for i in range(D):
        if x[i]==1:
            q+=a[i][0]
            score -= a[i][0]*(i+1)*100 + a[i][1]


    if score>0:
        for i in range(D-1,-1,-1):
            if x[i]==0:
                k=(a[i][0]-1)*(i+1)*100
                if k>=score:
                    q+= math.ceil( score/((i+1)*100) )
                    score=-1
                    break

                else:
                    q+=a[i][0]-1
                    score-= (a[i][0]-1)*(i+1)*100
        
    if score<=0: ans=min(ans,q)


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)
  
def f(a,b):
  if a==0:
    return 10**9
  m = min(b//(a*100),p[a-1])
  s = 100*a*m
  if m == p[a-1]:
    s += c[a-1]
  if s < b:
    m += f(a-1,b-s)
  return min(m,f(a-1,b))

print(f(D,G))

Submission status: Accepted

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

def solve(d,g):
    if d <= 0:
        return 10**5
    n = min(g//(100*d), points[d-1][0])
    s = 100 * d * n
    if n == points[d-1][0]:
        s = d * points[d-1][0] * 100 + points[d-1][1]
    
    if g > s:
        n += solve(d-1, g-s)
    
    return min(n, solve(d-1, g))
print(solve(D,G))

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
import itertools
import collections
import functools
import math
import operator
from queue import Queue
INF = float("inf")


def dfs(curr, goal, count, probs):
    if curr >= goal:
        return count

    if len(probs) == 0:
        return INF

    # ラス一問目を解かない
    m1 = dfs(curr, goal, count, probs[:-1])

    # ラス一問目を解ききる
    m2 = dfs(curr+probs[-1][0] * probs[-1][1] + probs[-1][2],
             goal, count+probs[-1][1], probs[:-1])

    # ラス一問目を途中まで解く
    m3 = INF
    s = goal-curr
    if (probs[-1][0] * probs[-1][1]) >= s:
        m3 = count + int(math.ceil(s / probs[-1][0]))

    # print(m1, m2, m3, curr, count, probs)
    return min(m1, m2, m3)


def solve(D: int, G: int, p: "List[int]", c: "List[int]"):

    probs = []
    for i in range(D):
        probs.append([100*(i+1), p[i], c[i]])

    m = dfs(0, G, 0, probs)
    print(m)

    return


def main():

    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    D = int(next(tokens))  # type: int
    G = int(next(tokens))  # type: int
    p = [int()] * (D)  # type: "List[int]"
    c = [int()] * (D)  # type: "List[int]"
    for i in range(D):
        p[i] = int(next(tokens))
        c[i] = int(next(tokens))
    solve(D, G, p, c)


if __name__ == '__main__':
    main()