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):
import math as m
from fractions import gcd
D,G = map(int,input().split())
info = [list(map(int,input().split())) for i in range(D)]
cm = 1
for p,c in info:
    cm *= p
L = []
for i in range(1,D+1):
    p = info[i-1][0]
    c = info[i-1][1]
    L.append([cm*100*i + c, i, p, c])
goal = G
count = 0

L.sort()



for i in range(D-1,-1,-1):
    iscore = 100 * L[i][1] * L[i][2] + L[i][3]
    if goal - iscore >= 0:
        goal -= iscore
        count += L[i][2]
        if goal == 0:
            break



    elif goal - iscore < 0:
        adopt = 100
        for k in range(i,-1,-1):
            score = 100 * L[k][1] * L[k][2] + L[k][3]
            if goal - score <= 0:
                j = min(m.ceil(goal/(100 * L[k][1])),L[k][2])
                if j < adopt:
                    adopt = j
        count += adopt
        break
print(count)

import math as m
from fractions import gcd
D,G = map(int,input().split())
info = [list(map(int,input().split())) for i in range(D)]
a = info[0][0]
L = []
for i in range(1,D):
    b = info[i][0]
    lcm = (a * b) // gcd(a,b)
    a = lcm
for i in range(1,D+1):
    p = info[i-1][0]
    c = info[i-1][1]
    L.append([lcm*100*i + c, i, p, c])
goal = G
count = 0

L.sort()



for i in range(D-1,-1,-1):
    iscore = 100 * L[i][1] * L[i][2] + L[i][3]
    if goal - iscore >= 0:
        goal -= iscore
        count += L[i][2]
        if goal == 0:
            break



    elif goal - iscore < 0:
        adopt = 100
        for k in range(i,-1,-1):
            score = 100 * L[k][1] * L[k][2] + L[k][3]
            if goal - score <= 0:
                j = min(m.ceil(goal/(100 * L[k][1])),L[k][2])
                if j < adopt:
                    adopt = j
        count += adopt
        break
print(count)

import math as m
D,G = map(int, input().split())
info = [list(map(int, input().split())) for i in range(D)]
def bfs(list_hoge=[[0,[]]],depth=0):
    queue = []
    for e in list_hoge:
        for b in [0,1]:
            if b == 0:
                score = e[0]
                copy = e[1][:]
                queue.append([score,copy])
            elif b == 1:
                score = e[0] + 100*(depth+1)*info[depth][0] + info[depth][1]
                copy = e[1][:]
                copy.append(depth)
                queue.append([score,copy])
    list_hoge = queue[:]
    if depth == len(info)-1:
        return list_hoge
    return bfs(list_hoge,depth+1)
res = bfs()
ans = float("inf")
for e in res:
    solved = 0
    for i in range(len(e[1])):
        solved += info[e[1][i]][0]
    print(solved)
    if e[0] >= G:
        if solved < ans:
            ans = solved
        continue
    for i in range(D-1,-1,-1):
        if not i in e[1]:
            nec = G-e[0]
            haiten = 100*(i+1)
            add_solve = m.ceil(nec/haiten)
            total_solved = solved + m.ceil(nec/haiten)
            if add_solve >= info[i][0]:
                break
            if total_solved < ans:
                ans = total_solved
print(ans)

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

cs = [100*(i+1)*p + c for i, (p, c) in enumerate(pc)]
ans = float("inf")

for i in range(1<<D):
    flag = [False] * D
    score = 0
    num = 0
    for j in range(D):
        
        if (i >> j) & 1:
            flag[j] = True
            score += cs[j]
            num += pc[j][0]

    if score >= G:
        ans = min(ans, num)
        continue

    last = -1
    for j in range(D)[::-1]:
        if not flag[j]:
            last = j
            break

    for _ in range(pc[j][0]-1):
        score += 100*(j+1)
        num += 1
        if score >= G:
            ans = min(ans, num)
            break

print(ans)

Verdicts: Wrong Answer

Runtime Error

Wrong Answer

Accepted