codeforces-scrape

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

1419C.md (2527B)


      1 Source: https://codeforces.com/problemset/problem/1419/C
      2 
      3 C. Killjoy
      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 A new agent called Killjoy invented a virus COVID-2069 that infects accounts on Codeforces. Each account has a rating, described by an integer (it can possibly be negative or very large).
     22 
     23 Killjoy's account is already infected and has a rating equal to $x$. Its rating is constant. There are $n$ accounts except hers, numbered from $1$ to $n$. The $i$-th account's initial rating is $a_i$. Any infected account (initially the only infected account is Killjoy's) instantly infects any uninfected account if their ratings are equal. This can happen at the beginning (before any rating changes) and after each contest. If an account is infected, it can not be healed.
     24 
     25 Contests are regularly held on Codeforces. In each contest, any of these $n$ accounts (including infected ones) can participate. Killjoy can't participate. After each contest ratings are changed this way: each participant's rating is changed by an integer, but the sum of all changes must be equal to zero. New ratings can be any integer.
     26 
     27 Find out the minimal number of contests needed to infect all accounts. You can choose which accounts will participate in each contest and how the ratings will change.
     28 
     29 It can be proven that all accounts can be infected in some finite number of contests.
     30 
     31 Input
     32 
     33 The first line contains a single integer $t$ $(1 \le t \le 100)$ — the number of test cases. The next $2t$ lines contain the descriptions of all test cases.
     34 
     35 The first line of each test case contains two integers $n$ and $x$ ($2 \le n \le 10^3$, $-4000 \le x \le 4000$) — the number of accounts on Codeforces and the rating of Killjoy's account.
     36 
     37 The second line of each test case contains $n$ integers $a_1, a_2, \dots, a_n$ $(-4000 \le a_i \le 4000)$ — the ratings of other accounts.
     38 
     39 Output
     40 
     41 For each test case output the minimal number of contests needed to infect all accounts.
     42 
     43 Example
     44 
     45 Input
     46 
     47 ```
     48 3
     49 2 69
     50 68 70
     51 6 4
     52 4 4 4 4 4 4
     53 9 38
     54 -21 83 50 -59 -77 15 -71 -78 20
     55 ```
     56 
     57 Output
     58 
     59 ```
     60 1
     61 0
     62 2
     63 ```
     64 
     65 Note
     66 
     67 In the first test case it's possible to make all ratings equal to $69$. First account's rating will increase by $1$, and second account's rating will decrease by $1$, so the sum of all changes will be equal to zero.
     68 
     69 In the second test case all accounts will be instantly infected, because all ratings (including Killjoy's account's rating) are equal to $4$.