Jellyfish and Undertale (Codeforces 1875A)
Tags: Greedy, brute force

Flowey has planted a bomb in Snowdin!The bomb has a timer that is initially set to $$$b$$$. Every second, the timer will decrease by $$$1$$$. When the timer reaches $$$0$$$, the bomb will explode! To give the residents of Snowdin enough time to evacuate, you will need to delay the bomb from exploding for as long as possible.You have $$$n$$$ tools. Each tool can only be used at most once. If you use the $$$i$$$-th tool, the timer will increase by $$$x_i$$$. However, if the timer is changed to an integer larger than $$$a$$$, the timer will be set to $$$a$$$ due to a bug.More specifically, the following events will happen every second in the following order:  You will choose some (possibly none) of your tools that have not been used before. If you choose the $$$i$$$-th tool, and the bomb's timer is currently set to $$$c$$$, the timer will be changed to $$$\min(c + x_i, a)$$$.  The timer decreases by $$$1$$$.  If the timer reaches $$$0$$$, the bomb explodes. Jellyfish now wants to know the maximum time in seconds until the bomb explodes if the tools are used optimally.

Input: Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \leq t \leq 2000$$$). The description of the test cases follows.The first line of each test case contains three integers $$$a$$$, $$$b$$$ and $$$n$$$ ($$$1 \leq b \leq a \leq 10^9$$$, $$$1 \leq n \leq 100$$$) — the maximum value of the bomb's timer, the initial value of the timer of the bomb and the number of tools.The second line of each test contains $$$n$$$ integers $$$x_1, x_2, \dots, x_n$$$ ($$$1 \leq x_i \leq 10^9$$$) — the number the timer can increase by using the $$$i$$$-th tool.Note that the sum of $$$n$$$ over all test cases is not bounded.

Output: For each test case, output a single integer — the maximum time in seconds until the bomb explodes.

Note: Let $$$c$$$ denote the value of the bomb's timer. In the first test case:  Second $$$1$$$: choose tool $$$1$$$ and $$$2$$$ at this second, then $$$c=5$$$; the timer decreases by $$$1$$$, then $$$c=4$$$.  Second $$$2$$$: the timer decreases by $$$1$$$, then $$$c=3$$$.  Second $$$3$$$: the timer decreases by $$$1$$$, then $$$c=2$$$.  Second $$$4$$$: the timer decreases by $$$1$$$, then $$$c=1$$$.  Second $$$5$$$: choose tool $$$3$$$, then $$$c=5$$$; the timer decreases by $$$1$$$, then $$$c=4$$$.  Second $$$6$$$: the timer decreases by $$$1$$$, then $$$c=3$$$.  Second $$$7$$$: the timer decreases by $$$1$$$, then $$$c=2$$$.  Second $$$8$$$: the timer decreases by $$$1$$$, then $$$c=1$$$.  Second $$$9$$$: the timer decreases by $$$1$$$, then $$$c=0$$$. The bomb explodes. It can be proved that there is no way to use the tools such that the bomb explodes after more than $$$9$$$ seconds.

Sample Inputs:
2
5 3 3
1 1 7
7 1 5
1 2 5 6 8

Sample Outputs:
9
21

Solution (Python):
import sys
sys.setrecursionlimit(1000000000)

def solve(a, b, n, x):
    res = b
    for i in x:
        if i < a:
            res += i
        else:
            res += a - 1
    return res
t = int(input())
for _ in range(t):
    (a, b, n) = map(int, input().split())
    x = list(map(int, input().split()))
    res2 = solve(a, b, n, x)
    print(res2)

Solution (Python):
def solution(ceil, current, tools):
    if ceil == 1:
        return 1
    ceil -= 1
    tools = [ceil if tool > ceil else tool for tool in tools]
    return sum(tools) + current
for x in range(int(input())):
    (ceil, current, n) = [int(val) for val in input().split()]
    tools = [int(val) for val in input().split()]
    print(solution(ceil, current, tools))

Solution (Python):
def solve():
    (a, b, n) = map(int, input().split())
    l = list(map(int, input().split()))
    for i in l:
        if i >= a:
            b += a - 1
        else:
            b += i
    print(b)
for _ in range(int(input())):
    solve()