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: Time Limit Exceeded

Solution code:
from collections import deque
D,G = [int(i) for i in input().split()]
P = [0]*D
n = 0
for i in range(D):
    p,c = [int(j) for j in input().split()]
    P[i] = [int(k) * 100 * (i+1) for k in range(p+1)]
    P[i][-1] += c
    n += p
deq = deque()
ans = n
deq.append((0,0,0))
while(len(deq)>0):
    tmp = deq.pop()
    if tmp[0]+1 > len(P):
        break
    for i,j in enumerate(P[tmp[0]]):
        cand = (tmp[0]+1, tmp[1]+i, tmp[2]+j)
        if cand[2] < G:
            if cand[1] < ans:
                deq.appendleft(cand)
        else:
            if cand[1] < ans:
                ans = cand[1]      
print(ans)

Submission status: Time Limit Exceeded

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

p = []

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

nums = []

from itertools import permutations
from math import ceil

for perm in permutations(range(d)):
    s = g
    num = 0
    for i in range(d):
        j = perm[i]
        if s > 100*(j+1)*p[j][0] + p[j][1]:
            s -= 100*(j+1)*p[j][0] + p[j][1]
            num += p[j][0]
        else:
            if s <= 100*(j+1)*(p[j][0] - 1):
                num += ceil(s / (100*(j+1)))
            else:
                num += p[j][0]
            s=0
        if s<=0:
            break
    nums.append(num)

print(min(nums))

Submission status: Time Limit Exceeded

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

dp = defaultdict(int)
dp[0] = 0
for i, (p, c) in enumerate(pc):
    dp_cur = list(dp.items())
    for p_cur, n_cur in dp_cur:
        for n in range(1, p+1):
            if n < p:
                if dp[p_cur+n*100*(i+1)] == 0:
                    dp[p_cur+n*100*(i+1)] = n_cur+n
                else:
                    dp[p_cur+n*100*(i+1)] = min(dp[p_cur+n*100*(i+1)], n_cur+n)
            else:
                if dp[p_cur+n*100*(i+1)+c] == 0:
                    dp[p_cur+n*100*(i+1)+c] = n_cur+n
                else:
                    dp[p_cur+n*100*(i+1)+c] = min(dp[p_cur+n*100*(i+1)+c], n_cur+n)

# print(dp)
ans = 10**9
v = 0
for p, n in list(dp.items()):
    if p < g:
        continue
    else:
        ans = min(ans, n)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
# -*- coding: utf-8 -*-

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

cache = {}

def minsolve(G, p, c, i):
    """100i点以下の問題だけでGを達成する最小問題数"""
    global cache
    if i <= 0:
        return float('inf')
    if (G, i) in cache:
        return cache[(G, i)]
    m = float('inf')
    for n in range(min(ceil(G / (100 * i)), p[i-1]) + 1):
        s = 100 * i * n
        if n == p[i-1]:
            s += c[i-1]
        if s >= G:
            m = min(m, n)
        else:
            m = min(m, n + minsolve(G - s, p, c, i-1))
    cache[(G, i)] = m
    return m

print(minsolve(G, p, c, D))

Submission status: Time Limit Exceeded

Solution code:
from itertools import permutations
from math import ceil, floor

D, G = [int(elem) for elem in input().split(' ')]
point_info_list = [[int(elem) for elem in input().split()] for _ in range(D)]
assert len(point_info_list) == D
assert len(point_info_list[0]) == 2

min_num = float('inf')
for perm in permutations(range(D)):
    current_point = 0
    current_num = 0
    for point in perm:
        if (G - current_point) - (point + 1) * 100 * point_info_list[point][0] <= 0:
            current_num += ceil((G - current_point) / ((point + 1) * 100))
            break
        elif (G - current_point) - (point + 1) * 100 * point_info_list[point][0] - point_info_list[point][1] <= 0:
            current_num += point_info_list[point][0]
            break
        else:
            current_point += (point + 1) * 100 * point_info_list[point][0] + point_info_list[point][1]
            current_num += point_info_list[point][0]
    min_num = min(current_num, min_num)

print(min_num)

Submission status: Time Limit Exceeded

Solution code:
from itertools import permutations

d, g = map(int, input().split())
g = g // 100
p = []
c = []

