h399. 蛋糕店促銷（簡易版） - 高中生程式解題系統

內容

※請注意，此題為簡易版，簡易版與困難版的唯一差異在於 $N$ 與 $T$ 的範圍。

最近蛋糕店的生意不好，為了吸引客人來光顧，蛋糕店的老闆最近在想要做一個促銷活動，活動內容大致如下。

在蛋糕店裡設置了摸彩箱，摸彩箱裡面有很多紙卡，每個紙卡上面都寫著一個正整數。而來光顧的每個客人都可以進行一次摸彩，假設客人摸彩摸到了數字 $M$ ，他可以使用特定規則找出一個數字 $K$ ，並且用 $10 M$ 的價格買走 $K$ 個蛋糕，找出 $K$ 的方法如下：

將數字 $M$ 拆成最少 $1$ 最多 $M$ 個正整數，並且將這些正整數相乘，所得到的值即為 $K$ 。

而老闆為了評估成本，要事前知道所有紙卡最多可以買走幾個蛋糕，希望你能幫助他，但由於答案可能很大，請將答案取 $998244353$ 的餘數後再告訴老闆。

輸入說明

輸入的第一行有一個正整數 $T$ ( $1 \leq T \leq 10^{4}$ )，代表老闆要問你 $T$ 個不同紙卡。

接著有 $T$ 行，每行有一個正整數 $N$ ( $1 \leq N \leq 10^{4}$ )，代表老闆問你數字 $N$ 最多可以買走幾個蛋糕。

保證所有 $N$ 的總和不會超過 $10^{4}$ 。

輸出說明

對於每一個 $N$ ，請輸出一行，每行有一個數字 $K$ ，代表數字 $N$ 最多可以買走 $K$ 個蛋糕。

範例輸入 #1

範例輸出 #1

6
4
1

測資資訊：

記憶體限制： 256 MB
公開測資點#0 (10%): 1.0s , <1K
公開測資點#1 (10%): 1.0s , <1K
公開測資點#2 (10%): 1.0s , <1K
公開測資點#3 (10%): 1.0s , <1K
公開測資點#4 (10%): 1.0s , <1K
公開測資點#5 (10%): 1.0s , <1M
公開測資點#6 (10%): 1.0s , <1M
公開測資點#7 (10%): 1.0s , <1M
公開測資點#8 (10%): 1.0s , <1K
公開測資點#9 (10%): 1.0s , <1K

提示：

對於第一個數字 $5$ ，可能的答案有

$1 \times 1 \times 1 \times 1 \times 1 = 1$

$1 \times 1 \times 1 \times 2 = 2$

$1 \times 2 \times 2 = 4$

$1 \times 1 \times 3 = 3$

$2 \times 3 = 6$

$1 \times 4 = 4$

$5 = 5$

其中最大者為 $6$ 。

標籤:

Greedy 數學

出處:

pcsh weekly contest [管理者： Ststone1687 (Ststone) ]

編號	身分	題目	主題	人氣	發表日期
沒有發現任何「解題報告」