D. Sand Fortress

你打算去海滩，心中怀揣着建造史上最大沙堡的宏伟目标！然而，海滩并没有你想象中那么三维，它实际上可以被描述为一条直线，上面有无限多个位置用于堆叠沙柱。这些位置从左到右编号为 #cf_span[1] 到无穷大。 显然，海滩上的沙子不够，因此你带了 #cf_span[n] 包沙子。设位置 #cf_span[i] 上沙柱的高度 #cf_span[hi] 为你在该位置使用的沙包数量。*你不能将一个沙包拆分到多个沙柱上，每个沙包必须全部用于一个沙柱。* 在第一个位置左侧有一道高度为 #cf_span[H] 的围栏，你必须防止沙子越过它。 最终，你确定了以下建造城堡的条件： 由于你拥有无限多个位置，总能找到满足上述条件的合法城堡结构。但你希望城堡尽可能紧凑。 你的任务是计算满足所有条件所需的最少位置数。 输入仅一行，包含两个整数 #cf_span[n] 和 #cf_span[H]（#cf_span[1 ≤ n, H ≤ 1018]），分别表示你拥有的沙包数量和围栏高度。 请输出满足所有城堡建造条件所需的最少位置数。 以下是一些合法城堡的高度示例： 两种情况下的第一个列表均为最优解，均占用了 #cf_span[3] 个位置。 以下是一些非法示例： ## Input 输入仅一行，包含两个整数 #cf_span[n] 和 #cf_span[H]（#cf_span[1 ≤ n, H ≤ 1018]），分别表示你拥有的沙包数量和围栏高度。 ## Output 请输出满足所有城堡建造条件所需的最少位置数。 [samples] ## Note 以下是一些合法城堡的高度示例： #cf_span[n = 5, H = 2, [2, 2, 1, 0, ...], [2, 1, 1, 1, 0, ...], [1, 0, 1, 2, 1, 0, ...]] #cf_span[n = 6, H = 8, [3, 2, 1, 0, ...], [2, 2, 1, 1, 0, ...], [0, 1, 0, 1, 2, 1, 1, 0...]]（此例占用了 #cf_span[5] 个位置） 两种情况下的第一个列表均为最优解，均占用了 #cf_span[3] 个位置。 以下是一些非法示例： #cf_span[n = 5, H = 2, [3, 2, 0, ...], [2, 3, 0, ...], [1, 0, 2, 2, ...]] #cf_span[n = 6, H = 8, [2, 2, 2, 0, ...], [6, 0, ...], [1, 4, 1, 0...], [2, 2, 1, 0, ...]]

