codeforces-scrape

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

1955C.md (2128B)


      1 Source: https://codeforces.com/problemset/problem/1955/C
      2 
      3 C. Inhabitant of the Deep Sea
      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 $n$ ships set out to explore the depths of the ocean. The ships are numbered from $1$ to $n$ and follow each other in ascending order; the $i$-th ship has a durability of $a_i$.
     22 
     23 The Kraken attacked the ships $k$ times in a specific order. First, it attacks the first of the ships, then the last, then the first again, and so on.
     24 
     25 Each attack by the Kraken reduces the durability of the ship by $1$. When the durability of the ship drops to $0$, it sinks and is no longer subjected to attacks (thus the ship ceases to be the first or last, and the Kraken only attacks the ships that have not yet sunk). If all the ships have sunk, the Kraken has nothing to attack and it swims away.
     26 
     27 For example, if $n=4$, $k=5$, and $a=[1, 2, 4, 3]$, the following will happen:
     28 
     29 1. The Kraken attacks the first ship, its durability becomes zero and now $a = [2, 4, 3]$;
     30 2. The Kraken attacks the last ship, now $a = [2, 4, 2]$;
     31 3. The Kraken attacks the first ship, now $a = [1, 4, 2]$;
     32 4. The Kraken attacks the last ship, now $a = [1, 4, 1]$;
     33 5. The Kraken attacks the first ship, its durability becomes zero and now $a = [4, 1]$.
     34 
     35 How many ships were sunk after the Kraken's attack?
     36 
     37 Input
     38 
     39 The first line contains an integer $t$ ($1 \le t \le 10^4$) — the number of test cases.
     40 
     41 The first line of each test case contains two integers $n$ and $k$ ($1 \le n \le 2 \cdot 10^5$, $1 \le k \le 10^{15}$) — the number of ships and how many times the Kraken will attack the ships.
     42 
     43 The second line of each test case contains $n$ integers $a_1, a_2, \dots, a_n$ ($1 \le a_i \le 10^9$) — the durability of the ships.
     44 
     45 It is guaranteed that the sum of $n$ for all test cases does not exceed $2 \cdot 10^5$.
     46 
     47 Output
     48 
     49 For each test case, output the number of ships sunk by the Kraken on a separate line.
     50 
     51 Example
     52 
     53 Input
     54 
     55 ```
     56 6
     57 
     58 4 5
     59 
     60 1 2 4 3
     61 
     62 4 6
     63 
     64 1 2 4 3
     65 
     66 5 20
     67 
     68 2 7 1 8 2
     69 
     70 2 2
     71 
     72 3 2
     73 
     74 2 15
     75 
     76 1 5
     77 
     78 2 7
     79 
     80 5 2
     81 ```
     82 
     83 Output
     84 
     85 ```
     86 2
     87 3
     88 5
     89 0
     90 2
     91 2
     92 ```