codeforces-scrape

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

1826A.md (1628B)


      1 Source: https://codeforces.com/problemset/problem/1826/A
      2 
      3 A. Trust Nobody
      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 There is a group of $n$ people. Some of them might be liars, who always tell lies. Other people always tell the truth. The $i$-th person says "There are at least $l_i$ liars amongst us". Determine if what people are saying is contradictory, or if it is possible. If it is possible, output the number of liars in the group. If there are multiple possible answers, output any one of them.
     22 
     23 Input
     24 
     25 The first line contains a single integer $t$ ($1 \leq t \leq 1000$) — the number of test cases.
     26 
     27 The first line of each test case contains a single integer $n$ ($1 \leq n \leq 100$).
     28 
     29 The second line of each test case contains $n$ integers $l_i$ ($0 \leq l_i \leq n$) — the number said by the $i$-th person.
     30 
     31 It's guaranteed that the sum of all $n$ does not exceed $10^4$.
     32 
     33 Output
     34 
     35 For each test case output a single integer. If what people are saying is contradictory, output $-1$. Otherwise, output the number of liars in the group. If there are multiple possible answers, output any one of them.
     36 
     37 Example
     38 
     39 Input
     40 
     41 ```
     42 7
     43 
     44 2
     45 
     46 1 2
     47 
     48 2
     49 
     50 2 2
     51 
     52 2
     53 
     54 0 0
     55 
     56 1
     57 
     58 1
     59 
     60 1
     61 
     62 0
     63 
     64 5
     65 
     66 5 5 3 3 5
     67 
     68 6
     69 
     70 5 3 6 6 3 5
     71 ```
     72 
     73 Output
     74 
     75 ```
     76 1
     77 -1
     78 0
     79 -1
     80 0
     81 3
     82 4
     83 ```
     84 
     85 Note
     86 
     87 In the first example, the only possible answer is that the second person is a liar, so the answer is $1$ liar.
     88 
     89 In the second example, it can be proven that we can't choose the liars so that all the requirements are satisfied.
     90 
     91 In the third example, everybody tells the truth, so the answer is $0$ liars.