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: Wrong Answer

Solution code:
import itertools
d,c=map(int, input().split())
p=[list(map(int, input().split())) for i in range(d)]
al=list(itertools.product(range(2),repeat=d))
ans=1000
for i in al:
    count=0
    score=0
    if 0 not in i:continue
    last0=d-list(reversed(i)).index(0)-1
    for j in range(d):
        count+=i[j]*p[j][0]
        score+=i[j]*p[j][1]+i[j]*p[j][0]*(j+1)*100
    #print(count,score,last0,i)
    if score>=c:ans=min(ans,count)
    elif (c-score)/((last0+1)*100)<p[last0][0]:ans=min(ans,count+(c-score+last0*100)//((last0+1)*100))
print(ans)

Submission status: Wrong Answer

Solution code:
d, g = map(int, raw_input().split())
problems = []
bonus = []
for i in range(0, d):
	p, c = map(int, raw_input().split())
	problems.append(p)
	bonus.append(c)
status = [[0, g, problems]]
min = 10000
while status != []:
	tmp = status.pop(0)
	for i in range(0, d):
		if tmp[2][i] != 0:
			flag = True
			nproblems = []
			for j in range(0, d):
				if i == j: nproblems.append(0)
				else: nproblems.append(tmp[2][j])
			sum = 0
			for j in range(0, tmp[2][i]):
				sum = sum + 100 * (i+1)
				if j == tmp[2][i] - 1:
					sum = sum + bonus[i]
				if tmp[1] <= sum:
					flag = False
					if tmp[0] + j + 1 < min:
						min = tmp[0] + j + 1
					break
			if flag:
				status.append([tmp[0]+tmp[2][i], g-sum, nproblems])
print min

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
import itertools

D, G = map(int, input().split())

pi = []
ci = []
score_i_c = []
score_i_h = []
for i in range(D):
    p_t, c_t = map(int, input().split())
    pi.append(p_t)
    ci.append(c_t)
    tmp = p_t * 100 * (i + 1) + c_t
    score_i_c.append((i,tmp,p_t))
    tmp = (p_t - 1) * 100 * (i + 1)
    score_i_h.append((i,tmp,p_t))

# 完全に解かなくても行ける場合
step1_list = []
for i,score,num in score_i_h:
    if score >= G:
        step1_list.append((i,score,num))

ans_list = []
if len(step1_list) > 0:
    min_i , _, _ = step1_list[-1]
    for i , score, num in step1_list:
        tmp_score = 0
        tmp_num = 0
        for i in range(pi[min_i]):
            if tmp_score >= G:
                break
            else:
                tmp_score += (min_i+1) * 100
                tmp_num  += 1
        ans_list.append(tmp_num)

#完全に解くケース
step1_list = []
for i in range(D):
    tmp = itertools.combinations(score_i_c, i+1)
    step1_list.extend(list(tmp))

# 合計がGを超える組み合わせを抽出
sum_list = []
for l in step1_list:
    numbers = []
    sum_score = 0
    sum_num = 0
    for i,score,num in l:
        numbers.append(i)
        sum_score += score
        sum_num += num

    if sum_score >= G:
        sum_list.append((numbers,sum_score,sum_num))
#
# print(step1_list)
# print(sum_list)

min_numbers = []
min_score = 0
min_num = 10000
for i,score,num in sum_list:
    if num < min_num:
        min_numbers = i
        min_score = score
        min_num = num

# print(min_numbers,min_score,min_num)

# min_i = min_numbers[-1]
for min_i in min_numbers:
    tmp_score = min_score - score_i_c[min_i][1]
    tmp_num = min_num - score_i_c[min_i][2]

    for i in range(pi[min_i]):
        if tmp_score >= G:
            break
        else:
            tmp_score += (min_i+1) * 100
            tmp_num  += 1

    ans_list.append(tmp_num)

# print(ans_list)

print(min(ans_list))

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
import itertools

D, G = map(int, input().split())

pi = []
ci = []
score_i_c = []
score_i_h = []
for i in range(D):
    p_t, c_t = map(int, input().split())
    pi.append(p_t)
    ci.append(c_t)
    tmp = p_t * 100 * (i + 1) + c_t
    score_i_c.append((i,tmp,p_t))
    tmp = (p_t - 1) * 100 * (i + 1)
    score_i_h.append((i,tmp,p_t))

# 完全に解かなくても行ける場合
step1_list = []
for i,score,num in score_i_h:
    if score >= G:
        step1_list.append((i,score,num))

sum_list = []
if len(step1_list) > 0:
    min_i , _, _ = step1_list[-1]
    for i , score, num in step1_list:
        tmp_score = 0
        tmp_num = 0
        for i in range(pi[min_i]):
            if tmp_score >= G:
                break
            else:
                tmp_score += (min_i+1) * 100
                tmp_num  += 1
        sum_list.append(tmp_num)
    print(min(sum_list))
    exit()

#完全に解くケース
step1_list = []
for i in range(D):
    tmp = itertools.combinations(score_i_c, i+1)
    step1_list.extend(list(tmp))

# 合計がGを超える組み合わせを抽出
sum_list = []
for l in step1_list:
    numbers = []
    sum_score = 0
    sum_num = 0
    for i,score,num in l:
        numbers.append(i)
        sum_score += score
        sum_num += num

    if sum_score >= G:
        sum_list.append((numbers,sum_score,sum_num))
#
# print(step1_list)
# print(sum_list)

min_numbers = []
min_score = 0
min_num = 10000
for i,score,num in sum_list:
    if num < min_num:
        min_numbers = i
        min_score = score
        min_num = num

# print(min_numbers,min_score,min_num)

ans_list = []
# min_i = min_numbers[-1]
for min_i in min_numbers:
    tmp_score = min_score - score_i_c[min_i][1]
    tmp_num = min_num - score_i_c[min_i][2]

    for i in range(pi[min_i]):
        if tmp_score >= G:
            break
        else:
            tmp_score += (min_i+1) * 100
            tmp_num  += 1

    ans_list.append(tmp_num)

# print(ans_list)

print(min(ans_list))

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
import itertools

D, G = map(int, input().split())

pi = []
ci = []
score_i_c = []
score_i_h = []
for i in range(D):
    p_t, c_t = map(int, input().split())
    pi.append(p_t)
    ci.append(c_t)
    tmp = p_t * 100 * (i + 1) + c_t
    score_i_c.append((i,tmp,p_t))
    tmp = (p_t - 1) * 100 * (i + 1)
    score_i_h.append((i,tmp,p_t))

# 完全に解かなくても行ける場合
step1_list = []
for i,score,num in score_i_h:
    if score >= G:
        step1_list.append((i,score,num))

if len(step1_list) > 0:
    min_i , _, _ = step1_list[-1]

    tmp_score = 0
    tmp_num = 0
    for i in range(pi[min_i]):
        if tmp_score >= G:
            break
        else:
            tmp_score += (min_i+1) * 100
            tmp_num  += 1

    print(tmp_num)
    exit()

#完全に解くケース
step1_list = []
for i in range(D):
    tmp = itertools.combinations(score_i_c, i+1)
    step1_list.extend(list(tmp))

sum_list = []
for l in step1_list:
    numbers = []
    sum_score = 0
    sum_num = 0
    for i,score,num in l:
        numbers.append(i)
        sum_score += score
        sum_num += num

    if sum_score >= G:
        sum_list.append((numbers,sum_score,sum_num))
#
# print(step1_list)
# print(sum_list)

min_numbers = []
min_score = 0
min_num = 10000
for i,score,num in sum_list:
    if num < min_num:
        min_numbers = i
        min_score = score
        min_num = num

# print(min_numbers,min_score,min_num)

ans_list = []
# min_i = min_numbers[-1]
for min_i in min_numbers:
    tmp_score = min_score - score_i_c[min_i][1]
    tmp_num = min_num - score_i_c[min_i][2]

    for i in range(pi[min_i]):
        if tmp_score >= G:
            break
        else:
            tmp_score += (min_i+1) * 100
            tmp_num  += 1

    ans_list.append(tmp_num)

# print(ans_list)

print(min(ans_list))

Submission status: Wrong Answer

Solution code:
import math, string, fractions, heapq, re, array, bisect, sys, random, time, copy
import itertools as it
import collections as cl
import functools as ft
import numpy as np

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()


def main(d, g, p, c):
    counts = []
    for choice in it.product(*[[0, 1]]*10):
        count = sum([p_ * flg for p_, flg in zip(p, choice)])
        total = sum([p_ * (100*i) for p_, i in zip(p, range(1, d+1))])
        if total >= g:
            counts.append(count)
        elif choice != [1] * d:
            i = d - choice[::-1].index
            part_count = (g - total) // (100 * i) + 1
            if part_count > 0:
                counts.append(count + part_count)

    return min(counts)


if __name__ == "__main__":
    d, g = LI()
    p = []
    c = []
    for _ in range(d):
        p_, c_ = LI()
        p.append(p_)
        c.append(c_)

    # print(main(d, g, p, c))
    counts = []
    for choice in it.product(*[[0, 1]]*d):
        count = sum([p_ * flg for p_, flg in zip(p, choice)])
        total = sum([(p_ * 100*i + c_) * flg for p_, i, flg, c_ in zip(p, range(1, d+1), choice, c)])
        # print(choice, count, total)
        if total >= g:
            counts.append(count)
        elif choice != [1] * d:
            i = d - choice[::-1].index(0)
            # print(choice, i)
            part_count = int((g - total) / (100*i))
            if part_count < p[i-1]:
                counts.append(count + part_count)
    print(min(counts))

Submission status: Wrong Answer

Solution code:
import math, string, fractions, heapq, re, array, bisect, sys, random, time, copy
import itertools as it
import collections as cl
import functools as ft
import numpy as np

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()


def main(d, g, p, c):
    counts = []
    for choice in it.product(*[[0, 1]]*10):
        count = sum([p_ * flg for p_, flg in zip(p, choice)])
        total = sum([p_ * (100*i) for p_, i in zip(p, range(1, d+1))])
        if total >= g:
            counts.append(count)
        elif choice != [1] * d:
            i = d - choice[::-1].index
            part_count = (g - total) // (100 * i) + 1
            if part_count > 0:
                counts.append(count + part_count)

    return min(counts)


if __name__ == "__main__":
    d, g = LI()
    p = []
    c = []
    for _ in range(d):
        p_, c_ = LI()
        p.append(p_)
        c.append(c_)

    # print(main(d, g, p, c))
    counts = []
    for choice in it.product(*[[0, 1]]*d):
        count = sum([p_ * flg for p_, flg in zip(p, choice)])
        total = sum([(p_ * 100*i + c_) * flg for p_, i, flg, c_ in zip(p, range(1, d+1), choice, c)])
        # print(choice, count, total)
        if total >= g:
            counts.append(count)
        elif choice != [1] * d:
            i = d - choice[::-1].index(0)
            # print(choice, i)
            part_count = (g - total) // (100*i)
            if part_count < p[i-1]:
                counts.append(count + part_count)
    print(min(counts))

Submission status: Wrong Answer

Solution code:
import math

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)
compl = [100 * (i+1) * p[i] + c[i] for i in range(d)]

