codeforces-scrape

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

1704C.md (2612B)


      1 Source: https://codeforces.com/problemset/problem/1704/C
      2 
      3 C. Virus
      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 are $n$ houses numbered from $1$ to $n$ on a circle. For each $1 \leq i \leq n - 1$, house $i$ and house $i + 1$ are neighbours; additionally, house $n$ and house $1$ are also neighbours.
     22 
     23 Initially, $m$ of these $n$ houses are infected by a deadly virus. Each morning, Cirno can choose a house which is uninfected and protect the house from being infected permanently.
     24 
     25 Every day, the following things happen in order:
     26 
     27 * Cirno chooses an uninfected house, and protect it permanently.
     28 * All uninfected, unprotected houses which have at least one infected neighbor become infected.
     29 
     30 Cirno wants to stop the virus from spreading. Find the minimum number of houses that will be infected in the end, if she optimally choose the houses to protect.
     31 
     32 Note that every day Cirno always chooses a house to protect before the virus spreads. Also, a protected house will not be infected forever.
     33 
     34 Input
     35 
     36 The input consists of multiple test cases. The first line contains a single integer $t$ ($1 \leq t \leq 10^4$) — the number of test cases. Description of test cases follows.
     37 
     38 The first line of each test case consists of two positive integers $n, m$ ($5 \leq n \leq 10^9$, $1 \leq m \leq \min(n, 10^5)$) — the number of houses on the circle, and the number of houses that are initially infected.
     39 
     40 The second line of each test case consists of $m$ distinct positive integers $a_1, a_2, \cdots , a_m$ ($1 \leq a_i \leq n$) — the indices of the houses infected initially.
     41 
     42 It is guaranteed that the sum of $m$ over all test cases does not exceed $10^5$.
     43 
     44 Output
     45 
     46 For each test case, output an integer on a separate line, which is the minimum number of infected houses in the end.
     47 
     48 Example
     49 
     50 Input
     51 
     52 ```
     53 8
     54 
     55 10 3
     56 
     57 3 6 8
     58 
     59 6 2
     60 
     61 2 5
     62 
     63 20 3
     64 
     65 3 7 12
     66 
     67 41 5
     68 
     69 1 11 21 31 41
     70 
     71 10 5
     72 
     73 2 4 6 8 10
     74 
     75 5 5
     76 
     77 3 2 5 4 1
     78 
     79 1000000000 1
     80 
     81 1
     82 
     83 1000000000 4
     84 
     85 1 1000000000 10 16
     86 ```
     87 
     88 Output
     89 
     90 ```
     91 7
     92 5
     93 11
     94 28
     95 9
     96 5
     97 2
     98 15
     99 ```
    100 
    101 Note
    102 
    103 In the first test case:
    104 
    105 At the start of the first day, house $3$, $6$, $8$ are infected. Choose house $2$ to protect.
    106 
    107 At the start of the second day, house $3$, $4$, $5$, $6$, $7$, $8$, $9$ are infected. Choose house $10$ to protect.
    108 
    109 At the start of the third day, no more houses are infected.
    110 
    111 In the second test case:
    112 
    113 At the start of the first day, house $2$, $5$ are infected. Choose house $1$ to protect.
    114 
    115 At the start of the second day, house $2$, $3$, $4$, $5$, $6$ are infected. No more available houses can be protected.