codeforces-scrape

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

1781B.md (2082B)


      1 Source: https://codeforces.com/problemset/problem/1781/B
      2 
      3 B. Going to the Cinema
      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 A company of $n$ people is planning a visit to the cinema. Every person can either go to the cinema or not. That depends on how many other people will go. Specifically, every person $i$ said: "I want to go to the cinema if and only if at least $a_i$ other people will go, not counting myself". That means that person $i$ will become sad if:
     22 
     23 * they go to the cinema, and strictly less than $a_i$ other people go; or
     24 * they don't go to the cinema, and at least $a_i$ other people go.
     25 
     26 In how many ways can a set of people going to the cinema be chosen so that nobody becomes sad?
     27 
     28 Input
     29 
     30 Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 10^4$). The description of the test cases follows.
     31 
     32 Each test case consists of two lines. The first line contains a single integer $n$ ($2 \le n \le 2 \cdot 10^5$) — the number of people in the company.
     33 
     34 The second line contains $n$ integers $a_1, a_2, \ldots, a_n$ ($0 \le a_i \le n - 1$) — integers from peoples' claims.
     35 
     36 It is guaranteed that the sum of $n$ over all test cases does not exceed $2 \cdot 10^5$.
     37 
     38 Output
     39 
     40 For each test case, print a single integer — the number of different ways to choose a set of people going to the cinema so that nobody becomes sad.
     41 
     42 Example
     43 
     44 Input
     45 
     46 ```
     47 4
     48 
     49 2
     50 
     51 1 1
     52 
     53 7
     54 
     55 0 1 2 3 4 5 6
     56 
     57 8
     58 
     59 6 0 3 3 6 7 2 7
     60 
     61 5
     62 
     63 3 0 0 3 3
     64 ```
     65 
     66 Output
     67 
     68 ```
     69 2
     70 1
     71 3
     72 2
     73 ```
     74 
     75 Note
     76 
     77 In the first test case, both people want to go to the cinema if and only if the other person goes. There are two valid options: either both people go, or neither of them goes. However, if just one of them goes, both will be sad.
     78 
     79 In the second test case, everyone has to go to the cinema. In any other case, someone will be sad.
     80 
     81 In the third test case, there are three valid options: person number $2$ goes to the cinema; or persons with indices $2, 3, 4, 7$ go; or all eight people go.