codeforces-scrape

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

2075C.md (2616B)


      1 Source: https://codeforces.com/problemset/problem/2075/C
      2 
      3 C. Two Colors
      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 Monocarp has installed a new fence at his summer house. The fence consists of $n$ planks of the same size arranged in a row.
     22 
     23 Monocarp decided that he would paint his fence according to the following rules:
     24 
     25 * each plank of the fence will be painted in exactly one color;
     26 * the number of different colors that the planks will be painted in is exactly two;
     27 * the planks of the fence that are painted in the same color must form a continuous sequence, meaning that for all pairs of planks painted in the same color, there will be no planks painted in a different color between them.
     28 
     29 Monocarp has $m$ different paints, and the paint of the $i$-th color is sufficient to paint no more than $a_i$ planks of the fence. Monocarp will not buy any additional paints.
     30 
     31 Your task is to determine the number of different ways to paint the fence that satisfy all of Monocarp's described wishes. Two ways to paint are considered different if there exists a plank that is painted in different colors in these two ways.
     32 
     33 Input
     34 
     35 The first line contains a single integer $t$ ($1 \le t \le 10^4$) — the number of test cases.
     36 
     37 The first line of each test case contains two integers $n$ and $m$ ($2 \le n, m \le 2 \cdot 10^5$) — the number of planks in the fence and the number of different colors of paint that Monocarp has.
     38 
     39 The second line contains $m$ integers $a_1, a_2, \dots, a_m$ ($1 \le a_i \le n$), where $a_i$ is the maximum number of planks that can be painted with the paint of color $i$.
     40 
     41 The sum of $n$ over all test cases does not exceed $2 \cdot 10^5$. The sum of $m$ over all test cases does not exceed $2 \cdot 10^5$.
     42 
     43 Output
     44 
     45 For each test case, output the number of different ways to paint the fence that satisfy all of Monocarp's described wishes.
     46 
     47 Example
     48 
     49 Input
     50 
     51 ```
     52 3
     53 
     54 5 2
     55 
     56 2 4
     57 
     58 5 2
     59 
     60 3 4
     61 
     62 12 3
     63 
     64 5 9 8
     65 ```
     66 
     67 Output
     68 
     69 ```
     70 4
     71 6
     72 22
     73 ```
     74 
     75 Note
     76 
     77 In the first test case, there are $4$ different ways to paint the fence (the sequences of color numbers in which the planks can be painted from left to right are listed below):
     78 
     79 1. $[1, 2, 2, 2, 2]$;
     80 2. $[1, 1, 2, 2, 2]$;
     81 3. $[2, 2, 2, 1, 1]$;
     82 4. $[2, 2, 2, 2, 1]$.
     83 
     84 In the second test case, there are $6$ different ways to paint the fence (the sequences of color numbers in which the planks can be painted from left to right are listed below):
     85 
     86 1. $[1, 2, 2, 2, 2]$;
     87 2. $[1, 1, 2, 2, 2]$;
     88 3. $[1, 1, 1, 2, 2]$;
     89 4. $[2, 2, 1, 1, 1]$;
     90 5. $[2, 2, 2, 1, 1]$;
     91 6. $[2, 2, 2, 2, 1]$.