Problem: 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?

Submission attempts (in order):
D, G = map(int, input().split())

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

def Calc(score, num):
    temp = list(filter(lambda x: x[1] < num+1, score))
    if temp == []:
        return score[-1][0] * num
    else:
        cand = []
        if len(score) == 1:
            cand.append(temp[0][0]*temp[0][1] + temp[0][2])
        else:
            copy_score = score.copy()
            for t in temp:
                temp_score = score.copy()
                del temp_score[temp_score.index(t)]
                del copy_score[copy_score.index(t)]
                cand.append(t[0]*t[1] + t[2] + Calc(temp_score, num - t[1]))
            if len(copy_score) > 0:
                cand.append(copy_score[-1][0] * num)
        return max(cand)

a, b = 1, q_sum+1
while (b-a) > 1:
    print(a, b)
    if Calc(Score, (b+a) // 2) >= G:
        b = (b+a) // 2
    else:
        a = (b+a) // 2
if Calc(Score, a) >= G:
    print(a)
else:
    print(b)


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

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

def Calc(score, num):
    temp = list(filter(lambda x: x[1] < num+1, score))
    if temp == []:
        return score[-1][0] * num
    else:
        cand = []
        if len(score) == 1:
            cand.append(temp[0][0]*temp[0][1] + temp[0][2])
        else:
            copy_score = score.copy()
            for t in temp:
                temp_score = score.copy()
                del temp_score[temp_score.index(t)]
                del copy_score[copy_score.index(t)]
                cand.append(t[0]*t[1] + t[2] + Calc(temp_score, num - t[1]))
            if len(copy_score) > 0:
                cand.append(copy_score[-1][0] * num)
        return max(cand)

a, b = 1, q_sum+1
while (b-a) > 2:
    print(a,b)
    if Calc(Score, (b+a) // 2) >= G:
        b = (b+a) // 2
    else:
        a = (b+a) // 2
if Calc(Score, a) >= G:
    print(a)
else:
    print(b)


# -*- coding: utf-8 -*-
from sys import stdin
import math

s_in = lambda: stdin.readline()[:-1] 
d_in = lambda: int(stdin.readline()) # N = d_in()
ds_in = lambda: list(map(int, stdin.readline().split())) # List = ds_in()

D, G = ds_in()

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

INF = 10**10

search = []
def SearchMin(search, idx):
    if idx == D:
        score = 0
        num = 0
        res = []
        maxprob = [0, 0, 0]
        for s, i in zip(Score, search):
            num += s[1] * i
            score += (s[0] * s[1] + s[2]) * i
            if i == 0 and s[0] > maxprob[0]:
                maxprob = s.copy()
        if (G > score) and (math.ceil((G - score) / maxprob[0]) <= maxprob[1]):
            return num + max(0, math.ceil((G - score) / maxprob[0]))
        elif G <= score:
            return num
        else:
            return INF

    else:
        s0 = search.copy()
        s0.append(0)
        s1 = search.copy()
        s1.append(1)
        idx += 1
        ans0 = SearchMin(s0, idx)
        ans1 = SearchMin(s1, idx)
        return min(ans0, ans1)

print(SearchMin(search, 0))


Verdicts: Wrong Answer

Wrong Answer

Accepted