1858B.md (5419B)
1 Source: https://codeforces.com/problemset/problem/1858/B 2 3 B. The Walkway 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$ benches near the Main Walkway in Summer Infomatics School. These benches are numbered by integers from $1$ to $n$ in order they follow. Also there are $m$ cookie sellers near the Walkway. The $i$-th ($1 \le i \le m$) cookie sellers is located near the $s_i$-th bench. 22 23 Petya is standing in the beginning of the Walkway. He will pass near all benches starting from the $1$-st bench and ending with the $n$-th bench. Petya passes the distance between two consecutive benches in $1$ minute. He has a knapsack with an infinite amount of cookies. Petya is going to eat cookies from his knapsack and buy them from cookie sellers during the walk. 24 25 Petya eats cookies only near the benches according to the following rule: he will eat the cookie near the $i$-th ($1 \le i \le n$) bench if and only if at least one of the following conditions holds: 26 27 * There is a cookie seller near the $i$-th bench. Then Petya will buy a cookie from cookie seller and eat it immediately. 28 * Petya has not yet eaten a cookie. Then Petya will take a cookie from his knapsack and eat it immediately. 29 * At least $d$ minutes passed since Petya ate the previous cookie. In other words, Petya has not eaten a cookie near the benches $i-1, i-2, \ldots, \max(i-d+1, 1)$. Then Petya will take a cookie from his knapsack and eat it immediately. 30 31 You may assume that Petya eats cookies instantly. Petya will not eat two or more cookies near the same bench. 32 33 You want to minimize the number of cookies Petya will eat during his walk. In order to do this, you will ask the administration of the Summer Informatics School to remove exactly one cookie seller from the Walkway before Petya starts his walk. 34 35 Please determine the minimum possible number of cookies Petya can eat after removing exactly one cookie seller. Also determine the number of cookie sellers, such that if you remove one of them, Petya will eat the minimum possible number of cookies. 36 37 Input 38 39 The first line contains a single integer $t$ ($1 \le t \le 10^3$) — the number of test cases. 40 41 The first line of each test case contains three integers $n$, $m$ and $d$ ($2 \le d \le n \le 10^9$, $2 \le m \le \min(10^{5}, n)$) — the number of benches, the number of cookie sellers and the value of parameter $d$ from the statement, respectively. 42 43 The second line of each test case contains $m$ integers $s_1, s_2, \ldots, s_m$ ($1 \le s_i \le n$) — the locations of the cookie sellers. It is guaranteed that $s_{i} \lt s_{i+1}$ for all $1 \leq i \leq m - 1$. 44 45 It is guaranteed that the sum of $m$ over all test cases does not exceed $10^5$. 46 47 Output 48 49 For each test case print two integers — the minimum number of cookies that Petya can eat if exactly one cookie seller is removed, and the number of cookie sellers such that if one of them is removed, Petya will eat the minimum possible number of cookies. 50 51 Example 52 53 Input 54 55 ``` 56 8 57 58 6 2 2 59 60 2 5 61 62 8 3 2 63 64 3 5 8 65 66 10 4 9 67 68 2 8 9 10 69 70 30 5 8 71 72 6 8 15 24 29 73 74 30 5 8 75 76 6 8 12 20 27 77 78 8 8 3 79 80 1 2 3 4 5 6 7 8 81 82 2 2 2 83 84 1 2 85 86 1000000000 3 20000000 87 88 57008429 66778899 837653445 89 ``` 90 91 Output 92 93 ``` 94 3 1 95 4 1 96 4 4 97 6 4 98 5 2 99 7 7 100 1 1 101 51 1 102 ``` 103 104 Note 105 106 In the first test case $n=6$, $m=2$, $d=2$ and $s=[2, 5]$. If no cookie seller is removed, then Petya will eat $4$ cookies during his walk (note that you have to remove exactly one cookie seller; this case is explained only to show how Petya decides whether to eat a cookie): 107 108 * Petya will eat a cookie near the $1$-st bench since he has not yet eaten a cookie. 109 * Petya will eat a cookie near the $2$-nd bench since there is a cookie seller near this bench. 110 * Petya will not eat a cookie near the $3$-rd bench since only $1 \lt d$ minute passed since he ate a cookie. 111 * Petya will eat a cookie near the $4$-th bench since $2\ge d$ minutes passed since he ate a cookie. 112 * Petya will eat a cookie near the $5$-th bench since there is a cookie seller near this bench. 113 * Petya will not eat a cookie near the $6$-th bench since only $1 \lt d$ minute passed since he ate a cookie. 114 115 If the $1$-st cookie seller is removed, Petya will eat $3$ cookies (near the benches $1$, $3$ and $5$). If the $2$-nd cookie seller is removed, Petya will eat $4$ cookies (near the benches $1$, $2$, $4$ and $6$). 116 117 Thus, the minimum number of cookies Petya will eat is $3$; there is only one cookie seller such that removing it results in minimizing the number of cookies Petya will eat. 118 119 In the second test case 120 121 * the removal of the $1$-st or the $2$-nd cookie seller results in Petya eating $5$ cookies near the benches $1$, $3$, $5$, $7$, $8$; 122 * the removal of the $3$-rd cookie seller results in Petya eating $4$ cookies near the benches $1$, $3$, $5$, $7$. 123 124 Note that the second integer you should output is the number of (that is, amount) cookie sellers, not the index of a cookie seller to remove. Thus, the answer to the second test case is 4 1 because there is only one cookie seller such that removing it results in Petya eating four cookies, which is the minimum possible. 125 126 In the third test case Petya will eat $4$ cookies no matter what cookie seller is removed. 127 128 Note that Petya is not interested in minimizing the number of cookies he will eat, so he eats cookies whenever it is possible under the rule from the statement.