codeforces-scrape

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

2112C.md (1957B)


      1 Source: https://codeforces.com/problemset/problem/2112/C
      2 
      3 C. Coloring Game
      4 
      5 time limit per test
      6 
      7 2.5 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 Alice and Bob are playing a game using an integer array $a$ of size $n$.
     22 
     23 Initially, all elements of the array are colorless. First, Alice chooses $3$ elements and colors them red. Then Bob chooses any element and colors it blue (if it was red — recolor it). Alice wins if the sum of the red elements is strictly greater than the value of the blue element.
     24 
     25 Your task is to calculate the number of ways that Alice can choose $3$ elements in order to win regardless of Bob's actions.
     26 
     27 Input
     28 
     29 The first line contains a single integer $t$ ($1 \le t \le 1000$) — the number of test cases.
     30 
     31 The first line of each test case contains a single integer $n$ ($3 \le n \le 5000$).
     32 
     33 The second line contains $n$ integers $a_1, a_2, \dots, a_n$ ($1 \le a_1 \le a_2 \le \cdots \le a_n \le 10^5$).
     34 
     35 Additional constraint on the input: the sum of $n$ over all test cases doesn't exceed $5000$.
     36 
     37 Output
     38 
     39 For each test case, print a single integer — the number of ways that Alice can choose $3$ elements in order to win regardless of Bob's actions.
     40 
     41 Example
     42 
     43 Input
     44 
     45 ```
     46 6
     47 
     48 3
     49 
     50 1 2 3
     51 
     52 4
     53 
     54 1 1 2 4
     55 
     56 5
     57 
     58 7 7 7 7 7
     59 
     60 5
     61 
     62 1 1 2 2 4
     63 
     64 6
     65 
     66 2 3 3 4 5 5
     67 
     68 5
     69 
     70 1 1 1 1 3
     71 ```
     72 
     73 Output
     74 
     75 ```
     76 0
     77 0
     78 10
     79 2
     80 16
     81 0
     82 ```
     83 
     84 Note
     85 
     86 In the first two test cases, no matter which three elements Alice chooses, Bob will be able to paint one element blue so that Alice does not win.
     87 
     88 In the third test case, Alice can choose any three elements. If Bob colors one of the red elements, the sum of red elements will be $14$, and the sum of blue elements will be $7$. If Bob chooses an uncolored element, the sum of red elements will be $21$, and the sum of blue elements will be $7$.
     89 
     90 In the fourth test case, Alice can choose either the $1$-st, $3$-rd and $4$-th element, or the $2$-nd, $3$-rd and $4$-th element.