for _ in range(d):
	pp, cc = map(int, input().split())
	p.append(pp)
	c.append(cc // 100)

ans = float("inf")
for array in permutations(range(d)):
	gap = g
	num = 0
	for a in array:
		if p[a] * (a + 1) >= gap:
			num += (gap - 1) // (a + 1) + 1
			break
		elif p[a] * (a + 1) + c[a] >= gap:
			num += p[a]
			break
		else:
			num += p[a]
			gap -= p[a] * (a + 1) + c[a]

	if num < ans:
		ans = num

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys

stdin = sys.stdin

ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline()

D, G = na()
p = []
c = []
for i in range(D):
    x, y = na()
    p.append(x)
    c.append(y)

ans = 99999999
for i in range(1<<D):
    ct = 0
    score = 0
    for j in range(D):
        if i>>j&1:
            score += c[j]
            score += p[j] * (j+1) * 100
            ct += p[j]
    while score < G:
        for j in range(D-1, -1, -1):
            if i>>j&1: continue
            for k in range(p[j]):
                if score < G:
                    score += (j+1)*100
                    ct += 1
    ans = min(ans, ct)
print(ans)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10 ** 6)

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

def solve(bit):
  if bit >= (1<<D):
    return 1000
  p_sum=0
  num=0
  for i in range(D):
    if bit & (1<<i):
      p_sum += c[i] + p[i] * 100*(i+1)
      num += p[i]
  if p_sum >= G:
    return min(num,solve(bit+1))
  else:
    for i in reversed(range(D)):
      if bit & 1<<i:
        continue
      for j in range(p[i]):
        if p_sum >= G:
          break
        p_sum += 100*(i+1)
        num += 1
      else:
        return solve(bit+1)
    return min(num,solve(bit+1))

print(solve(0))

Submission status: Accepted

Solution code:
# import sys
# sys.setrecursionlimit(10 ** 6)
# import bisect
# from collections import deque
# from decorator import stop_watch
# 
# 
# @stop_watch
def solve(D, G, pc):
    point_map = []
    point_sum = []
    for i in range(D):
        p, c = pc[i]
        tmp = [100 * (i + 1)] * p
        tmp[-1] += c
        point_map.append(tmp)
        point_sum.append(sum(tmp))

    ans = 100 * 11
    for i in range(2 ** D):
        count = 0
        point = 0
        other_problems = []
        for j in range(D):
            if i >> j & 1:
                count += pc[j][0]
                point += point_sum[j]
            else:
                other_problems = point_map[j][:-1] + other_problems
        if point < G:
            for op in other_problems:
                count += 1
                point += op
                if point >= G:
                    break
        if point >= G:
            ans = min(ans, count)
    print(ans)


if __name__ == '__main__':
    D, G = map(int, input().split())
    pc = [[int(i) for i in input().split()] for _ in range(D)]
    solve(D, G, pc)

    # # test
    # from random import randint
    # from func import random_str
    # solve()

Submission status: Accepted

Solution code:
d, g = map(int, input().split())
pc = [list(map(int, input().split())) for i in range(d)]
 
ans = float("inf")
 