Given: - $ n $: total number of sand packs (each pack must be assigned entirely to one pillar). - $ H $: height of the fence to the left of the first spot; the leftmost pillar must have height at most $ H $, and no pillar may exceed the height of the pillar immediately to its left by more than 1 (i.e., the sequence of pillar heights must be *non-increasing* and differ by at most 1 between adjacent pillars, with the leftmost pillar $ \leq H $). Objective: Find the minimum number of spots $ k $ such that there exists a sequence $ h_1, h_2, \dots, h_k $ of non-negative integers satisfying: 1. $ h_1 \leq H $, 2. $ h_i - h_{i+1} \leq 1 $ for all $ i = 1, 2, \dots, k-1 $, 3. $ h_i \geq h_{i+1} $ for all $ i = 1, 2, \dots, k-1 $ (non-increasing), 4. $ \sum_{i=1}^k h_i = n $, 5. $ h_i \in \mathbb{Z}_{\geq 0} $. We seek the **minimum** $ k $ such that such a sequence exists. --- **Formal Mathematical Statement:** Find the smallest integer $ k \geq 1 $ such that there exists a non-increasing sequence $ (h_1, h_2, \dots, h_k) \in \mathbb{Z}_{\geq 0}^k $ satisfying: - $ h_1 \leq H $, - $ h_i \geq h_{i+1} \geq h_i - 1 $ for all $ i = 1, 2, \dots, k-1 $, - $ \sum_{i=1}^k h_i = n $. --- **Equivalent Reformulation (Optimal Structure):** The optimal (maximizing total sand for fixed $ k $) configuration under the constraints is a *unimodal* or *decreasing-by-at-most-1* sequence starting at some $ h_1 \leq H $, decreasing by 1 until it reaches 0 (or 1), and then possibly continuing with 0s (but 0s can be omitted since they don't contribute to the sum). Thus, the maximum total sand that can be placed on $ k $ spots under the constraints is achieved by the sequence: - If $ k \leq H $: $ h_i = H - i + 1 $ for $ i = 1 $ to $ k $ → sum = $ \sum_{i=0}^{k-1} (H - i) = kH - \frac{k(k-1)}{2} $ - If $ k > H $: the sequence decreases from $ H $ to 1, then stays at 0: sum = $ \sum_{i=1}^H i = \frac{H(H+1)}{2} $ Wait — correction: the sequence must be non-increasing and decrease by at most 1. So the **maximum** sand achievable on $ k $ spots is: Let $ m = \min(k, H) $. Then the maximum possible sum is: $$ S_{\max}(k, H) = \sum_{i=1}^m (H - i + 1) + \sum_{i=m+1}^k \max(0, H - m - (i - m - 1)) $$ Wait — better: the optimal configuration is a "pyramid" starting at height $ h_1 = \min(H, h_{\text{max}}) $, decreasing by 1 each step until it hits 0. Actually, the **maximum** sand that can be placed on $ k $ spots with the constraints is: Let $ t = \min(k, H) $. Then the tallest possible sequence is: - $ h_1 = \min(H, t + \text{something}) $ — no. Actually, the optimal way to maximize sand for fixed $ k $ is to start as high as possible, i.e., set $ h_1 = \min(H, a) $, then $ h_2 = h_1 - 1 $, etc., until 0. But we are allowed to start at any $ h_1 \leq H $. So the **maximum** total sand on $ k $ spots is achieved when the sequence is: $$ h_i = \max(0, H - i + 1) \quad \text{for } i = 1, 2, \dots, k $$ Wait — no, that would be if we start at $ H $, but we are constrained to $ h_1 \leq H $. So the maximum sum for $ k $ spots is: Let $ r = \min(k, H) $. Then the best we can do is: - Start at height $ r $, then $ r-1, r-2, \dots, 1 $, and then 0s? No — we can start higher. Actually, the maximum total sand on $ k $ spots is achieved by a sequence that is **non-increasing, decreases by at most 1**, and starts at most at $ H $. So the maximum total is: Let $ x = \min(k, H) $. Then the optimal sequence is: - $ h_1 = H $, $ h_2 = H - 1 $, ..., $ h_{H} = 1 $, then $ h_{H+1} = 0 $, etc. But if $ k < H $, then we can only have $ k $ terms: $ H, H-1, \dots, H - k + 1 $ So: $$ S_{\max}(k, H) = \begin{cases} \sum_{i=0}^{k-1} (H - i) = kH - \frac{k(k-1)}{2} & \text{if } k \leq H \\ \sum_{i=1}^{H} i = \frac{H(H+1)}{2} & \text{if } k > H \end{cases} $$ Wait — if $ k > H $, then the sequence must be: $ H, H-1, \dots, 1, 0, 0, \dots, 0 $. The sum is $ \frac{H(H+1)}{2} $. But if $ k \leq H $, then we can have $ H, H-1, \dots, H-k+1 $, sum = $ \frac{k(2H - k + 1)}{2} $ So: $$ S_{\max}(k, H) = \begin{cases} \frac{k(2H - k + 1)}{2} & \text{if } k \leq H \\ \frac{H(H+1)}{2} & \text{if } k > H \end{cases} $$ We need the **minimum** $ k $ such that $ S_{\max}(k, H) \geq n $. So the problem reduces to: > Find the smallest integer $ k \geq 1 $ such that $ S_{\max}(k, H) \geq n $ Where $ S_{\max}(k, H) $ is defined as above. --- **Final Formal Statement:** Let $ n, H \in \mathbb{Z} $, $ 1 \leq n, H \leq 10^{18} $. Define the function: $$ f(k) = \begin{cases} \displaystyle \frac{k(2H - k + 1)}{2} & \text{if } 1 \leq k \leq H \\ \displaystyle \frac{H(H+1)}{2} & \text{if } k > H \end{cases} $$ Find the minimum integer $ k \geq 1 $ such that $ f(k) \geq n $. --- **Note:** Since $ f(k) $ is strictly increasing for $ k \leq H $, and constant for $ k > H $, we can solve this by binary search on $ k \in [1, \max(H, \lceil \sqrt{2n} \rceil + 1)] $, or solve the quadratic inequality for $ k \leq H $, and check the constant case. But the problem asks only for the **formal mathematical representation**, so we stop here. --- **Answer (Formal):** Find the minimal integer $ k \geq 1 $ such that: $$ \begin{cases} \displaystyle \frac{k(2H - k + 1)}{2} \geq n & \text{if } k \leq H \\ \displaystyle \frac{H(H+1)}{2} \geq n & \text{if } k > H \end{cases} $$