310714: CF1875A. Jellyfish and Undertale
Description
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.
InputEach 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.
OutputFor each test case, output a single integer — the maximum time in seconds until the bomb explodes.
ExampleInput2 5 3 3 1 1 7 7 1 5 1 2 5 6 8Output
9 21Note
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.
Output
题目描述了一个关于炸弹倒计时的问题。有一个炸弹，其定时器最初被设置为 $ b $ 秒，每秒钟定时器会减 1，当定时器到达 0 时，炸弹会爆炸。你有 $ n $ 个工具，每个工具最多只能使用一次。使用第 $ i $ 个工具，定时器会增加 $ x_i $。但如果由于一个 bug，定时器被改变为一个大于 $ a $ 的整数，定时器将被设置为 $ a $。具体来说，每秒钟按照以下顺序发生以下事件：
1. 你可以选择一些（也可能不选择）之前没有使用过的工具。如果你选择了第 $ i $ 个工具，并且炸弹的定时器当前设置为 $ c $，定时器将改变为 $ \min(c + x_i, a) $。
2. 定时器减 1。
3. 如果定时器达到 0，炸弹爆炸。
现在Jellyfish想知道如果工具被最优使用，炸弹爆炸前的最大时间（以秒计）。
输入输出数据格式：
输入：
- 第一行包含一个整数 $ t $（$ 1 \leq t \leq 2000 $），表示测试用例的数量。
- 每个测试用例包含三行：
- 第一行包含三个整数 $ a $，$ b $ 和 $ n $（$ 1 \leq b \leq a \leq 10^9 $，$ 1 \leq n \leq 100 $），分别表示炸弹定时器的最大值、炸弹定时器的初始值和工具的数量。
- 第二行包含 $ n $ 个整数 $ x_1, x_2, \dots, x_n $（$ 1 \leq x_i \leq 10^9 $），表示使用第 $ i $ 个工具时定时器可以增加的数值。
输出：
- 对于每个测试用例，输出一个整数，表示炸弹爆炸前的最大时间（以秒计）。题目大意： 题目描述了一个关于炸弹倒计时的问题。有一个炸弹，其定时器最初被设置为 $ b $ 秒，每秒钟定时器会减 1，当定时器到达 0 时，炸弹会爆炸。你有 $ n $ 个工具，每个工具最多只能使用一次。使用第 $ i $ 个工具，定时器会增加 $ x_i $。但如果由于一个 bug，定时器被改变为一个大于 $ a $ 的整数，定时器将被设置为 $ a $。具体来说，每秒钟按照以下顺序发生以下事件： 1. 你可以选择一些（也可能不选择）之前没有使用过的工具。如果你选择了第 $ i $ 个工具，并且炸弹的定时器当前设置为 $ c $，定时器将改变为 $ \min(c + x_i, a) $。 2. 定时器减 1。 3. 如果定时器达到 0，炸弹爆炸。 现在Jellyfish想知道如果工具被最优使用，炸弹爆炸前的最大时间（以秒计）。 输入输出数据格式： 输入： - 第一行包含一个整数 $ t $（$ 1 \leq t \leq 2000 $），表示测试用例的数量。 - 每个测试用例包含三行： - 第一行包含三个整数 $ a $，$ b $ 和 $ n $（$ 1 \leq b \leq a \leq 10^9 $，$ 1 \leq n \leq 100 $），分别表示炸弹定时器的最大值、炸弹定时器的初始值和工具的数量。 - 第二行包含 $ n $ 个整数 $ x_1, x_2, \dots, x_n $（$ 1 \leq x_i \leq 10^9 $），表示使用第 $ i $ 个工具时定时器可以增加的数值。 输出： - 对于每个测试用例，输出一个整数，表示炸弹爆炸前的最大时间（以秒计）。