#215026. [NHSPC 2024] 花果山

【部分不宜展示的内容已被删除】

「我們必須立刻改變！從現在起，花果山所有桃樹結下的桃子，直接接收後，再重新分配給花果山上的猴子，直到所有猴子都擁有等量的桃子為止！」

孫悟空要求統計所有猴子所擁有的桃子以及桃樹每天的桃子產量。花果山統計局很快地將相關數據呈給孫悟空：花果山上總共有 隻猴子，第 隻猴子擁有 顆桃子，而桃樹的產量很穩定，每天都能夠生產出 顆桃子。

花果山的內政大臣天命人針對重新分配的方法，向孫悟空提出建言：「為了花果山上的和諧，重新分配桃子時，不可以從猴子手中奪走任何桃子。每天接收到的桃子，必須當天就分配出去。最重要的是要避免相對剝奪感，每一天分配到最多桃子的猴子，只能比分配到最少桃子的猴子多得一顆桃子。」孫悟空覺得很有道理，便要求按照天命人的建議進行分配。

假設 ，即花果山上總共有 4 隻猴子，分別有 1, 2, 3, 4 顆桃子，而桃樹每天的產量是 7 顆桃子。按照天命人的建議，每隻猴子每天都可以分配到一顆或是兩顆桃子，不能更少也不能更多，否則會帶來相對剝奪感。此時可以透過下列步驟，讓所有的猴子擁有等量的桃子：

1. 第一天到第三天都分配各兩顆桃子給前三隻猴子、一顆桃子給第四隻猴子。三天過後，四隻猴子分別擁有 7, 8, 9, 7 顆桃子。
2. 第四天、第五天都分配各兩顆桃子給前兩隻猴子、一顆桃子給第三隻猴子、兩顆桃子給第四隻猴子。五天過後，四隻猴子分別擁有 11, 12, 11, 11 顆桃子。
3. 第六天分配一顆桃子給第二隻猴子、各兩顆桃子給其餘的三隻猴子。六天過後，四隻猴子分別擁有 13, 13, 13, 13 顆桃子，數量相等。

請撰寫一個程式計算，最少要幾天之後，才能使得所有的猴子都擁有等量的桃子。

• 表示測試資料個數。
• 為第 筆測試資料。

每一筆測試資料的輸入格式如下

• 為猴子的數量。
• 為桃子每天的產量。
• 代表第 隻猴子擁有的桃子數量。

輸出 筆測試資料之答案

• 為第 筆測試資料之答案。

每一筆測試資料答案的輸出格式如下：如該組測試資料在 天後，所有猴子能夠擁有等量的桃子，則輸出一個整數 ，如果那天永遠不可能到來，則輸出 poor monkeys。

样例输入 1

5
4 7
1 2 3 4
4 4
1 2 3 4
8 3
1 1 2 3 4 5 6 9
8 4
1 1 2 3 4 5 6 9
2 1
0 1

样例输出 1

6
poor monkeys
19
poor monkeys
1

測資限制

• 。
• 。
• 。
• 。
• 且 。
• 輸入的數皆為整數。
• 筆測試資料中 的總和 。

評分說明

本題共有五組子任務，條件限制如下所示。 每一組可有一或多筆測試資料，該組所有測試資料皆需答對才會獲得該組分數。

• 註 1：「最少天數存在」的意思是有一天所有猴子可以擁有等量的桃子，不存在的意思則是這一天永遠不可能到來。
• 註 2：子任務 4 保證對於那些最少天數存在的測試資料，最少天數的總和不超過 。換句話說，正確答案中輸出的數字總和不超過 。