$22/7$ 是一個常見的 $\pi$ 近似值,這個近似值從古代就有人使用。縱使阿基米德並非這個近似值的始創者,但他證明了 $22/7$ 高估了圓周率。他以 $22/7$ 大於外切正 $96$ 邊形的周界作證明。
但是今天沒有要教你算圓周率,因為那出題太麻煩了。
人與人之間偶有嫌隙,但破鏡重圓才是正確的道路。
現在有一些人,他們形成一個朋友鏈(就直直一條沒有分支),可是他們之間有一些人吵架了,導致這個朋友鏈瀕臨斷裂,好消息是現在有一個新的科技繩可以把吵架的人綁在一起,這樣他們就重新和好了,可是這種繩子最多只能用 $k$ 條且為相同長度的,不然朋友鏈就會斷掉,而且單條越長越貴,所以要盡可能用短的繩子,已知綁起兩個人需要使用兩單位的繩子,三個人需要使用三單位的繩子,以此類推。想請問你繩子單條最短最少需要多長。
第一行輸入包含三個正整數 $n$ $m$ $k$ ($2 \leq n \leq 10^ 9$, $m < n$ 且 $m \leq 10^ 6$, $k\leq m$)
代表有 $n$ 個人,編號從 $1$ 開始,還有 $m$ 個吵架,最多可以用 $k$ 段繩子。
第二行輸入包含 $m$ 個由小到大的整數用空白分開,第 $i$ 個代表編號第 $A_i$ 與 $A_i + 1$ 吵架
輸出僅包含一個整數,代表答案。
No. | Testdata Range | Score |
---|---|---|
1 | 0~12 | 100 |
No. | Time Limit (ms) | Memory Limit (KiB) | Output Limit (KiB) | Subtasks |
---|---|---|---|---|
0 | 1000 | 65536 | 65536 | |
1 | 1000 | 65536 | 65536 | |
2 | 1000 | 65536 | 65536 | |
3 | 1000 | 65536 | 65536 | |
4 | 1000 | 65536 | 65536 | |
5 | 1000 | 65536 | 65536 | |
6 | 2000 | 65536 | 65536 | |
7 | 1000 | 65536 | 65536 | |
8 | 2000 | 65536 | 65536 | |
9 | 2000 | 65536 | 65536 | |
10 | 2000 | 65536 | 65536 | |
11 | 2000 | 65536 | 65536 | |
12 | 1000 | 65536 | 65536 |