ans = 1e9
for i in range(2 ** d):
    score = num = 0
    for j in range(d):
        if (i >> j) & 1:
            score += compl[j] 
            num += p[j] 
        else:
            # index of highest rest valuable p.
            rest_idx = j
    if score < g:
        need = (g - score) // (100 * (rest_idx + 1))
        if need >= p[rest_idx]:
            continue
        num += need
    ans = min(ans, num)
print(ans)

Submission status: Wrong Answer

Solution code:
# encoding: utf-8
import itertools

P_MAX = 100

num_and_pnt = lambda x: [int(x[0]), int(x[1]) // 100]

D, G = num_and_pnt(input().split())

# [flag, index, pi, ci]
pc = [[1, i] + num_and_pnt(input().split()) for i in range(D)]

cnt = 0

# find min. # of completed points
G_tmp = 0
for i, x in enumerate(sorted(pc, key=lambda x: x[1] + x[3] / x[2])):
    if G_tmp < G: G_tmp += (x[1] + 1) * x[2] + x[3]
    else: break
p_num = i

# search ans.
mincnt = 100 * 10
skip = (-1,)
pc.sort(key=lambda x: -(x[1] + x[3] / x[2])) # to find local solution earlier
# print("#", pc)
for order in itertools.permutations(range(D), p_num):
    pc_tmp = list(pc)
    # skip
    if all([a == b for a, b in zip(skip, order)]): continue
    # fill completed points
    # print("#", order)
    cnt = 0
    G_tmp = 0
    for i, idx in enumerate(order):
        x = pc_tmp[idx]
        G_i = (x[1] + 1) * x[2] + x[3]
        if cnt > mincnt: break
        elif G_tmp + G_i < G:
            cnt += x[2]
            G_tmp += G_i
            pc_tmp[idx][0] = 0
            # print("##", cnt, G_tmp)
        else: break
    # record for skip
    if i < p_num - 1: skip = order[:i]
    # escape
    if cnt > mincnt: continue
    # evaluate cnt
    cnt_last = 100
    for x in filter(lambda x: x[0] > 0, pc_tmp):
        cnt_last_tmp = x[2]
        G_last = (x[1] + 1) * x[2] + x[3]
        if G_tmp + G_last < G: continue
        for i in range(x[2]):
            if G_tmp + G_last < G:
                if i == 0: continue
                cnt_last_tmp += 1
                break
            else:
                cnt_last_tmp -= 1
                G_last = (x[1] + 1) * cnt_last_tmp
        # print("##", x, cnt_last_tmp)
        if cnt_last_tmp < cnt_last: cnt_last = cnt_last_tmp
    # loop end
    # print("#", order, cnt, cnt_last)
    if cnt + cnt_last < mincnt: mincnt = cnt + cnt_last

print(mincnt)

Submission status: Wrong Answer

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

arr = []

for i in range(d):
	arr.append(map(int,raw_input().split()))


ans = float("inf")
for i in range(2**d):
	bit = (bin(i)[2:]).zfill(d)

	count = 0
	points = 0

	rest = []

	for j in range(d):
		if bit[j] == "1":
			count += arr[j][0]
			points += arr[j][0] * (j+1) * 100 + arr[j][1]
		
		else :
			for k in range(arr[j][0]-1) :
				rest.append((j+1)*100)


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

	else :
		rest.reverse()
		i = 0
		while i < len(rest) and points + rest[i] <= g:
			points += rest[i]
			i += 1

		if i == len(rest):
			next

		ans = min(ans,count + i)


print ans

Submission status: Wrong Answer

Solution code:
D, G = map(int, input().split())
S = [[0] for i in range(D + 1)]
B = [[0] for i in range(D + 1)]
sumP = 0
for i in range(D):
  p, c = map(int, input().split())
  S[i + 1] += [0] * (len(S[i]) + p - 1)
  B[i + 1] += [100 * (x + 1) for x in range(p)]
  B[i + 1][-1] += c
for i in range(1, D + 1):
  for j in range(1, len(S[i])):
    for k in range(max(j - len(S[i - 1]) + 1, 0), min(len(B[i]), j + 1)):
      S[i][j] = max(B[i][k] + S[i - 1][j - k], S[i][j])
for i, s in enumerate(S[D]):
  if s >= G:
    print(i)
    break

Submission status: Wrong Answer

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
mod = 10**9+7
dd = [(-1,0),(0,1),(1,0),(0,-1)]
ddn = [(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)


def main():
    d,g = LI()
    p = []
    c = []
    for _ in range(d):
        t = LI()
        p.append(t[0])
        c.append(t[1])

    r = inf
    for i in range(2**d):
        tg = 0
        tr = 0
        for j in range(d):
            if 2**j & i:
                tg += c[j]
                tg += (j+1) * p[j] * 100
                tr += p[j]
        for j in range(d-1,-1,-1):
            if tg >= g:
                break
            if 2**j & i:
                continue
            ng = g - tg
            k = ng // ((j+1) * 100)
            if p[j] >= k:
                tr += k
                break
            tr += p[j]
            tg += p[j] * (j+1) * 100
        if r > tr:
            r = tr
    return r


print(main())

Submission status: Wrong Answer

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

print(PC)

# コンプリートしたときの点数
comp = [100*(i+1)*PC[i][0] + PC[i][1] for i in range(D)]

# bit全探索
# 配点が高い位置からコンプリートする問題を決め打ち
ans = sum([PC[i][0] for i in range(D)])
for bit in range(1<<D):
    
    
    point = 0
    prob = 0
    
    print("init",bit,ans,prob,point)
    
    for j in range(D-1, -1, -1):
        if bit & (1<<j):
            point += comp[j]
            prob += PC[j][0]

    # コンプだけでG以上になったなら次へ
    if point >= G:
        ans = min(ans,prob)
        continue
    
    # そうでないなら高い位置から貪欲
    else:
        for j in range(D-1, -1, -1):
            if bit & (1<<j):
                continue
            else:
                if point + 100*(j+1)*(PC[j][0]-1) < G:
                    point += 100*(j+1)*(PC[j][0]-1)
                    prob += (PC[j][0]-1)
                else:
                    temp = (G-point)//(100*(j+1)) + bool((G-point)%(100*(j+1)))
                    point += 100*(j+1)*temp
                    prob += temp
        
            if point >= G:
                ans = min(ans,prob)
                break
            

print(ans)

Submission status: Wrong Answer

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

arr = []

for i in range(d):
	arr.append(map(int,raw_input().split()))


ans = float("inf")
for i in range(2**d):
	bit = (bin(i)[2:]).zfill(d)

	count = 0
	points = 0

	rest = []

	for j in range(d):
		if bit[j] == "1":
			count += arr[j][0]
			points += arr[j][0] * (j+1) * 100 + arr[j][1]
		
		else :
			for k in range(arr[j][0]) :
				rest.append((j+1)*100)


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

	else :
		rest.reverse()
		i = 0
		while i < len(rest) and points + rest[i] <= g:
			points += rest[i]
			i += 1

		if i == len(rest):
			next

		ans = min(ans,count + i)


print ans

Submission status: Wrong Answer

Solution code:
import itertools
D,G=map(int,input().split())
p=[0 for i in range(D)]
c=[0 for i in range(D)]
for i in range(D):
    p[i],c[i]=map(int,input().split())

S=list(itertools.product(range(2),repeat=D))
ans=sum(p)
for seq in S:
    score=0
    prove=0
    for i in range(D):
        if seq[i]==1:
            score+=(p[i]*100*(i+1)+c[i])
            prove+=p[i]
    if score>G:
        if ans>prove:
            ans=prove
        continue
    j=-1
    for i in range(D):
        if seq[i]==0:
            j=i
    for k in range(p[j]):
        prove+=1
        score+=100*(j+1)
        if G<=score:
            break
    if G>score:
        continue
    if ans>prove:
        ans=prove
print(ans)

Submission status: Wrong Answer

Solution code:
from itertools import product
d,g = (int(i) for i in input().split())
p = [[int(i) for i in input().split()] for i in range(d)]
q,ans = [],10000
for i in range(d): q.append(p[i][0]*(i+1)*100+p[i][1]) 
for i in product(range(2), repeat=d):
	m,n,x = 0,0,[]
	for j in range(d):
		if i[j]==1: m,n = m+q[j],n+p[j][0]
		else: x.append(j)
	if m>=g: ans = min(ans,n)
	else:
		for k in x:
			num = (g-m+99)//((k+1)*100)
			if num<p[k][0]: ans = min(ans,n+num)
print(ans)

Submission status: Wrong Answer

Solution code:
from itertools import product
d,g = (int(i) for i in input().split())
p = [[int(i) for i in input().split()] for i in range(d)]
q,ans = [],1001
for i in range(d): q.append(p[i][0]*(i+1)*100+p[i][1]) 
for i in product(range(2), repeat=d):
	m,n,x = 0,0,[]
	for j in range(d):
		if i[j]==1: m,n = m+q[j],n+p[j][0]
		else: x.append(j)
	if m>=g: ans = min(ans,n)
	else:
		for k in x:
			num = (g-m+99)//((k+1)*100)
			if num<p[k][0]: ans = min(ans,n+num)
print(ans)

Submission status: Wrong Answer

Solution code:
import math

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

ans = float('inf')

for i in range(1 << D): # bit全探索
    solved = [a for a in range(D)] # 全て解く＝ボーナス点をもらう問題群
    count = 0
    point = 0
    for j in range(D): # 全て解く＝ボーナス点をもらう問題群の点数合計
        if i & (1 << j): # (j + 1) * 100 点の問題を全て解く場合
            count += Problems[j][0]
            point += Problems[j][0] * (j + 1) * 100 + Problems[j][1]
            solved.remove(j) # (j + 1) * 100 点の問題は全て解答済
    if point < G and len(solved) > 0:
        k = max(solved)
        if math.ceil((G - point) / ((k + 1) * 100)) > Problems[k][0] - 1:
            continue
        else:
            count += math.ceil((G - point) // ((k + 1) * 100))
            ans = min(ans, count)
    else:
        ans = min(ans, count)

print(ans)

Submission status: Wrong Answer

Solution code:
import math

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

ans = float('inf')

for i in range(1 << D): # bit全探索
    solved = [a for a in range(D)] # 全て解く＝ボーナス点をもらう問題群
    count = 0
    point = 0
    for j in range(D): # 全て解く＝ボーナス点をもらう問題群の点数合計
        if i & (1 << j): # (j + 1) * 100 点の問題を全て解く場合
            count += Problems[j][0]
            point += Problems[j][0] * (j + 1) * 100 + Problems[j][1]
            solved.remove(j)
    if point < G and len(solved) > 0:
        k = max(solved)
        if math.ceil((G - point) // ((k + 1) * 100)) > Problems[k][0] - 1:
            continue
        else:
            count += math.ceil((G - point) // ((k + 1) * 100))
            ans = min(ans, count)
    else:
        ans = min(ans, count)

print(ans)

Submission status: Wrong Answer

Solution code:
import math

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

ans = float('inf')

for i in range(1 << D): # bit全探索
    solved = [a for a in range(D)] # 全て解く＝ボーナス点をもらう問題群
    count = 0
    point = 0
    for j in range(D): # 全て解く＝ボーナス点をもらう問題群の点数合計
        if i & (1 << j): # (j + 1) * 100 点の問題を全て解く場合
            count += Problems[j][0]
            point = Problems[j][0] * (j + 1) * 100 + Problems[j][1]
            solved.remove(j)
    if point < G and len(solved) > 0:
        k = max(solved)
        if math.ceil((G - point) // ((k + 1) * 100)) > Problems[k][0] - 1:
            continue
        else:
            count += math.ceil((G - point) // ((k + 1) * 100))
            ans = min(ans, count)
    else:
        ans = min(ans, count)

print(ans)

Submission status: Wrong Answer

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

ans = 1000
for X in product(range(2), repeat = D):
    cnt = 0
    com = 0
    K = []
    for i in range(D):
        if X[i] == 1:
            cnt += P[i]
            com += SUM[i]
        else:
            K.append(i)
    if com >= G:
        ans = min(ans, cnt)
    else:
        for k in K:
            need = min((G-com)//(100*(k+1))+1,P[k]-1)
            kcnt = cnt + need
            kcom = com + need*100*(k+1)
            if kcom >= G:
                ans = min(ans,kcnt)
print(ans)

Submission status: Wrong Answer

Solution code:
D,G = list(map(int,input().split()))
L=[]
for i in range(D):
    L.append(list(map(int,input().split())))
for i in range(D):
    L[i].append(L[i][0]*(i+1)*100)
    L[i].append(L[i][2]+L[i][1])
print(L)
answer = 10**4
for bits in range(1<<D):
    point_sum = 0
    n = 0
    j = -1
    for i in range(D):
        if bits & 1<<i:
            point_sum += L[i][3]
            n += L[i][0]
        else:
            j = max(j, i)
    if point_sum >= G:
        answer = min(answer, n)
    elif j >=0 and (point_sum+L[j][2])-(j+1)*100 >= G:
        a = G - point_sum
        b = (j+1)*100
        answer = min(answer, n+int((a+b-1)/b))
    else:
        pass
print(answer)

Submission status: Wrong Answer

Solution code:
import math
from itertools import chain, combinations



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

for _ in range(D):
    p_in, c_in = map(int, input().split())
    p.append(p_in)
    c.append(c_in)

# ボーナスを使う

def powerset(itr):
    s = list(itr)
    return chain.from_iterable(combinations(s, r) for r in range(len(s)+1))


# フルコン時の点数
fullcon = []
for i in range(D):
    score = 100 * (i + 1) * p[i] + c[i]
    fullcon.append(score)


use_flag_itr = range(D)
use_flag_set = powerset(use_flag_itr)

mincount = 100 * 10

for use_flag in use_flag_set:
    fullscore = 0
    fullcount = 0
    for i in use_flag:
        fullcount += p[i]
        fullscore += fullcon[i]

    remain = G - fullscore

    if remain <= 0:
        if mincount > fullcount:
            mincount = fullcount 
        continue



    for i in reversed(range(D)):
        if i in use_flag:
            continue

        score = 100 * (i + 1) 
        if score * p[i] > remain:
            new_count = fullcount +  int(math.floor(remain / score))
            if mincount > new_count:
                mincount = new_count
        break

print(mincount)

Submission status: Wrong Answer

Solution code:
D,G = list(map(int,input().split()))
L=[]
for i in range(D):
    L.append(list(map(int,input().split())))
for i in range(D):
    L[i].append(L[i][0]*(i+1)*100)
    L[i].append(L[i][2]+L[i][1])
answer = 10*12
for bits in range(1<<D):
    point_sum = 0
    n = 0
    j = -1
    for i in range(D):
        if bits & 1<<i:
            point_sum += L[i][3]
            n += L[i][0]
        else:
            j = max(j, i)
    if point_sum >= G:
        answer = min(answer, n)
    elif j >=0 and (point_sum+L[j][2])-(j+1)*100 >= G:
        a = G - point_sum
        b = (j+1)*100
        answer = min(answer, n+int((a+b-1)/b))
    else:
        pass
print(answer)

Submission status: Wrong Answer

Solution code:
D,G = list(map(int,input().split()))
L=[]
for i in range(D):
    L.append(list(map(int,input().split())))
for i in range(D):
    L[i].append(L[i][0]*(i+1)*100)
    L[i].append(L[i][2]+L[i][1])
answer = 10*12
for bits in range(1<<D):
    point_sum = 0
    n = 0
    j = -1
    for i in range(D):
        if bits & 1<<i:
            point_sum += L[i][3]
            n += L[i][0]
        else:
            j = max(j, i)
    if point_sum >= G:
        answer = min(answer, n)
    elif j >=0 and point_sum+L[j][2] >= G:
        a = G - point_sum
        b = (j+1)*100
        answer = min(answer, n+int((a+b-1)/b))
    else:
        pass
print(answer)

Submission status: Wrong Answer

Solution code:
from itertools import product
D, G = map(int, input().split())
l = [tuple(map(int, input().split())) for i in range(D)]
s = [0] * D
ans = float('inf')
for b in product([0,1], repeat=D):
    s = sum([(i+1)*100 * l[i][0] + l[i][1] for i,f in enumerate(b) if f])
    tmp = sum([l[i][0] for i,f in enumerate(b) if f])
    if s < G:
        for i, j in enumerate(reversed(b)):
            if j == 0:
                d = D - i
                k = 0
                if s + 100 * d * (l[d-1][0] - 1 - k) < G:
                    tmp = float('inf')
                    break
                while s + 100 * d * (l[d-1][0] - 1 - k) > G:
                    k += 1
                tmp += l[d-1][0] - k - 1
                break
    ans = min(ans, tmp)
print(ans)

Submission status: Wrong Answer

Solution code:
class Solution:
    def min_test(self):
        n, target = map(int, input().split())
        tests = []
        ncount = 0
        for i in range(n):
            a, b = map(int, input().split())
            tests.append([a, b, (i + 1) * 100])

        while target > 0:


            tests = sorted(tests,
                           key=lambda each: each[2] if each[0] * each[2] > target else (each[0] * each[2] + each[1]) /
                                                                                 each[0])


            a, b, c = tests.pop()
            if a * c > target:
                ncount += target // c

                target -= target // c * c

            else:
                target -= a * c + b
                ncount += a

        return ncount


print(Solution().min_test())

Submission status: Wrong Answer

Solution code:
class Solution:
    def min_test(self):
        n, target = map(int, input().split())
        tests = []
        ncount = 0
        for i in range(n):
            a, b = map(int, input().split())
            tests.append([a, b, (i + 1) * 100])

        while target > 0:

            tests = sorted(tests, key=lambda each: (each[0] * each[2] + each[1]) / each[0] if each[0] * each[
                2] + each[1] <= target else each[1])
     
            a, b, c = tests.pop()
            if a * c < target:
                target -= a * c + b
                ncount += a
            else:
                ncount += target // c
                target -= target // c * c


        return ncount


print(Solution().min_test())