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 sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians, log2
from itertools import accumulate, permutations, combinations, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce
import numpy as np
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7
 
D, G = MAP()
pc = [LIST() for _ in range(D)]
count_min = 1000000000

#i番目の問題を完全に解くかをbitで場合わけしてからのfor　　O(D 2^D)
for i in range(1<<D):
	sum_ = 0
	count = 0
	i = list("{:b}".format(i).zfill(D))
	#print(i)
	for j in range(D):
		if i[j] == "1":    # j = "1" なら全部加える
			sum_ += (j+1)*100*pc[j][0] + pc[j][1]
			count += pc[j][0]
	if sum_ >= G:
		if count < count_min :
			#print("更新", count_min, "->", count)
			count_min = count
	else:  #中途半端にとる
		for j in range(D-1, -1, -1):
			if i[j] == "0":   # G-sum_ : 残りのポイント
				num = ceil((G-sum_)/((j+1)*100))
				#print(num)
				if num > pc[j][0]:
					count = 1000000000
					break
				count += ceil((G-sum_)/((j+1)*100))
				break
		if count < count_min:
			#print("更新", count_min, "->", count)
			count_min = count

print(count_min)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3

import sys
import math
# from string import ascii_lowercase, ascii_upper_case, ascii_letters, digits, hexdigits
# import re                                    # re.compile(pattern) => ptn obj; p.search(s), p.match(s), p.finditer(s) => match obj; p.sub(after, s)
# from operator import itemgetter              # itemgetter(1), itemgetter('key')
# from collections import deque                # deque class. deque(L): dq.append(x), dq.appendleft(x), dq.pop(), dq.popleft(), dq.rotate()
# from collections import defaultdict          # subclass of dict. defaultdict(facroty)
# from collections import Counter              # subclass of dict. Counter(iter): c.elements(), c.most_common(n), c.subtract(iter)
# from heapq import heapify, heappush, heappop # built-in list. heapify(L) changes list in-place to min-heap in O(n), heappush(heapL, x) and heappop(heapL) in O(lgn).
# from heapq import nlargest, nsmallest        # nlargest(n, iter[, key]) returns k-largest-list in O(n+klgn).
# from itertools import count, cycle, repeat   # count(start[,step]), cycle(iter), repeat(elm[,n])
# from itertools import groupby                # [(k, list(g)) for k, g in groupby('000112')] returns [('0',['0','0','0']), ('1',['1','1']), ('2',['2'])]
# from itertools import starmap                # starmap(pow, [[2,5], [3,2]]) returns [32, 9]
from itertools import product, permutations  # product(iter, repeat=n), permutations(iter[,r])
# from itertools import combinations, combinations_with_replacement
# from itertools import accumulate             # accumulate(iter[, f])
# from functools import reduce                 # reduce(f, iter[, init])
# from functools import lru_cache              # @lrucache ...arguments of functions should be able to be keys of dict (e.g. list is not allowed)
# from bisect import bisect_left, bisect_right # bisect_left(a, x, lo=0, hi=len(a)) returns i such that all(val<x for val in a[lo:i]) and all(val>-=x for val in a[i:hi]).
# from copy import deepcopy                    # to copy multi-dimentional matrix without reference
# from fractions import gcd                    # for Python 3.4 (previous contest @AtCoder)


