切割相加 (APCS 2026-11 高級)

有一個只由數字 \(1\)～\(9\) 組成的字串 \(S\)。字串裡每兩個相鄰的數字之間都有一個空隙，長度為 \(|S|\) 的字串共有 \(|S|-1\) 個空隙。你可以在其中一些空隙插入加號（每個空隙可以插、也可以不插），把 \(S\) 變成一個加法算式，再算出它的結果。一個加號都不插也算是一種插法，這時算式就是 \(S\) 本身。

另外給你一個整數 \(m\)。請在所有結果不超過 \(m\) 的插法中，找出最大的結果，並算出有幾種插法的結果剛好等於這個最大值。兩種插法只要有某一個空隙在一種插法裡插了加號、在另一種插法裡沒插，就算是不同的插法。

以範例 2 為例，\(S\) 是 91253217、\(m = 100\)。插成 9+12+53+2+17 時，結果是 \(93\)；一個加號都不插時，結果是 \(91253217\)，超過了 \(m\)。沒有任何插法的結果介於 \(94\) 到 \(100\) 之間，所以在所有結果不超過 \(100\) 的插法中，最大的結果是 \(93\)，而且剛好有兩種插法得到 \(93\)：

9+12+53+2+17 = 93
9+1+2+53+21+7 = 93

因此第一行輸出 \(93\)，第二行輸出 \(2\)。

輸入格式

第一行是字串 \(S\)。

第二行是一個整數 \(m\)。

限制

• \(1 \le |S| \le 40\)，其中 \(|S|\) 是字串 \(S\) 的長度
• \(S\) 只由數字 \(1\)～\(9\) 組成
• \(1 \le m \le 3 \times 10^4\)
• \(m\) 不小於 \(S\) 中所有數字的總和
• 答案中的插法數不超過 \(2^{31}-1\)

輸出格式

輸出兩行。第一行是所有結果不超過 \(m\) 的插法中最大的結果，第二行是結果等於這個最大值的插法數。

評分說明

每一筆測試資料的執行時間限制均為 \(2\) 秒，依正確通過的測試資料筆數給分。

範例輸入 1

36319
50

範例輸出 1

49
2

範例解釋 1

沒有任何插法的結果剛好是 \(50\)。結果不超過 \(50\) 的插法中，最大的結果是 \(49\)，有以下兩種插法：

36+3+1+9 = 49
3+6+31+9 = 49

範例輸入 2

91253217
100

範例輸出 2

93
2

範例解釋 2

這組範例在題目敘述中已經說明過：結果不超過 \(100\) 的插法中，最大的結果是 \(93\)，共有兩種插法。

題目來源

APCS 2026 年 11 月高級實作題第 3 題。

官方未公布題本，題敘依考生考後回憶整理，細節可能與正式試題有出入。