codeforces-scrape

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

1982C.md (2696B)


      1 Source: https://codeforces.com/problemset/problem/1982/C
      2 
      3 C. Boring Day
      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 On another boring day, Egor got bored and decided to do something. But since he has no friends, he came up with a game to play.
     22 
     23 Egor has a deck of $n$ cards, the $i$-th card from the top has a number $a_i$ written on it. Egor wants to play a certain number of rounds until the cards run out. In each round, he takes a non-zero number of cards from the top of the deck and finishes the round. If the sum of the numbers on the cards collected during the round is between $l$ and $r$, inclusive, the round is won; otherwise, it is lost.
     24 
     25 Egor knows by heart the order of the cards. Help Egor determine the maximum number of rounds he can win in such a game. Note that Egor is not required to win rounds consecutively.
     26 
     27 Input
     28 
     29 Each test consists of several test cases. The first line contains an integer $t$ ($1 \le t \le 10^{4}$) — the number of test cases. This is followed by a description of the test cases.
     30 
     31 The first line of each test case contains three integers $n$, $l$, and $r$ ($1 \le n \le 10^{5}$, $1 \le l \le r \le 10^9$).
     32 
     33 The second line of each test case contains $n$ integers $a_1, a_2, \ldots, a_n$ ($1 \le a_i \le 10^9$) — the numbers on the cards from top to bottom.
     34 
     35 It is guaranteed that the sum of $n$ for all test cases does not exceed $2 \cdot 10^{5}$.
     36 
     37 Output
     38 
     39 For each test case, output a single number — the maximum number of rounds Egor can win.
     40 
     41 Example
     42 
     43 Input
     44 
     45 ```
     46 8
     47 
     48 5 3 10
     49 
     50 2 1 11 3 7
     51 
     52 10 1 5
     53 
     54 17 8 12 11 7 11 21 13 10 8
     55 
     56 3 4 5
     57 
     58 3 4 2
     59 
     60 8 12 25
     61 
     62 10 7 5 13 8 9 12 7
     63 
     64 2 3 3
     65 
     66 5 2
     67 
     68 9 7 9
     69 
     70 2 10 5 1 3 7 6 2 3
     71 
     72 1 8 10
     73 
     74 9
     75 
     76 5 5 6
     77 
     78 1 4 2 6 4
     79 ```
     80 
     81 Output
     82 
     83 ```
     84 3
     85 0
     86 1
     87 4
     88 0
     89 3
     90 1
     91 2
     92 ```
     93 
     94 Note
     95 
     96 In the first test case, Egor can win $3$ rounds:
     97 
     98 * In the first round, take the top $2$ cards with values $2$ and $1$ and win, as their sum is $3$. After this, the deck will look like this: $[11, 3, 7]$.
     99 * In the second round, take the top card and lose, as its value $11$ is greater than $r = 10$. After this, the deck will look like this: $[3, 7]$.
    100 * In the third round, take the top card with value $3$ and win. After this, the deck will look like this: $[7]$.
    101 * After this, in the fourth round, Egor only has to take the last card in the deck with value $7$ and win again.
    102 
    103 In the second test case, Egor cannot win any rounds, no matter how hard he tries.
    104 
    105 In the third test case, you can take one card in each round, then the first and third rounds will be losing, and the second round will be winning.
    106 
    107 In the fourth test case, you can take two cards in each round and always win.