久遠久遠以前,存在一個由正整數所構成的國度,在這個國度裡面,名為「再生」的程序不斷地進行著。所謂的再生,是指國度中最大的兩個正整數進行的融合與分裂後轉變為三個新正整數的過程。精確來說,這兩個最大的數會先融合為此二數之和 $S$,之後$S$會分裂成三個數字,滿足三數之和為$S$且任兩數最多差$1$若國度中最大的數不止兩個,則依然只有其中某二數會進行再生的程序。然而,再生並不會隨意進行;進行的充分必要條件是在國度中有兩個數字之和大於等於$K$,其中$K$為「再生門檻」,為一大於等於$3$的數。對於一個不會發生再生的國度,我們稱其為「穩定國度」。
比如說,考慮一由三數$4, 6, 9$構成的國度;若$K = 9$,則再生會於此國度進行,首先$6$與$9$融合為$15$,之後$15$分裂成$5, 5, 5$三個數字,因此經歷完第一次再生後,此國度的成員會變為$4, 5, 5, 5$四個數字。我們可以很容易的檢測,當前的國度並非穩定國度,故會進行第二次再生;在第二次再生過程中,最大的二數 (某兩個 $5$) 會融合成$10$,之後分裂成$3, 3, 4$;在第二次再生完成後,國度中有$3, 3, 4, 4, 5$五個數字。這樣的再生會不斷地進行,直到國度變為穩定國度 (再生終會停止,這是顯而易見的)。以此範例來說,再生停止時國度中的數字為$3, 3, 3, 3, 3, 4$。
今針對一給定的國度,請計算此國度需要經歷幾次的再生,才會變為「穩定國度」。
每筆測試資料的第一列有兩個正整數$n, K$($2 \leq n \leq 10^ 5$、$3 \leq K \leq 10^ {12}$),分別代表一國度最初的正整數個數以及該國度的再生門檻。接下來的$n$列,每一列有一個正整數,這$n$個數字代表了國度中一開始的數字。所有數字都不會超過$10^ {12}$。
在單一行中,輸出此國度須經歷的再生總數。
題目取自2019 TOI選訓第四次模擬考pA
Testdata from Utaha
Problem set by oToToT
No. | Testdata Range | Constraints | Score |
---|---|---|---|
1 | 0~5 | $2\leq n\leq 10$、$3\leq K \leq 10$、所有數字皆不超過100 | 9 |
2 | 6~14 | $K=3$ | 17 |
3 | 15~24 | $2\leq n\leq 10^ 3$、所有數字皆不超過$10^ 6$ | 18 |
4 | 25~33 | $2\leq n\leq 10^ 4$、所有數字皆不超過$10^ 9$ | 23 |
5 | 34~42 | 無額外限制。 | 33 |