codeforces-scrape

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

1649B.md (2080B)


      1 Source: https://codeforces.com/problemset/problem/1649/B
      2 
      3 B. Game of Ball Passing
      4 
      5 time limit per test
      6 
      7 1 second
      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 Daniel is watching a football team playing a game during their training session. They want to improve their passing skills during that session.
     22 
     23 The game involves $n$ players, making multiple passes towards each other. Unfortunately, since the balls were moving too fast, after the session Daniel is unable to know how many balls were involved during the game. The only thing he knows is the number of passes delivered by each player during all the session.
     24 
     25 Find the minimum possible amount of balls that were involved in the game.
     26 
     27 Input
     28 
     29 There are several test cases in the input data. The first line contains a single integer $t$ ($1 \leq t \leq 5 \cdot 10^4$) — the number of test cases. This is followed by the test cases description.
     30 
     31 The first line of each test case contains one integer $n$ ($2 \leq n \leq 10^5$) — the number of players.
     32 
     33 The second line of the test case contains a sequence of integers $a_1, a_2, \ldots, a_n$ ($0 \leq a_i \leq 10^9$), where $a_i$ is the number of passes delivered by the $i$-th player.
     34 
     35 It is guaranteed that the sum of $n$ over all test cases doesn't exceed $10^5$.
     36 
     37 Output
     38 
     39 For each test case print a single integer — the answer to the problem.
     40 
     41 Example
     42 
     43 Input
     44 
     45 ```
     46 4
     47 
     48 4
     49 
     50 2 3 3 2
     51 
     52 3
     53 
     54 1 5 2
     55 
     56 2
     57 
     58 0 0
     59 
     60 4
     61 
     62 1000000000 1000000000 1000000000 1000000000
     63 ```
     64 
     65 Output
     66 
     67 ```
     68 1
     69 2
     70 0
     71 1
     72 ```
     73 
     74 Note
     75 
     76 In the first test case, with the only ball, the game can go like this:
     77 
     78 $2 \rightarrow 1 \rightarrow 3 \rightarrow 4 \rightarrow 1 \rightarrow 2 \rightarrow 3 \rightarrow 4 \rightarrow 2 \rightarrow 3 \rightarrow 2$.
     79 
     80 In the second test case, there is no possible way to play the game with only one ball. One possible way to play with two balls:
     81 
     82 $2 \rightarrow 1 \rightarrow 2 \rightarrow 3 \rightarrow 2 \rightarrow 1$.
     83 
     84 $2 \rightarrow 3 \rightarrow 2 \rightarrow 1$
     85 
     86 In the third example, there were no passes, so $0$ balls are possible.