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):
N, G = map(int, input().split())
bonus = []
problems = []
for _ in range(N):
    PI, CI = map(int, input().split())
    problems.append(PI)
    bonus.append(CI)


def make_plan(total_problem, total_score, problems):
    
    
    for i in range(N - 1, -1, -1):
        pi = problems[i]
        si = (i + 1) * 100
        if pi == 0:
            continue
        else:
            if total_score + pi * si >= G:
                
                
                score = total_score
                pn = total_problem
                while score < G:
                    pn += 1
                    score += si
                return score, pn
            else:
                
                min_pn = 10000  
                cand_score = 0
                for j in range(1, pi+1):
                    plus_score = si * j
                    if j == pi:
                        plus_score += bonus[i]
                    problems[i] = 0
                    score, pn = make_plan(total_problem+j, total_score+plus_score, problems)  
                    problems[i] = pi
                    if pn < min_pn:
                        min_pn = pn
                        cand_score = score
                    if total_score + plus_score >= G:
                        break
                return cand_score, min_pn
    else:
        
        return 0, 10000


print(make_plan(0, 0, problems))


N, G = map(int, input().split())
bonus = []
problems = []
for _ in range(N):
    PI, CI = map(int, input().split())
    problems.append(PI)
    bonus.append(CI)


def calc_rest_score():
    total = 0
    for i, pi in enumerate(problems):
        if pi:
            score = (i+1) * 100
            total += score * pi + bonus[i]
    return total


def make_plan(total_problem, total_score):
    
    
    rest_score = calc_rest_score()  
    if total_score + rest_score < G:
        
        return 0, 10000

    
    for i in range(N - 1, -1, -1):
        pi = problems[i]
        si = (i + 1) * 100
        if pi == 0:
            continue
        else:
            if total_score + pi * si >= G:
                
                
                score = total_score
                pn = total_problem
                while score < G:
                    pn += 1
                    score += si
                # print("goal")
                return score, pn
            else:
                
                min_pn = 10000  
                cand_score = 0
                for j in range(pi+1, 0, -1):
                    # print("test", j)
                    plus_score = si * j
                    if j == pi:
                        plus_score += bonus[i]
                    problems[i] = 0
                    score, pn = make_plan(total_problem+j, total_score+plus_score)  
                    problems[i] = pi
                    if pn < min_pn:
                        min_pn = pn
                        cand_score = score
                    if total_score + plus_score >= G:
                        break
                return cand_score, min_pn
    else:
        
        return 0, 10000


print(make_plan(0, 0)[1])


N, G = map(int, input().split())
bonus = []
problems = []
for _ in range(N):
    PI, CI = map(int, input().split())
    problems.append(PI)
    bonus.append(CI)


def calc_rest_score():
    total = 0
    for i, pi in enumerate(problems):
        if pi:
            score = (i+1) * 100
            total += score * pi + bonus[i]
    return total


def make_plan(total_problem, total_score, flag):
    
    if total_score >= G:
        return total_problem

    # print("call ", total_problem, total_score, problems)

    rest_score = calc_rest_score()  
    if total_score + rest_score < G:
        
        return 10000

    for i in range(N - 1, -1, -1):
        pi = problems[i]
        si = (i + 1) * 100
        if pi == 0:
            continue
        else:
            
            problems[i] = 0
            pn1 = make_plan(total_problem + pi,
                            total_score + si * pi + bonus[i],
                            flag)
            problems[i] = pi
            # print("pn1:", pn1)

            
            if not flag:
                
                min_pn = 10000  
                for j in range(pi, -1, -1):  
                    plus_score = si * j
                    if j == pi:
                        plus_score += bonus[i]
                    problems[i] = 0
                    pn = make_plan(total_problem+j,
                                   total_score+plus_score,
                                   True if j != 0 else flag)
                    # print("test", j, pn)
                    problems[i] = pi
                    if pn < min_pn:
                        min_pn = pn
                pn2 = min_pn
            else:
                pn2 = 10000

            return min(pn1, pn2)
    else:
        
        return 10000


print(make_plan(0, 0, False))


Verdicts: Wrong Answer

Wrong Answer

Accepted