English · Original
Chinese · Translation
Formal · Original
It is winter now, and Max decided it's about time he watered the garden.
The garden can be represented as _n_ consecutive garden beds, numbered from 1 to _n_. _k_ beds contain water taps (_i_\-th tap is located in the bed _x__i_), which, if turned on, start delivering water to neighbouring beds. If the tap on the bed _x__i_ is turned on, then after one second has passed, the bed _x__i_ will be watered; after two seconds have passed, the beds from the segment \[_x__i_ - 1, _x__i_ + 1\] will be watered (if they exist); after _j_ seconds have passed **(_j_ is an integer number)**, the beds from the segment \[_x__i_ - (_j_ - 1), _x__i_ + (_j_ - 1)\] will be watered (if they exist). **Nothing changes during the seconds, so, for example, we can't say that the segment \[_x__i_ - 2.5, _x__i_ + 2.5\] will be watered after 2.5 seconds have passed; only the segment \[_x__i_ - 2, _x__i_ + 2\] will be watered at that moment.**
<center> The garden from test 1. White colour denotes a garden bed without a tap, red colour — a garden bed with a tap.</center><center> The garden from test 1 after 2 seconds have passed after turning on the tap. White colour denotes an unwatered garden bed, blue colour — a watered bed.</center>Max wants to **turn on all the water taps at the same moment**, and now he wonders, what is the minimum number of seconds that have to pass after he turns on some taps until the whole garden is watered. Help him to find the answer!
## Input
The first line contains one integer _t_ — the number of test cases to solve (1 ≤ _t_ ≤ 200).
Then _t_ test cases follow. The first line of each test case contains two integers _n_ and _k_ (1 ≤ _n_ ≤ 200, 1 ≤ _k_ ≤ _n_) — the number of garden beds and water taps, respectively.
Next line contains _k_ integers _x__i_ (1 ≤ _x__i_ ≤ _n_) — the location of _i_\-th water tap. It is guaranteed that for each condition _x__i_ - 1 < _x__i_ holds.
It is guaranteed that the sum of _n_ over all test cases doesn't exceed 200.
**Note that in hacks you have to set _t_ = 1**.
## Output
For each test case print one integer — the minimum number of seconds that have to pass after Max turns on some of the water taps, until the whole garden is watered.
[samples]
## Note
The first example consists of 3 tests:
1. There are 5 garden beds, and a water tap in the bed 3. If we turn it on, then after 1 second passes, only bed 3 will be watered; after 2 seconds pass, beds \[1, 3\] will be watered, and after 3 seconds pass, everything will be watered.
2. There are 3 garden beds, and there is a water tap in each one. If we turn all of them on, then everything will be watered after 1 second passes.
3. There are 4 garden beds, and only one tap in the bed 1. It will take 4 seconds to water, for example, bed 4.
现在是冬天，Max 决定是时候给花园浇水了。
花园可以表示为 #cf_span[n] 个连续的花园床，编号从 #cf_span[1] 到 #cf_span[n]。其中有 #cf_span[k] 个花园床装有水龙头（第 #cf_span[i] 个水龙头位于第 #cf_span[xi] 个床），如果打开，它们会向相邻的床供水。如果位于第 #cf_span[xi] 个床的水龙头被打开，那么经过 1 秒后，第 #cf_span[xi] 个床会被浇水；经过 2 秒后，区间 #cf_span[[xi - 1, xi + 1]] 内的床（如果存在）会被浇水；经过 #cf_span[j] 秒后（#cf_span[j] 为整数），区间 #cf_span[[xi - (j - 1), xi + (j - 1)]] 内的床（如果存在）会被浇水。*在秒数之间没有任何变化，因此我们不能说经过 #cf_span[2.5] 秒后区间 #cf_span[[xi - 2.5, xi + 2.5]] 会被浇水；只有在该时刻区间 #cf_span[[xi - 2, xi + 2]] 会被浇水。*
Max 希望 *同时打开所有水龙头*，现在他想知道，在打开某些水龙头后，最少需要多少秒才能使整个花园都被浇水。请帮助他找出答案！
第一行包含一个整数 #cf_span[t] —— 需要解决的测试用例数量（#cf_span[1 ≤ t ≤ 200]）。
接下来是 #cf_span[t] 个测试用例。每个测试用例的第一行包含两个整数 #cf_span[n] 和 #cf_span[k]（#cf_span[1 ≤ n ≤ 200]，#cf_span[1 ≤ k ≤ n]）—— 分别表示花园床的数量和水龙头的数量。
下一行包含 #cf_span[k] 个整数 #cf_span[xi]（#cf_span[1 ≤ xi ≤ n]）—— 第 #cf_span[i] 个水龙头的位置。保证对每个 #cf_span[i] 都满足条件 #cf_span[xi - 1 < xi]。
保证所有测试用例中 #cf_span[n] 的总和不超过 #cf_span[200]。
*注意：在黑客测试中，你必须设置 #cf_span[t = 1]*。
对于每个测试用例，输出一个整数——Max 打开某些水龙头后，直到整个花园都被浇水所需的最少秒数。
## Input
第一行包含一个整数 #cf_span[t] —— 需要解决的测试用例数量（#cf_span[1 ≤ t ≤ 200]）。接下来是 #cf_span[t] 个测试用例。每个测试用例的第一行包含两个整数 #cf_span[n] 和 #cf_span[k]（#cf_span[1 ≤ n ≤ 200]，#cf_span[1 ≤ k ≤ n]）—— 分别表示花园床的数量和水龙头的数量。下一行包含 #cf_span[k] 个整数 #cf_span[xi]（#cf_span[1 ≤ xi ≤ n]）—— 第 #cf_span[i] 个水龙头的位置。保证对每个 #cf_span[i] 都满足条件 #cf_span[xi - 1 < xi]。保证所有测试用例中 #cf_span[n] 的总和不超过 #cf_span[200]。*注意：在黑客测试中，你必须设置 #cf_span[t = 1]*。
## Output
对于每个测试用例，输出一个整数——Max 打开某些水龙头后，直到整个花园都被浇水所需的最少秒数。
[samples]
## Note
第一个示例包含 #cf_span[3] 个测试：
有 #cf_span[5] 个花园床，且在第 #cf_span[3] 个床有一个水龙头。如果打开它，那么经过 #cf_span[1] 秒后，只有第 #cf_span[3] 个床会被浇水；经过 #cf_span[2] 秒后，区间 #cf_span[[1, 3]] 内的床会被浇水；经过 #cf_span[3] 秒后，所有床都会被浇水。
有 #cf_span[3] 个花园床，每个床都有一个水龙头。如果打开所有水龙头，那么经过 #cf_span[1] 秒后，所有床都会被浇水。
有 #cf_span[4] 个花园床，且仅在第 #cf_span[1] 个床有一个水龙头。要浇灌例如第 #cf_span[4] 个床，需要 #cf_span[4] 秒。
**Definitions**
Let $ t \in \mathbb{Z} $ be the number of test cases.
For each test case:
- Let $ n \in \mathbb{Z} $ be the number of garden beds, indexed $ \{1, 2, \dots, n\} $.
- Let $ k \in \mathbb{Z} $ be the number of water taps.
- Let $ X = (x_1, x_2, \dots, x_k) $ be the sorted sequence of tap positions, where $ 1 \le x_1 < x_2 < \dots < x_k \le n $.
**Constraints**
1. $ 1 \le t \le 200 $
2. $ 1 \le n \le 200 $, $ 1 \le k \le n $
3. $ 1 \le x_i \le n $ and $ x_{i-1} < x_i $ for all $ i \in \{2, \dots, k\} $
4. $ \sum_{\text{test cases}} n \le 200 $
**Objective**
Find the minimum time $ T \in \mathbb{Z}_{\ge 0} $ such that, if all taps are turned on simultaneously, every bed $ j \in \{1, 2, \dots, n\} $ is covered by the watered region from at least one tap after $ T $ seconds.
The water from tap at position $ x_i $, after $ s $ seconds, covers the interval:
$$
[x_i - (s - 1), x_i + (s - 1)] \cap \{1, 2, \dots, n\}
$$
Equivalently, find the smallest $ T $ such that:
$$
\bigcup_{i=1}^{k} \left[ x_i - (T - 1), x_i + (T - 1) \right] \supseteq \{1, 2, \dots, n\}
$$
(If $ T = 0 $, coverage is only the exact tap positions.)
API Response (JSON)
{
"problem": {
"name": "A. Water The Garden",
"description": {
"content": "It is winter now, and Max decided it's about time he watered the garden. The garden can be represented as _n_ consecutive garden beds, numbered from 1 to _n_. _k_ beds contain water taps (_i_\\-th tap",
"description_type": "Markdown"
},
"platform": "Codeforces",
"limit": {
"time_limit": 1000,
"memory_limit": 262144
},
"difficulty": "None",
"is_remote": true,
"is_sync": true,
"sync_url": null,
"sign": "CF920A"
},
"statements": [
{
"statement_type": "Markdown",
"content": "It is winter now, and Max decided it's about time he watered the garden.\n\nThe garden can be represented as _n_ consecutive garden beds, numbered from 1 to _n_. _k_ beds contain water taps (_i_\\-th tap...",
"is_translate": false,
"language": "English"
},
{
"statement_type": "Markdown",
"content": "现在是冬天，Max 决定是时候给花园浇水了。\n\n花园可以表示为 #cf_span[n] 个连续的花园床，编号从 #cf_span[1] 到 #cf_span[n]。其中有 #cf_span[k] 个花园床装有水龙头（第 #cf_span[i] 个水龙头位于第 #cf_span[xi] 个床），如果打开，它们会向相邻的床供水。如果位于第 #cf_span[xi] 个床的水龙头被打开，那么经过 1 秒...",
"is_translate": true,
"language": "Chinese"
},
{
"statement_type": "Markdown",
"content": "**Definitions** \nLet $ t \\in \\mathbb{Z} $ be the number of test cases. \nFor each test case: \n- Let $ n \\in \\mathbb{Z} $ be the number of garden beds, indexed $ \\{1, 2, \\dots, n\\} $. \n- Let $ k \\in...",
"is_translate": false,
"language": "Formal"
}
]
}