codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

2192C.md (2730B)


      1 Source: https://codeforces.com/problemset/problem/2192/C
      2 
      3 C. All-in-one Gun
      4 
      5 time limit per test
      6 
      7 2 seconds
      8 
      9 memory limit per test
     10 
     11 256 megabytes
     12 
     13 input
     14 
     15 standard input
     16 
     17 output
     18 
     19 standard output
     20 
     21 You are developing a new shooter game, but since there are a lot of shooter games out there, you decide to have something unique in your game.
     22 
     23 You have an all-in-one gun that shoots bullets in a fixed order. There are $n$ bullets in the magazine, the $i$-th of which deals $a_i$ damage. The enemy starts with $h$ health and dies when its health becomes $\le 0$.
     24 
     25 The gun shoots one bullet per second. After firing all $n$ bullets, it must reload, which takes $k$ seconds. Reloading always restores the same sequence of bullets $[a_1, a_2, \ldots, a_n]$. You cannot reload early; you must empty the magazine first. At the start, the magazine is already full.
     26 
     27 Before the fight begins, you may perform at most one swap: pick any indices $1 \le i \lt j \le n$ and exchange $a_i$ with $a_j$.
     28 
     29 Your task is to find the minimum number of seconds needed to kill the enemy, taking into account this optional single swap.
     30 
     31 Input
     32 
     33 Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 10^4$). The description of the test cases follows.
     34 
     35 The first line of each testcase contains three integer $n$, $h$ and $k$ ($2 \le n \le 2\cdot 10^5$, $ 1 \le h, k \le 10^9$) — the size of magazine, health of your enemy and time required to reload the magazine.
     36 
     37 The second line of each testcase contains $n$ integers $a_1, a_2, \ldots, a_n$ ($1 \le a_i \le 10^9$).
     38 
     39 It is guaranteed that the sum of $n$ does not exceed $2 \cdot 10^5$ over all test cases.
     40 
     41 Output
     42 
     43 For each testcase, output a single integer denoting the minimum time required to kill the enemy.
     44 
     45 Example
     46 
     47 Input
     48 
     49 ```
     50 6
     51 
     52 5 10 1
     53 
     54 4 2 3 5 3
     55 
     56 5 10 1
     57 
     58 4 2 3 7 3
     59 
     60 3 10 2
     61 
     62 1 2 3
     63 
     64 2 5 3
     65 
     66 2 1
     67 
     68 3 18 5
     69 
     70 1 2 3
     71 
     72 4 10 10
     73 
     74 1 1 2 2
     75 ```
     76 
     77 Output
     78 
     79 ```
     80 3
     81 
     82 2
     83 
     84 7
     85 
     86 6
     87 
     88 19
     89 
     90 17
     91 ```
     92 
     93 Note
     94 
     95 In the first test case, you swap the bullets present at index $2$ and $5$. This makes array $a$ as $4, 3, 3, 5, 2$.
     96 
     97 After $3$ seconds, the health of your enemy will be $10 - 4 - 3 - 3 = 0$, hence the enemy dies in $3$ seconds. It can be shown that achieving time to kill less than $3$ is not possible.
     98 
     99 In the third test case, you swap bullets present at index $1$ and $3$. This makes array $a$ as $3, 2, 1$.
    100 
    101 In $7$ seconds, you shoot the entire first magazine ($3$ seconds) $+$ reload a new magazine ($2$ seconds) $+$ shoot the first and the second bullet from the new magazine ($2$ seconds).
    102 
    103 The health of the enemy will be $10 - 3 - 2 - 1 - 3 - 2 = -1$, hence the enemy dies in $7$ seconds. It can be shown that achieving time to kill less than $7$ is not possible.