for bit in range(1 << d):
    count = 0
    sum = 0
    nokori = set(range(1, d + 1))
 
    for i in range(d):
        if bit & (1 << i):
            sum += pc[i][0] * (i + 1) * 100 + pc[i][1]
            count += pc[i][0]
            nokori.discard(i + 1)
 
    # G 点に満たなければ nokori のうち一番大きいものを解く
    if sum < g:
        use = max(nokori)
        n = min(pc[use - 1][0], -(-(g - sum) // (use * 100)))
        count += n
        sum += n * use * 100
 
    if sum >= g:
        ans = min(ans, count)
 
print(ans)

Submission status: Accepted

Solution code:
"""
中途半端にとく問題は一種類のみで良い。
全探索で全ての点数帯について、ボーナスをとるか・一問もとかないかで全探索
もし点がGに満たない場合は一番点が高いものを解く。
"""
d, g = map(int, input().split())
pc = [list(map(int, input().split())) for i in range(d)]

ans = float("inf")

for bit in range(1 << d):  #2^d通り試す
    count = 0
    sum = 0
    rest = list(range(1, d + 1))  #一問も解いていない点数帯の集合

    for i in range(d):
        if bit & (1 << i):
            sum += pc[i][0] * (i + 1) * 100 + pc[i][1]
            count += pc[i][0]
            rest.remove(i + 1)

    # G 点に満たなければ nokori のうち一番大きいものを解く
    if sum < g:
        use = max(rest)
        n = min(pc[use - 1][0], -(-(g - sum) // (use * 100)))  ##全部解いても足りないかもしれない。-(-a//b))で切り上げをしている。
        count += n
        sum += n * use * 100

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

print(ans)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10 ** 6)

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

def solve(bit):
  if bit >= (1<<D):
    return 1000
  p_sum=0
  num=0
  
  for i in range(D):
    if bit & (1<<i):
      p_sum += pc[i][1] + pc[i][0] * 100*(i+1)
      num += pc[i][0]
  if p_sum >= G:
    return min(num,solve(bit+1))
  else:
    for i in reversed(range(D)):
      if bit & 1<<i:
        continue
      for j in range(pc[i][0]):
        if p_sum >= G:
          break
        p_sum += 100*(i+1)
        num += 1
      else:
        return solve(bit+1)
    return min(num,solve(bit+1))

print(solve(0))

Submission status: Accepted

Solution code:
d,g=[int(_) for _ in input().split()]
l=[0]+[list(map(int,input().split())) for _ in  range(d)]
def f(i,g):
	if i==0:return 10**9
	c=min(g//(100*i),l[i][0])
	s=100*i*c
	if c==l[i][0]:s+=l[i][1]
	if s<g:
		c+=f(i-1,g-s)
	return min(c,f(i-1,g))
print(f(d,g))

Submission status: Accepted

Solution code:
def dfs(i: int, sum: int, count: int, nokori: int) -> int:
    global ans
    if i == d:
        if sum < g:
            use = max(nokori)
            n = min(p[use], -(-(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 + p[i+1]*(i+1)*100+c[i+1], count + p[i+1], nokori - {i+1})

d,g = map(int, input().split())
p = [0] * (d+1)
c = [0] * (d+1)

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

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,c = map(int,input().split())
    P.append(p)
    C.append(c)

ans = 1000
for i in range(2**D):
    point = 0
    num = 0
    unsolved = []
    for j in range(D):
        if (i >> j)&1 == 1:
            point += 100*(j + 1)*P[j] + C[j]
            num += P[j]
        
        else:
            unsolved.append(j)

    if G <= point:
        ans = min(num, ans)
    
    
    else:
        l = []
        unsolved.reverse()
        for i in unsolved:
            l += [100*(i + 1)]*(P[i] - 1)
        for j in range(len(l)):
            point += l[j]
            num += 1

            if G <= point:
                ans = min(num, ans)
print(ans)

Submission status: Accepted

Solution code:
def main():
	D,G = map(int,input().split())
	ListPC = [list(map(int,input().split())) for d in range(D)]
	ans = sum([i[0] for i in ListPC])

	for i in range(2**D):
		# 点数,正解数,解いてない最高点数idx
		TempPoint,num,restmax = 0,0,-1
		# 全埋め問題加算
		for j in range(D):
			if i>>j & 1:
				TempPoint += 100*(j+1)*ListPC[j][0]+ListPC[j][1]
				num += ListPC[j][0]
			else:
				restmax = max(j,restmax)
		# 合格なら更新
		if TempPoint >= G:
			ans = min(num,ans)
		# 最高問題解いて合格なら更新
		elif (G - TempPoint) // ((restmax + 1) * 100) <= ListPC[restmax][0]:
			ans = min(num + (G - TempPoint - 1) // ((restmax + 1) * 100) + 1, ans)
	print(ans)

if __name__ == '__main__':
	main()

Submission status: Accepted

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

ans = 1000
for b in range(2**D):
    score = 0
    solve = 0
    unsolved = []
    for i in range(D):
        if (b >> i) & 1:
            score += C[i] + 100 * (i + 1) * P[i]
            solve += P[i]
        else:
            unsolved.append(i)
    if G > score:
        resprbs = []
        unsolved.reverse()
        for i in unsolved:
            resprbs += [100 * (i + 1)] * (P[i] - 1)
        for j in range(len(resprbs)):
            score += resprbs[j]
            solve += 1
            if G <= score:
                break
    if G <= score:
        ans = min(ans, solve)

print(ans)

Submission status: Accepted

Solution code:
def cal():
    d, g = map(int, input().split())
    a = [list(map(int, input().split())) for i in range(d)]
    ans = float('inf')

    for i in range(2**d):
        b = ['-']*d
        for j in range(d):
            if (i>>j)&1:
                b[j] = '+'
        count0, count1 = 0, 0
        for j in range(d):
            if b[j] == '+':
                count0 += 100*(j+1)*a[j][0]+a[j][1]
                count1 += a[j][0]
        if count0 < g:
            for j in range(d-1, -1, -1):
                if b[j] == '-':
                    for k in range(a[j][0]):
                        if count0 >= g:
                            break
                        count0 += 100*(j+1)
                        count1 += 1
        ans = min(ans, count1)
    print(ans)
cal()

Submission status: Accepted

Solution code:
from itertools import product

D, G = map(int, input().split())
G //= 100
prob = []

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

ans = 1000
for comp in product((0, 1), repeat=D):
  cnt, score = 0, 0
  for i, c in enumerate(comp):
    if c:
      cnt += prob[i][1]
      score += prob[i][0]*prob[i][1] + prob[i][2]
  j = D-1
  while score < G and j >= 0:
    if comp[j] == 0:
      if score + prob[j][0]*prob[j][1] <= G:
        cnt += prob[j][1]
        score += prob[j][0]*prob[j][1]
      else:
        temp = -(-(G - score)//prob[j][0])
        cnt += temp
        score += prob[j][0]*temp
    j -= 1
  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())

ans=1000
for i in range(2 ** D):
    op = ["-"] * D
    for j in range(D):
        if ((i >> j) & 1):
            op[D - 1 - j] = "+"
    s=0
    cnt=0
    for j in range(D):
        if op[j]=="+":
            s+=100*(j+1)*p[j]
            s+=c[j]
            cnt+=p[j]
    if s<G:
        for j in range(D-1,-1,-1):
            if op[j]=="-":
                for k in range(p[j]):
                    if s>=G:
                        break
                    s+=100*(j+1)
                    cnt+=1
    ans=min(cnt,ans)

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 = 10000000
for i in range(1 << d):
    s = set()
    use = 0
    res = 0
    for j in range(d):
        if i >> j & 1:
            use += p[j]
            res += p[j] * (j + 1) + c[j]
            s.add(j)
    for j in range(d - 1, -1, -1):
        if res >= g:
            break
        if j in s:
            continue
        use += min(p[j], (g - res + j) // (j + 1))
        res += min(p[j], (g - res + j) // (j + 1)) * (j + 1)
    if res >= g:
        ans = min(ans, use)
print(ans)

Submission status: Accepted

Solution code:
import bisect, collections, copy, heapq, itertools, math, string, sys
input = lambda: sys.stdin.readline().rstrip() 
sys.setrecursionlimit(10**7)
INF = float('inf')
def I(): return int(input())
def F(): return float(input())
def SS(): return input()
def LI(): return [int(x) for x in input().split()]
def LI_(): return [int(x)-1 for x in input().split()]
def LF(): return [float(x) for x in input().split()]
def LSS(): return input().split()

def resolve():
    D, G = LI()
    pc = [LI() for _ in range(D)]

    # コンプリートする問題を全パターン試す
    # 足りない分があれば解いてない最高点数の問題で埋める
    ans = sum([i[0] for i in pc])
    for i in range(2 ** D):
        score = 0
        num = 0
        not_completed_max = -1
        for j in range(D):
            if i >> j & 1:
                score += pc[j][0] * (j + 1) * 100  + pc[j][1]
                num += pc[j][0]
            else:
                not_completed_max = max(j, not_completed_max)
        if score >= G:
            ans = min(num, ans)
        elif (G - score) // ((not_completed_max + 1) * 100) <= pc[not_completed_max][0]:
            ans = min(num + (G - score - 1) // ((not_completed_max + 1) * 100) + 1, ans)

    print(ans)

if __name__ == '__main__':
    resolve()

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())
ans = 10000000
for i in range(1 << d):
    s = set()
    use = 0
    res = 0
    for j in range(d):
        if i >> j & 1:
            use += p[j]
            res += p[j] * (j + 1) * 100 + c[j]
            s.add(j)
    for j in range(d - 1, -1, -1):
        if res >= g:
            break
        if j in s:
            continue
        use += min(p[j], (g - res + j) // (100 * (j + 1)))
        res += min(p[j], (g - res + j) // (100 * (j + 1))) * 100 * (j + 1)
    if res >= g:
        ans = min(ans, use)
print(ans)

Submission status: Accepted

Solution code:
d, gl = map(int, input().split())
p = []
g = []
for i in range(d):
  P,G = map(int, input().split())
  p.append(P)
  g.append(G)
ans = sum(p)
for i in range(1<<d):
  tmp = 0
  c = 0
  b = [0 for i in range(d)]
  for j in range(d):
    if i&(1<<j):
      tmp += g[j] + (j+1)*p[j]*100
      c += p[j]
      b[j] = 1
  s = d-1
  while tmp < gl and s >= 0:
    if b[s] == 1:
      s -= 1
    else:
      for k in range(p[s]):
        tmp += 100*(s+1)
        c += 1
        if tmp >= gl:
          break
      s -= 1
  ans = min(ans,c)
print (ans)

Submission status: Accepted

Solution code:
d, gl = map(int, input().split())
p = []
g = []
for i in range(d):
  P,G = map(int, input().split())
  p.append(P)
  g.append(G)
ans = sum(p)
for i in range(1<<d):
  tmp = 0
  c = 0
  b = [0 for i in range(d)]
  for j in range(d):
    if i&(1<<j):
      tmp += g[j] + (j+1)*p[j]*100
      c += p[j]
      b[j] = 1
  s = d-1
  while tmp < gl and s >= 0:
    if b[s] == 1:
      s -= 1
    else:
      for k in range(p[s]):
        tmp += 100*(s+1)
        c += 1
        if tmp >= gl:
          break
      s -= 1
  if tmp >= gl:
    ans = min(ans,c)
print (ans)

Submission status: Accepted

Solution code:
import math
from typing import List, Any


def read_int() -> int:
    return int(input().strip())


def read_ints() -> List[int]:
    return list(map(int, input().strip().split(' ')))


def solve() -> Any:
    D, G = read_ints()
    p: List[int]= []
    c: List[int]= []
    for _ in range(D):
        pc = read_ints()
        p.append(pc[0])
        c.append(pc[1])
    count = [0]*(1<<D)
    score = [0]*(1<<D)
    for i in range(D):
        count[1<<i] = p[i]
        score[1<<i] = c[i]+(p[i]*100*(i+1))
    for i in range(1, 1<<D):
        submask = i&(i-1)
        submask_complement = i-submask
        count[i] = count[submask]+count[submask_complement]
        score[i] = score[submask]+score[submask_complement]
    min_count = 10**9
    for i in range(1<<D):
        for j in range(D):
            if i&(1<<j) == 0 and score[i] < G and score[i]+score[1<<j] >= G:
                required_count = math.ceil((G-score[i])/((j+1)*100))
                if required_count < count[1<<j]:
                    min_count = min(min_count, required_count+count[i])
                else:
                    min_count = min(min_count, count[1<<j]+count[i])
    return min_count


if __name__ == '__main__':
    print(solve())

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):
  al=[]
  notal=[]
  anstmp=0
  score=0
  for j in range(d):
    if (i>>j)&1:al.append(j)
    else:notal.append(j)
  for j in al:
    score+=(j+1)*100*pc[j][0]
    score+=pc[j][1]
    anstmp+=pc[j][0]
  while notal and score<g:
    j=notal.pop()
    k=(g-score+(j+1)*100-1)//((j+1)*100)
    k=min(k,pc[j][0]-1)
    score+=(j+1)*100*k
    anstmp+=k
  if score>=g:ans=min(ans,anstmp)
print(ans)

Submission status: Accepted

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

mn=10000
for i in range(2**d):
  pcnt=0
  qcnt=0
  nm=None
  for j in range(d):
    if i&(2**j):
      pcnt+=(j+1)*l[j][0]+l[j][1]
      qcnt+=l[j][0]
    else:
      nm=j
  if pcnt<g:
    need=(g-pcnt-1)//(nm+1)+1
    if need<l[nm][0]:
      qcnt+=need
    else:
      qcnt+=10000
  mn=min(mn,qcnt)
print(mn)

Submission status: Accepted

Solution code:
from math import ceil
D, G = map(int,input().split())
ps, cs = [], []
for _ in range(D):
    p, c = map(int,input().split())
    ps.append(p)
    cs.append(c)
ans = float("inf")
for i in range(2**D):
    cnt = 0
    point = 0
    for j in range(D):
        if (i>>j)&1:
            cnt += ps[j]
            point += ps[j]*100*(j+1)+cs[j]
    if point >= G:
        ans = min(ans, cnt)
        continue
    for j in range(D-1, -1, -1):
        if (i>>j)&1 == 0:
            if (ps[j]-1)*100*(j+1)+point >= G:
                cnt += ceil((G-point)/100/(j+1))
                point += ceil((G-point)/100/(j+1))*100*(j+1)
                break
            else:
                cnt += (ps[j]-1)
                point += (ps[j]-1)*100*(j+1)
    if point >= G:
        ans = min(ans, cnt)
print(ans)

Submission status: Accepted

Solution code:
d, g = map(int, input().split())
pc = [0] + [list(map(int, input().split())) for i in range(d)]
def dfs(ind,score):
  if ind == 0:
    return float("inf")
  cnt = min(score//(ind*100),pc[ind][0])
  add_sc = cnt*(ind*100)
  if cnt == pc[ind][0]:
    add_sc += pc[ind][1]
  if add_sc < score:
    cnt += dfs(ind-1,score-add_sc)
  return min(cnt,dfs(ind-1,score))

print(dfs(d,g))

Submission status: Accepted

Solution code:
from itertools import product

d, g = map(int, input().split())
g //= 100
p, c = [], []
for _ in range(d):
    i, j = map(int, input().split())
    p.append(i)
    c.append(j // 100)

# full search about complete bonuses
ans = sum(p)
for tf in product([True, False], repeat=d):
    score = 0
    cnt = 0

    for ind in range(d):
        if tf[ind]:
            cnt += p[ind]
            score += (ind + 1) * p[ind] + c[ind]
    
    for ind in range(d-1, -1, -1):
        if score >= g:
            break

        if tf[ind]:
            continue
        
        if (ind + 1) * p[ind] + score <= g:
            cnt += p[ind]
            score += (ind + 1) * p[ind]
        else:
            cnt += (g - score - 1) // (ind + 1) + 1
            score = g
    
    if score >= g and ans > cnt:
        ans = cnt

print(ans)

Submission status: Accepted

Solution code:
# 未知のアルゴリズムか天才系DPかと思ってすぐ諦めて解説読んでしまった

d, g = map(int, input().split())
points = []
for _ in range(d):
    p, c = map(int, input().split())
    points.append((p, c))
ans = 10**12
for bit in range(2**d):
    arr = [False] * d
    for i in range(d):
        if bit >> i & 1 == 1:
            arr[i] = True
    tmp_sum = 0
    count = 0
    for i in range(d):
        if arr[i]:
            # kompuli-to
            tmp_sum += points[i][1]
            tmp_sum += (i + 1) * 100 * points[i][0]
            count += points[i][0]
    if tmp_sum < g:
        # 達成できるまで得点の高いやつからやっていく
        for i in range(d - 1, -1, -1):
            if arr[i]:
                # すでにkompuli-toしてるので
                continue
            used = 0
            for j in range(points[i][0]):
                if tmp_sum < g:
                    tmp_sum += (i + 1) * 100
                    count += 1
                    used += 1
            if used == points[i][0]:
                tmp_sum += points[i][1]
            if tmp_sum >= g:
                break
    ans = min(ans, count)
print(ans)

Submission status: Accepted

Solution code:
d, g = map(int, input().split())
pc = [0] + [list(map(int, input().split())) for i in range(d)]
def dfs(d_, g_):
    if d_ == 0:
        return float("inf")
    cnt = min(g_ // (d_ * 100), pc[d_][0])
    cur = cnt * 100 * d_
    if cnt == pc[d_][0]:
        cur += pc[d_][1]
    if g_ > cur:
        cnt += dfs(d_ - 1, g_ - cur)
    return min(cnt, dfs(d_ - 1, g_))
print(dfs(d, g))

Submission status: Accepted

Solution code:
# coding: utf-8
# Your code here!
from itertools import product

ans = 10**9

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

for p in product([True, False], repeat=D):
    
    point = 0
    num = 0
    
    for i in range(D):
        if p[i]:
            point += (i+1) * 100 * problem[i][0] + problem[i][1]
            num += problem[i][0]
            
    if point >= G:
        ans = min(ans, num)
    
    for i in reversed(range(D)):
        if p[i] == False:
            if point >= G:
                ans = min(ans, num)
                break
            for j in range(problem[i][0]):
                point += (i+1) * 100
                num += 1
                if point >= G:
                    break
    if point >= G:
        ans = min(ans, num)
print(ans)

Submission status: Accepted

Solution code:
d, g = map(int, input().split())
pc = [0] + [list(map(int, input().split())) for i in range(d)]
def dfs(d_, g_):
    if d_ == 0:
        return float("inf")
    cnt = min(g_ // (d_ * 100), pc[d_][0])
    cur = cnt * 100 * d_
    if cnt == pc[d_][0]:
        cur += pc[d_][1]
    if g_ > cur:
        cnt += dfs(d_ - 1, g_ - cur)
    return min(cnt, dfs(d_ - 1, g_))
print(dfs(d, g))

Submission status: Accepted

Solution code:
import math
d,g = map(int,input().split())
prob = []
for i in range(d):
  p,c = map(int,input().split())
  prob.append([p,c,p*(i+1)*100+c])
  
mindays = 10**9
for i in range(2**d):
  point = 0
  days = 0
  one = []
  for j in range(d):
    if ((i>>j)&1)==0:
      point += prob[j][2]
      days += prob[j][0]
    else:
      one.append(j+1)
  if point>=g:
    mindays = min(mindays,days)
  elif point<g:
    for k in range(len(one)):
        day =days
        tmp = math.ceil((g-point)/(one[k]*100))
        if tmp<=prob[one[-1]-1][0]:
          day += tmp
          mindays = min(mindays,day)
print(mindays)

Submission status: Accepted

Solution code:
import math

if __name__ == "__main__":
    D, G = map(int, input().split())
    p_c_l = [list(map(int, input().split())) for _ in range(D)]
    _min = sum([p_c[0] for p_c in p_c_l])
    for i in range(2 ** D):
        count = 0
        total = 0
        bins = '{:0={}b}'.format(i, D)
        incomplete_index = int(bins.rfind('0'))
        for index, _bin in enumerate(bins):
            if _bin == '0':
                continue
            total += 100 * (index + 1) * p_c_l[index][0] + p_c_l[index][1]
            count += p_c_l[index][0]
        if incomplete_index == -1:
            break
        remaining = G - total
        if remaining <= 0:
            if count < _min:
                _min = count
            continue
        incomplete_p = 100 * (incomplete_index + 1)
        incomplete_ans_num = math.ceil(remaining / incomplete_p)
        incomplete_p_num = p_c_l[incomplete_index][0]
        if incomplete_ans_num >= incomplete_p_num:
            continue
        count += incomplete_ans_num
        if count < _min:
            _min = count

    print(_min)

Submission status: Accepted

Solution code:
D, G = map(int, input().split())
p = []
c = []
for _ in range(D):
    t1, t2 = map(int, input().split())
    p.append(t1)
    c.append(t2)
ans = float("inf")
for i in range(2**D):
    not_complete = []
    score = 0
    tmp = 0
    for j in range(D):
        if (i>>j & 1):
            score += 100 * (j+1) * p[j] + c[j]
            tmp += p[j]
        else:
            not_complete.append(j)
    if score >= G:
        ans = min(ans, tmp)
        continue
    
    not_complete.sort(reverse=True)
    for j in not_complete:
        rest = p[j]
        while score < G and rest > 1:
            rest -= 1
            score += 100*(j+1)
            tmp += 1
    if score >= G:
        ans = min(ans, tmp)
print(ans)