def main():
    mod = 1000000007                # 10^9+7
    inf = float('inf')              # sys.float_info.max = 1.79...e+308
    # inf = 2 ** 64 - 1               # (for fast JIT compile in PyPy) 1.84...e+19
    sys.setrecursionlimit(10**6)    # 1000 -> 1000000
    def input(): return sys.stdin.readline().rstrip()
    def ii():    return int(input())
    def mi():    return map(int, input().split())
    def mi_0():  return map(lambda x: int(x)-1, input().split())
    def lmi():   return list(map(int, input().split()))
    def lmi_0(): return list(map(lambda x: int(x)-1, input().split()))
    def li():    return list(input())


    def calc_minimum_num_of_problems(comp_list, target_score):
        constraints = problem[:]
        num_of_problems = 0
        for i, elm in enumerate(comp_list):
            # complete するという前提
            if elm:
                target_score -= problem[i] * (i + 1)    # 基礎点が全て確定
                target_score -= bonus[i]    # ボーナス点が確定
                num_of_problems += problem[i]    # 解いた問題に加算されてしまう
                constraints[i] = 0    # これ以上解いていい問題はない
            else:
                constraints[i] -= 1    # complete はしちゃダメ
        # print(f"comp list {comp_list}")
        # print(f"constrains {constraints}")
        # print(f"target {target_score}")
        # 後は基礎点が高い順に貪欲
        for i in range(d - 1, -1, -1):
            if target_score <= 0:
                break
            if constraints[i] * (i + 1) <= target_score:
                target_score -= constraints[i] * (i + 1)
                num_of_problems += constraints[i]
                constraints[i] = 0
            else:
                solved = math.ceil(target_score / (i + 1))
                target_score -= solved * (i + 1)
                assert(target_score <= 0)
                num_of_problems += solved
                constraints[i] -= solved
        if target_score > 0:
            num_of_problems = float('inf')
        # print(num_of_problems)
        return num_of_problems
    
    
    d, g = mi()
    g //= 100
    problem = []    # 第 k 問 (k 点) は problem[k-1] 個ある
    bonus = []    # 第 k 問をコンプすると bonus[k-1] 点を得る
    for _ in range(d):
        p, b = mi()
        problem.append(p)
        bonus.append(b // 100)
    
    ans = float('inf')
    for complete_or_not in product([True, False], repeat=d):
        ans = min(ans, calc_minimum_num_of_problems(complete_or_not, g))
    print(ans)



if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
def main():
    from itertools import combinations_with_replacement
    from math import ceil

    d, g, *pc = map(int, open(0).read().split())
    p, c = pc[::2], pc[1::2]
    ans = sum(p)
    
    q = ceil(g / (d * 100))
    if q < p[-1]:
        ans = q
        
    l = range(d)
    for x in combinations_with_replacement(l, d):
        y = list(set(x))
        tmp = g
        count = 0
        for i in y:
            tmp -= ((i + 1) * 100 * p[i] + c[i])
            count += p[i]
        if tmp <= 0:
            ans = min(ans, count)
        else:
            j = max(set(l) - set(x))
            k = ceil(tmp / (100 * (j + 1)))
            if k < p[j]:
                count += k
                ans = min(ans, count)

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def main():
    from math import ceil
    d, g, *pc = map(int, open(0).read().split())
    p, c = pc[::2], pc[1::2]

    ans = sum(p)

    for i in range(2 ** d - 1):
        tmp = g
        count = 0
        # i は集合の表現 ex 1001101
        for j in range(d):
            # iのj桁目が1はどうか
            if i >> j & 1:
                # process
                tmp -= (c[j] + 100 * (j + 1) * p[j])
                count += p[j]

        j = d - 1
        while i >> j & 1:
            j -= 1

        if tmp <= 0:
            ans = min(ans, count)
            continue
        else:
            k = ceil(tmp / ((j + 1) * 100))
            if k >= p[j]:
                continue
            else:
                count += k
                ans = min(count, ans)

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

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

N=0
for i in range(D):
    N+=pc[i][0]

MIN_SUM=N
for n in range(2**D):
    score=0
    SUM=0
    for i in range(D):
        if (n>>i)&1==1:
            SUM+=pc[i][0]
            score+=100*(i+1)*pc[i][0]+pc[i][1]
    if score>=G:
        pass
    else:
        for j in reversed(range(D)):
            if (n>>j)&1==0:
                cnt=0
                while cnt<=pc[j][0]-2 and score<G:
                    score+=100*(j+1)
                    SUM+=1
                    cnt+=1
    if score>=G and SUM<=MIN_SUM:
        MIN_SUM=SUM

print(MIN_SUM)

Submission status: Accepted

Solution code:
def parial_solve(G, pb_set):
    if(G >= pb_set[3]):
        return -1
    for num in range(pb_set[1]):
        score = pb_set[0] * num
        if(score >= G):
            return num
    return -1       

def main():
    import heapq
    from itertools import combinations

    D, G = map(int, input().split())
    pc = []
    answer_list = []
    for i in range(1, D+1, 1):
        prob_num, bonus_score = map(int, input().split())
        # List of problem set:(score for single prob, num of prob, bonus score)
        total_score = 100 * i * prob_num + bonus_score
        pc.append((i*100, prob_num, bonus_score, total_score))

    for i in range(D+1):
        for comb in combinations(range(D), i):
            score = 0
            answer_num = 0
            for p_index in comb:
                prob = pc[p_index]
                score += prob[3]
                answer_num += prob[1]
            if(score >= G):
                # Not neeed to use partial solve
                answer_list.append((answer_num, comb))
            else:
                # Partial solve for 
                max_prob_index = max(set(range(D)) - set(comb))
                pb_set = pc[max_prob_index]
                partial_solve_num = parial_solve(G - score, pb_set)
                if(partial_solve_num == -1):
                    continue
                else:
                    answer_list.append((answer_num+partial_solve_num, comb, max_prob_index))
    import heapq
    heapq.heapify(answer_list)
    print(heapq.heappop(answer_list)[0])

main()

Submission status: Accepted

Solution code:
#template
def inputlist(): return [int(k) for k in input().split()]
def base10to(n, b):
    if (int(n/b)):
        return base10to(int(n/b), b) + str(n%b)
    return str(n%b)
def len_check(k,n):
    if len(k) == n:
        return k
    else:
        for _ in range(n-len(k)):
            k = '0'+k
        return k
#template
D,G = inputlist()
ans = 10**9
li = [0]*D
for i in range(D):
    li[i] = inputlist()
for i in range(2**D):
    lis = []
    k = base10to(i,2)
    k = len_check(k,D)
    for d in range(D):
        if k[d] == '1':
            otake = [(d+1)*100] + li[d]
            lis.append(otake)
    lis.sort(reverse=True)
    n = len(lis)
    tmp = 0
    count = 0
    for t in range(n):
        p = lis[t][1]
        point = lis[t][0]
        for pt in range(1,p+1):
            tmp += point
            count +=1
            if pt == p:
                tmp += lis[t][2]
            if tmp >= G:
                ans = min(ans,count)
                break
print(ans)

Submission status: Accepted

Solution code:
d, g = map(int, input().split())
a = []
min_cnt = 1000
for i in range(1, d + 1):
    p, c = map(int, input().split())
    a.append([p, i * p * 100 + c])
for i in range(0, 2 ** d):
    b = bin(i)[2:].zfill(d)
    score = sum(int(b[i]) * a[i][1] for i in range(d))
    cnt = sum(int(b[i]) * a[i][0] for i in range(d))
    if score >= g:
        min_cnt = min(min_cnt, cnt)
    else:
        for j in range(d-1, -1, -1):
            if b[j] == '0':
                break
        tmp_cnt = (g - score - 1) // (100 * (j + 1)) + 1
        if a[j][0] >= tmp_cnt:
            min_cnt = min(min_cnt, cnt+tmp_cnt)
print(min_cnt)

Submission status: Accepted

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

total = 10000
for i in range(2**D):
    sum_score = 0
    flag = 0
    total_temp = 0
    for j in range(D):
        if i >> j & 1 :
            sum_score += score[j][0]*100*(j+1)+score[j][1]
            total_temp += score[j][0]
        else:
            flag = j
    if sum_score >= G and total >= total_temp:
        total = total_temp
    elif sum_score < G:
        for _ in range(score[flag][0]-1):
            sum_score += (flag+1)*100
            total_temp += 1
            if sum_score >= G and total >= total_temp:
                total = total_temp
                break
print(total)

Submission status: Accepted

Solution code:
import itertools
from pprint import pprint


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

plist=[]
clist=[]

bonus_masterlist=[]

for _ in range(d):
    p_temp,c_temp = map(int,input().split())
    plist.append(p_temp)
    clist.append(c_temp)


bonus_masterlist = list(itertools.product(range(2), repeat=d))
#bit全探索をやらなくても、itertoolsを使えば一瞬でできちゃう。(タプルのリスト)
#for i in range(2**d):
#    bonus_templist = [0] * d
#    for j in range(d):
#        if i >> j & 1:
#            bonus_templist[d-1-j] = 1
#    bonus_masterlist.append(bonus_templist)

#point_list = [100,200,300, ... ,d*100]
#max_list: plist = [p[0],p[1],p[2], ... ,p[d]]
#bonuspoint_list: clist = [c[0],c[1],c[2], ... ,c[d]]

count_list = [0] * d

mincount = 100 * 10

"""
def dfs(i):
    global mincount
    if sum([count_list[i] * 100*(i+1) for i in range(d)]) + sum([bonus_list[j] * clist[j] for j in range(d)]) >= g:
        if sum(count_list) < mincount:
            mincount = sum(count_list)
    elif plist[i] == count_list[i]:
        bonus_list[i] = 1
        dfs(i-1)
    elif plist[i] > count_list[i]:
        count_list[i] += 1
        dfs(i)
    return
"""

for bonus_tuple in bonus_masterlist:
    bonus_list = list(bonus_tuple)
    count_list = [x * y for (x, y) in zip(bonus_list, plist)]
    i = d-1
    while True:
        if sum([count_list[i] * 100*(i+1) for i in range(d)]) + sum([bonus_list[j] * clist[j] for j in range(d)]) >= g:
            if sum(count_list) < mincount:
                mincount = sum(count_list)
            break
        elif plist[i] == count_list[i]:
            bonus_list[i] = 1
            i -= 1
            continue
        elif plist[i] > count_list[i]:
            count_list[i] += 1
            continue


print(mincount)

Submission status: Accepted

Solution code:
d, g = [int(i) for i in input().split()]
p, c = [0] * d, [0] * d
for i in range(d):
    p[i], c[i] = [int(j) for j in input().split()]

ans = float('inf')
for bit in range(1 << d):
    tot = 0
    num = 0
    for i in range(d):
        if bit >> i & 1:
            tot += c[i] + p[i]*100*(i + 1)
            num += p[i]
    if tot >= g:
        ans = min(ans, num)
    else:
        for i in reversed(range(d)):
            if bit >> i & 1:
                continue
            for j in range(p[i]):
                if tot >= g:
                    break
                tot += 100 * (i + 1)
                num += 1
        ans = min(ans, num)
print(ans)

Submission status: Accepted

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

ans = sum(Problems)

for i in range(2**D):
    a = 0
    solved_num = 0
    for j in range(D):
        if (i >> j) & 1:
            a += Complete_Bonus[j] + Problems[j] * (j + 1) * 100
            solved_num += Problems[j]
    if a >= G:
        ans = min(ans, solved_num)
    else:
        flag = False
        for j in range(D):
            if flag:
                break
            if not ((i >> (D - j - 1)) & 1):
                for k in range(Problems[D-j-1]):
                    a += 100 * (D-j)
                    solved_num += 1
                    if a >= G:
                        ans = min(ans, solved_num)
                        flag = True
                        break

print(ans)

Submission status: Accepted

Solution code:
D,G=[int(x) for x in input().rstrip().split()]
l=[]
val=[]
ans_cnt=float('inf')
cnt=float('inf')
now=0
for i in range(D):
  pc=[int(x) for x in input().rstrip().split()]


  l.append(pc)
kai=0
for i in range(2**D):
  for j in range(D):#現在のiを2進数で表したものをシフトさせるためのfor文
    if ((i>>j) & 1):
      kai=l[D-j-1][0]#D=4でj=0のときは0001などの時にインデックス3を参照したい。
      for s in range(kai):
        if s+1==kai:
          now+=l[D-j-1][1]
        
        now+=(D-j)*100
        cnt+=1   

        if G<=now:
          ans_cnt=min(ans_cnt,cnt)
          break

  cnt=0
  now=0

print(ans_cnt)

Submission status: Accepted

Solution code:
d,g=map(int,input().split())
pc=[list(map(int,input().split())) for _ in range(d)]
ans=1000
for i in range(2**d):
    s,cnt=0,0
    for j in range(d):
        if i>>j&1:
            s+=pc[j][0]*(j+1)*100+pc[j][1]
            cnt+=pc[j][0]
    if s<g:
        k=d-1
        while i>>k&1:
            k-=1
            if k<0:
                break
        if k>=0:
            if g-s>=pc[k][0]*(k+1)*100:
                continue
            else:
                cnt+=(g-s)//((k+1)*100)+1
                if (g-s)%((k+1)*100)==0:
                    cnt-=1
                ans=min(ans,cnt)
    else:
        ans=min(ans,cnt)
print(ans)

Submission status: Accepted

Solution code:
import sys
d, g = map(int, input().split())
g=g//100
pc=[[0,0]]
ans=sys.maxsize
for i in range(d):
  pc.append(list(map(int,input().split())))

for i in range(2**d):
  temp=0
  cnt=0
  for j in range(1,d+1):
    p=pc[j][0]
    c=pc[j][1]//100
    if (i>>(j-1)) & 1:
      temp+=(p*j+c)
      cnt+=p
  if temp >= g:
    ans=min(ans,cnt)
  else:
    for j in range(d,0,-1):
      p=pc[j][0]
      if (not ((i>>(j-1)) & 1)):
        if temp + j*p >= g:
          h=(((g-temp)//j)+1)
          if (g-temp)%j == 0:
            h-=1
          cnt+=h
          ans=min(ans,cnt)
        break
print(ans)

Submission status: Accepted

Solution code:
import itertools
n, g = map(int, input().split())
L = []
for i in range(n):
    t = list(map(int, input().split()))
    # 配点
    t.append((i+1)*100)
    # この配点の問題を全部解いた時の得点
    t.append((i+1)*100*t[0]+t[1])
    L.append(t)
# print(L)

ans = g//100
# https://img.atcoder.jp/abc104/editorial.pdf bit全探索
for i in range(2**n):
    count = 0
    score = 0
    m = 0
    for j in range(n):
        if (i >> j) & 1:
            score += L[j][3]
            count += L[j][0]
        else:
            m = j
    # print(bin(i), m, score, count)
    if score >= g:
        ans = min(ans, count)
    else: # 解いていない配点の問題の中で一番配点が高いもの
        if (g - score)/L[m][2] <= L[m][0] and (g - score)%L[m][2] == 0:
            count += (g - score)//L[m][2]
        elif (g - score)/L[m][2] + 1 <= L[m][0]:
            count += ((g - score)//L[m][2])+1
        else:
            count = g//100
        ans = min(ans, count)
    # print(bin(i), m, L[m], score, count)
print(ans)

# 全探索したら時間超過
# ans = 100 * n
# for v in itertools.permutations(L):
#     score = 0
#     count = 0
#     k = 0
#     p = v[k][0]
#     while score < g:
#         score += v[k][2]
#         p -= 1
#         count += 1
#         if p == 0:
#             score += v[k][1]
#             k += 1
#             if k < n:
#                 p = v[k][0]
#     ans = min(ans, count)
# print(ans)

# DPっぽく解こうとしたけど失敗
# P = []
# G = []
# for i in range(n):
#     s, t = map(int, input().split())
#     P.insert(0, s)
#     G.insert(0, t//100)
# score = 0
# k = 0
# count = 0
# while score < g:
#     count += 1
#     if 1 in P:
#         j = P.index(1)
#         score += n-j + G[j]
#         P[j] = 0
#         if j == k:
#             k += 1
#     else:
#         score += n-k
#         P[k] -= 1
#     print(P,G,score,count,k)
# print(count)

Submission status: Accepted

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

def main():
    D, G = map(int, readline().rstrip().split())
    G //= 100
    PC = [tuple(map(int, readline().rstrip().split())) for _ in range(D)]
    ans = 10 ** 4
    for i in range(2**D):
        b = bin(i)[2:].zfill(D)
        score = 0
        cost = 0
        for i, e in enumerate(b):
            if e == '1':
                score += PC[i][0] * (i+1) + PC[i][1] // 100
                cost += PC[i][0]
        
        if '0' in b:
            m = D - b[::-1].index('0') - 1
            for _ in range(PC[m][0]-1):
                if score >= G:
                    break
                score += m + 1
                cost += 1
        
        if score >= G:
            ans = min(ans, cost)
    
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import heapq as hq
d,g=map(int,input().split())
Q=[]
for i in range(d):
    p,c=map(int,input().split())
    Q.append([p,c])
    
ans=10000
for i in range(2**d):
    #print(bin(i))
    p=0 #取得ポイント
    cnt=0 #問題数
    R=[] #余った問題の点数と個数
    hq.heapify(R)
    for j in range(d):
        a=(j+1)*100
        if i>>j&1:
            p+=Q[j][0]*a+Q[j][1]
            cnt+=Q[j][0]
        else:
            for k in range(Q[j][0]-1):
                hq.heappush(R,-a)
        #print(p,cnt)
        if p>=g:
            break
    while p<g and R:
        p-=hq.heappop(R)
        cnt+=1
        #print(p,cnt)
    if p>=g:
        ans=min(cnt,ans)
    #print(ans)
print(ans)

Submission status: Accepted

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

p = []
c = []

for i in range(d):
    pi, ci = map(int, input().split())
    p.append(pi)
    c.append(ci)

def two_list(d):
    if d == 1:
        return [[0],[1]]
    else:
        res = []
        prevlist = two_list(d-1)
        for l in prevlist:
            tmp = l + [0]
            res.append(tmp)
            tmp = l + [1]
            res.append(tmp)
        return res

s = []
for i in range(d):
    sump = 100 * (i+1) * p[i] + c[i]
    s.append(sump)

minp = sum(p)

for twolist in two_list(d):
    sumall = 0
    sumnum = 0
    for i in range(d):
        sumall += s[i] * twolist[i]
        sumnum += p[i] * twolist[i]
    if 0 in twolist:
        max0 = d - twolist[::-1].index(0)
    else:
        break
    if sumall >= g:
        minp = min(minp, sumnum)
    elif sumall < g and (g-sumall) < s[max0-1]:
        add = (g-sumall)//(100*max0)
        sumnum += add
        if (g-sumall)%(100*max0) != 0:
            sumnum += 1
        minp = min(minp, sumnum)

print(minp)

Submission status: Accepted

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

def solve(n):
    N = n
    score = 0
    ans = 0
    for i in range(D):
        if N & 1:
            score += (i + 1) * 100 * problems[i][0] + problems[i][1]
            ans += problems[i][0]
        N >>= 1
    if score >= G:
        return ans
    i = D - 1
    while n & 2 ** i and i != -1:
        i -= 1
    if i == -1:
        return 10 ** 8
    cnt = 0
    while score + (i + 1) * 100 * cnt < G:
        cnt += 1
    if cnt >= problems[i][0]:
        return 10 ** 8
    return ans + cnt

MIN = 10 ** 8
for i in range(2 ** D):
    MIN = min(MIN, solve(i))
print(MIN)

Submission status: Accepted

Solution code:
D, G = map(int, input().split())
grid = [[0,0]]#インデックス合わせとく
for i in range(D):
    p,c = map(int, input().split())
    grid.append([p,c])

import itertools
kumi = list(itertools.product([0,1], repeat=D))
anls = []
fans = float('inf')
for item in kumi:
    count = 0
    ans = 0
    k = 0
    score = 0
    for i in item:
        count += 1
        if i == 1:
            score += grid[count][0]*100*count + grid[count][1]
            ans += grid[count][0]
        else:
            k = count

    if G <= score :
        fans = min(fans,ans)
    elif score+(k*100)*(grid[k][0]-1) >= G :
        a = int((G-score)/(k*100))
        if score+a*k*100==G:
            ans += a
        else:
            ans += (a+1)
        fans = min(fans,ans)
if fans != float('inf'):
    fans = int(fans)
print(fans)

Submission status: Accepted

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

complete = []
for i in range(2 ** d):
    temp = [0] * d
    for j in range(d):
        if (i >> j) & 1:
            temp[j] = 1
    complete.append(temp)

ans = 10 ** 9
for i in range(len(complete)):
    score = g
    solved = 0
    for j in range(d):
        zenkan = complete[i][j]
        num = pc[j][0]
        bonus = pc[j][1]
        point = (j + 1) * 100
        if zenkan == 1:
            solved += num
            score -= num * point + bonus

    if score <= 0:
        ans = min(ans, solved)
    else:
        for j in reversed(range(d)):
            zenkan = complete[i][j]
            num = pc[j][0]
            bonus = pc[j][1]
            point = (j + 1) * 100
            if zenkan == 0:
                if score - (num - 1) * point > 0:
                    solved += num - 1
                    score -= (num - 1) * point
                else:
                    if score % point == 0:
                        solved += score // point
                    else:
                        solved += score // point + 1
                    ans = min(ans, solved)
                    break

print(ans)

Submission status: Accepted

Solution code:
D, G = map(int, input().split()) 
S = [[int(x) for x in input().split()]for i in range(D)]
Minimum_can = []
for i in range(2**D):
    binary = str(format(i,'b'))
    binary_zero = binary.zfill(D)
    SUM = 0
    Number = 0
    for j in range(D):
        if binary_zero[j]=='1':
            SUM += S[j][0]*100*(j+1)+S[j][1]
            Number += S[j][0]
    if SUM >= G: Minimum_can.append(Number)        
    elif SUM < G:
        Biggest_0_number = 0
        for k in range(D):
            if binary_zero[D-k-1]=='0':
                Biggest_0_number = D-k-1
                break
        for k in range(S[Biggest_0_number][0]):
            if SUM+100*(Biggest_0_number+1)*(k+1) >= G:
                Minimum_can.append(Number+k+1)
                break 
print(min(Minimum_can))

Submission status: Accepted

Solution code:
d, g = map(int, input().split())
pc = [list(map(int, input().split())) for i in range(d)]
ans = []
def dfs(i, sum, count, residue):
  if i == d:
    if sum < g:
      use = max(residue)
      n = min(pc[use - 1][0], -(-(g - sum)//(use*100)))
      count += n
      sum +=  n*use*100
    if sum >= g:
      ans.append(count)
  else:
    dfs(i + 1, sum, count, residue)
    dfs(i + 1, sum + pc[i][0]*(i + 1)*100 + pc[i][1], count + pc[i][0], residue - {i+1})

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

Submission status: Accepted

Solution code:
from statistics import median
#import collections
#aa = collections.Counter(a) # list to list || .most_common(2)で最大の2個とりだせるお a[0][0]
from fractions import gcd
from itertools import combinations # (string,3) 3回
from collections import deque
from collections import defaultdict
import bisect
#
#    d = m - k[i] - k[j]
#    if kk[bisect.bisect_right(kk,d) - 1] == d:
#
#
#
# pythonで無理なときは、pypyでやると正解するかも！！
#
#

import sys
sys.setrecursionlimit(10000000)
mod = 10**9 + 7

def readInts():
  return list(map(int,input().split()))
def main():
    D,G = readInts()
    P = []
    C = []
    res = float('inf')
    for i in range(D):
        p,c = readInts()
        P.append(p)
        C.append(c)
    # bit全探索
    for bit in range(1 << D):
        SUM = 0
        NUM = 0
        for i in range(D):
            if bit & (1 << i):
                SUM += P[i]*(1+i)*100 + C[i]
                NUM += P[i]
        if SUM >= G:
            res = min(res,NUM)
        else:
            for i in range(D-1,-1,-1):
                if bit & (1 << i):
                    continue
                else:
                    for j in range(P[i]):
                        if SUM >= G:
                            break
                        SUM += 100*(i+1)
                        NUM += 1
            #print(NUM)
            res = min(res,NUM)
    print(res)
if __name__ == '__main__':
  main()

Submission status: Accepted

Solution code:

import itertools

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

icntmin=10*100+1
for j in itertools.product([0,1], repeat=d):
    icnt=0
    gcnt=0
    for i in range(d):
        if j[i]==1:
            icnt+=pc[i][0]
            gcnt+=pc[i][0]*100*(i+1)+pc[i][1]
        else:
            ii=i
            
#    print("1",icnt,gcnt,j)
    if gcnt>=g:
        icntmin=min(icnt,icntmin)
        continue
    else:
        gr=g-gcnt
        k=(gr-1)//(100*(ii+1))+1
        if k<pc[ii][0]:
            icnt+=k
            gcnt+=k*100*(ii+1)
            icntmin=min(icnt,icntmin)
#    print("2",icnt,gcnt,ii,gr,k,j)
        
print(icntmin)