P14908 [NHSPC 2024] 花果山

【部分不宜展示的内容已被删除】 「我們必須立刻改變！從現在起，花果山所有桃樹結下的桃子，直接接收後，再重新分配給花果山上的猴子，直到所有猴子都擁有等量的桃子為止！」 孫悟空要求統計所有猴子所擁有的桃子以及桃樹每天的桃子產量。花果山統計局很快地將相關數據呈給孫悟空：花果山上總共有 $n$ 隻猴子，第 $i$ 隻猴子擁有 $a_i$ 顆桃子，而桃樹的產量很穩定，每天都能夠生產出 $k$ 顆桃子。 花果山的內政大臣天命人針對重新分配的方法，向孫悟空提出建言：「為了花果山上的和諧，重新分配桃子時，不可以從猴子手中奪走任何桃子。每天接收到的桃子，必須當天就分配出去。最重要的是要避免相對剝奪感，每一天分配到最多桃子的猴子，只能比分配到最少桃子的猴子多得一顆桃子。」孫悟空覺得很有道理，便要求按照天命人的建議進行分配。 假設 $n=4,k=7,a_1=1,a_2=2,a_3=3,a_4=4$，即花果山上總共有 4 隻猴子，分別有 1, 2, 3, 4 顆桃子，而桃樹每天的產量是 7 顆桃子。按照天命人的建議，每隻猴子每天都可以分配到一顆或是兩顆桃子，不能更少也不能更多，否則會帶來相對剝奪感。此時可以透過下列步驟，讓所有的猴子擁有等量的桃子： 1. 第一天到第三天都分配各兩顆桃子給前三隻猴子、一顆桃子給第四隻猴子。三天過後，四隻猴子分別擁有 7, 8, 9, 7 顆桃子。 2. 第四天、第五天都分配各兩顆桃子給前兩隻猴子、一顆桃子給第三隻猴子、兩顆桃子給第四隻猴子。五天過後，四隻猴子分別擁有 11, 12, 11, 11 顆桃子。 3. 第六天分配一顆桃子給第二隻猴子、各兩顆桃子給其餘的三隻猴子。六天過後，四隻猴子分別擁有 13, 13, 13, 13 顆桃子，數量相等。 請撰寫一個程式計算，最少要幾天之後，才能使得所有的猴子都擁有等量的桃子。

$$\begin{aligned} &T \\ &\text{testcase}_1 \\ &\text{testcase}_2 \\ &\vdots \\ &\text{testcase}_T \end{aligned}$$ - $T$ 表示測試資料個數。 - $\text{testcase}_i$ 為第 $i$ 筆測試資料。 每一筆測試資料的輸入格式如下 $$\begin{aligned} &n \ k \\ &a_1 \ a_2 \ \ldots \ a_n \end{aligned}$$ - $n$ 為猴子的數量。 - $k$ 為桃子每天的產量。 - $a_i$ 代表第 $i$ 隻猴子擁有的桃子數量。

輸出 $T$ 筆測試資料之答案 $$\begin{aligned} &\text{answer}_1 \\ &\text{answer}_2 \\ &\vdots \\ &\text{answer}_T \end{aligned}$$ - $\text{answer}_i$ 為第 $i$ 筆測試資料之答案。 每一筆測試資料答案的輸出格式如下：如該組測試資料在 $x$ 天後，所有猴子能夠擁有等量的桃子，則輸出一個整數 $x$，如果那天永遠不可能到來，則輸出 `poor monkeys`。

### 測資限制 - $1 \leq T \leq 5 \times 10^5$。 - $2 \leq n \leq 10^6$。 - $1 \leq k \leq 10^9$。 - $0 \leq a_i \leq 10^9$。 - $a_1 \leq a_2 \leq \dots \leq a_n$ 且 $a_1 < a_n$。 - 輸入的數皆為整數。 - $T$ 筆測試資料中 $n$ 的總和 $\sum n \leq 10^6$。 ### 評分說明 本題共有五組子任務，條件限制如下所示。 每一組可有一或多筆測試資料，該組所有測試資料皆需答對才會獲得該組分數。 | 子任務 | 分數 | 額外輸入限制 | | :------: | :----: | ------------ | | 1 | 2 | $\sum n \leq 100$，$k = 1$，$a_i \leq 100$ 且保證最少天數存在。 | | 2 | 3 | $\sum n \leq 100$，$k = n-1$，$a_i \leq 100$ 且保證最少天數存在。 | | 3 | 29 | $\sum n \leq 1000$，$k \leq 1000$，$a_i \leq 1000$ 且保證若最少天數存在，則不超過 $10^4$。 | | 4 | 39 | $\sum n \leq 10^5$，$k \leq 10^5$，$a_i \leq 10^5$，見註 2。 | | 5 | 27 | 無額外限制。 | - 註 1：「最少天數存在」的意思是有一天所有猴子可以擁有等量的桃子，不存在的意思則是這一天永遠不可能到來。 - 註 2：子任務 4 保證對於那些最少天數存在的測試資料，最少天數的總和不超過 $10^5$。換句話說，正確答案中輸出的數字總和不超過 $10^5$。