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())
p = []
c = []
for _ in range(d):
    _p, _c = map(int, input().split())
    p.append(_p)
    c.append(_c)

res = 0
count = 0
ans_list = []

def dfs(i, p, c, res, count):
    if i == 0:
        if res >= g:
            ans_list.append(count)
    else:
        for j in reversed(range(p[i - 1] + 1)):
            _count = count + j
            _res = res + 100 * j * i
            if j == p[i - 1]:
                _res += c[i - 1]
            if _res <= g:
                dfs(i - 1, p, c, _res, _count)
                break
            else:
                dfs(i - 1, p, c, _res, _count)

dfs(d, p, c, res, count)
print(min(ans_list))

d, g = map(int, input().split())
p = []
c = []
for _ in range(d):
    _p, _c = map(int, input().split())
    p.append(_p)
    c.append(_c)

res = 0
count = 0
ans_list = []

def dfs(i, p, c, res, count):
    if i == 0:
        if res >= g:
            ans_list.append(count)
    else:
        for j in reversed(range(p[i - 1] + 1)):
            _count = count + j
            _res = res + 100 * j * i
            if j == p[i - 1]:
                _res += c[i - 1]
            if res <= g:
                dfs(i - 1, p, c, _res, _count)
                break

dfs(d, p, c, res, count)
print(min(ans_list))

p = []
c = []
d, g = map(int, input().split())
for _ in range(d):
    _p, _c = map(int, input().split())
    p.append(_p)
    c.append(_c)

ans_list = []

def dfs(i, p, c, res, count):
    if i == 0:
        if res >= g:
            ans_list.append(count)
    else:
        for j in range(p[i - 1] + 1):
            _count = count + j
            _res = res + 100 * j * i
            if j == p[i - 1]:
                _res += c[i - 1]
            dfs(i - 1, p, c, _res, _count)

dfs(d, p, c, res, count)
print(min(ans_list))

d, g = map(int, input().split())
p = []
c = []
for _ in range(d):
    _p, _c = map(int, input().split())
    p.append(_p)
    c.append(_c)

ans_list = []

def dfs(i, p, c, res, count):
    if i == 0:
        if res >= g:
            ans_list.append(count)
    else:
        for j in range(p[i - 1] + 1):
            _count = count + j
            _res = res + 100 * j * i
            if j == p[i - 1]:
                _res += c[i - 1]
            dfs(i - 1, p, c, _res, _count)

dfs(d, p, c, res, count)
print(min(ans_list))

import numpy as np
d, g = map(int, input().split())
p = []
c = []
for _ in range(d):
    _p, _c = map(int, input().split())
    p.append(_p)
    c.append(_c)

s = np.arange(1, d + 1) * 100
p = np.array(p)

ans_list = []

bool_list = [False] * d

state_list = []

def dfs(i, n, bool_list):
    bool_list = bool_list.copy()
    if i == n:
        state_list.append(bool_list)
    else:
        dfs(i + 1, n, bool_list)
        bool_list[i] = True
        dfs(i + 1, n, bool_list)

dfs(0, d, bool_list)

for state in state_list:
    if np.dot(s * p, state) + np.dot(c, state) >= g:
        ans_list.append(np.dot(p, state))
    else:
        score = max(s * np.array([not i for i in state]))
        for j in range(1, p[score//100 - 1] + 1):
            if np.dot(s * p, state) + np.dot(c, state) + score * j >= g:
                ans_list.append(np.dot(p, state) + j)

print(min(ans_list))

Verdicts: Wrong Answer

Runtime Error

Runtime Error

Runtime Error

Accepted