codeforces-scrape

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

2086B.md (2412B)


      1 Source: https://codeforces.com/problemset/problem/2086/B
      2 
      3 B. Large Array and Segments
      4 
      5 time limit per test
      6 
      7 2 seconds
      8 
      9 memory limit per test
     10 
     11 512 megabytes
     12 
     13 input
     14 
     15 standard input
     16 
     17 output
     18 
     19 standard output
     20 
     21 There is an array $a$ consisting of $n$ positive integers, and a positive integer $k$. An array $b$ is created from array $a$ according to the following rules:
     22 
     23 * $b$ contains $n \cdot k$ numbers;
     24 * the first $n$ numbers of array $b$ are the same as the numbers of array $a$, that is, $b_{i} = a_{i}$ for $i \le n$;
     25 * for any $i \gt n$, it holds that $b_{i} = b_{i - n}$.
     26 
     27 For example, if $a = [2, 3, 1, 4]$ and $k = 3$, then $b = [2, 3, 1, 4, 2, 3, 1, 4, 2, 3, 1, 4]$.
     28 
     29 Given a number $x$, it is required to count the number of such positions $l$ ($1 \le l \le n \cdot k$), for which there exists a position $r \ge l$, such that the sum of the elements of array $b$ on the segment $[l, r]$ is at least $x$ (in other words, $b_{l} + b_{l+1} + \dots + b_{r} \ge x$).
     30 
     31 Input
     32 
     33 Each test consists of several test cases. The first line contains one integer $t$ ($1 \le t \le 10^{4}$) — the number of test cases. The description of the test cases follows.
     34 
     35 The first line of each test case contains three integers $n$, $k$, $x$ ($1 \le n, k \le 10^{5}$; $1 \le x \le 10^{18}$).
     36 
     37 The second line of each test case contains $n$ integers $a_{i}$ ($1 \le a_{i} \le 10^{8}$).
     38 
     39 Additional constraints on the input:
     40 
     41 * the sum of $n$ across all test cases does not exceed $2 \cdot 10^{5}$;
     42 * the sum of $k$ across all test cases does not exceed $2 \cdot 10^{5}$.
     43 
     44 Output
     45 
     46 For each test case, output one integer — the number of suitable positions $l$ in the array $b$.
     47 
     48 Example
     49 
     50 Input
     51 
     52 ```
     53 7
     54 
     55 5 3 10
     56 
     57 3 4 2 1 5
     58 
     59 15 97623 1300111
     60 
     61 105 95 108 111 118 101 95 118 97 108 111 114 97 110 116
     62 
     63 1 100000 1234567891011
     64 
     65 1
     66 
     67 1 1 1
     68 
     69 1
     70 
     71 1 1 1
     72 
     73 2
     74 
     75 2 1 2
     76 
     77 1 1
     78 
     79 2 1 5
     80 
     81 2 1
     82 ```
     83 
     84 Output
     85 
     86 ```
     87 12
     88 1452188
     89 0
     90 1
     91 1
     92 1
     93 0
     94 ```
     95 
     96 Note
     97 
     98 In the first test case, the array $b$ looks like this:
     99 
    100 $$[3, 4, 2, 1, 5, 3, 4, 2, 1, 5, 3, 4, 2, 1, 5]$$
    101 
    102 There are $12$ positions $l$ for which there exists a suitable position $r$. Here are some (not all) of them:
    103 
    104 * $l = 1$, for which there is a position $r = 6$, the sum over the segment $[1, 6]$ equals $18$;
    105 * $l = 2$, for which there is a position $r = 5$, the sum over the segment $[2, 5]$ equals $12$;
    106 * $l = 6$, for which there is a position $r = 9$, the sum over the segment $[6, 9]$ equals $10$.