CF985D.Sand Fortress
提高+/省选-
通过率:0%
时间限制:2.00s
内存限制:256MB
AC君温馨提醒
该题目为【codeforces】题库的题目,您提交的代码将被提交至codeforces进行远程评测,并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供,我们无法保证该服务的稳定性,若提交后无反应,请等待一段时间后再进行重试。
题目描述
You are going to the beach with the idea to build the greatest sand castle ever in your head! The beach is not as three-dimensional as you could have imagined, it can be decribed as a line of spots to pile up sand pillars. Spots are numbered 1 through infinity from left to right.
Obviously, there is not enough sand on the beach, so you brought n packs of sand with you. Let height h__i of the sand pillar on some spot i be the number of sand packs you spent on it. You can't split a sand pack to multiple pillars, all the sand from it should go to a single one. There is a fence of height equal to the height of pillar with H sand packs to the left of the first spot and you should prevent sand from going over it.
Finally you ended up with the following conditions to building the castle:
- _h_1 ≤ H: no sand from the leftmost spot should go over the fence;
- For any
|h__i - h__i + 1| ≤ 1: large difference in heights of two neighboring pillars can lead sand to fall down from the higher one to the lower, you really don't want this to happen;
: you want to spend all the sand you brought with you.
As you have infinite spots to build, it is always possible to come up with some valid castle structure. Though you want the castle to be as compact as possible.
Your task is to calculate the minimum number of spots you can occupy so that all the aforementioned conditions hold.
你正前往海滩,脑海中构思着要建造一座有史以来最伟大的沙堡!然而,这片海滩并不像你想象中那样是三维的,它实际上可以被描述为一条从左至右无限延伸的直线,上面分布着若干可用于堆砌沙柱的位置点。这些位置点从左到右依次编号为 1,2,3,…(直至无穷)。
显然,海滩上没有足够的沙子,因此你随身带了 n 包沙子。设第 i 个位置点上的沙柱高度为 hi,其值等于你在该位置上所消耗的沙包数量。你不能将一包沙子拆分用于多个沙柱——每包沙子必须全部用于唯一一个沙柱。此外,在第一个位置点(即位置 1)的左侧有一道围栏,其高度恰好等于用 H 包沙子堆成的沙柱高度;你必须确保沙子不会越过这道围栏。
最终,你归纳出建造沙堡需满足以下条件:
- h1≤H:最左侧位置(位置 1)上的沙柱不可高于左侧围栏;
- 对任意 i≥1,满足 ∣hi−hi+1∣≤1:相邻两个沙柱的高度差过大,会导致沙子从较高的沙柱滑落到较低的沙柱上,而这正是你极力避免的情况;
- ∑i=1∞hi=n:你希望耗尽所有带来的沙子。
由于可供建造的位置点是无限多的,因此总能构造出某种满足上述所有条件的沙堡结构。但你希望这座沙堡尽可能紧凑。
你的任务是:计算满足上述所有条件时,所需占据的最少位置点数量。
输入格式
The only line contains two integer numbers n and H (1 ≤ n, H ≤ 1018) — the number of sand packs you have and the height of the fence, respectively.
唯一一行包含两个整数 n 和 H(1 ≤ n, H ≤ 1018)——分别为你拥有的沙包数量和篱笆的高度。
输出格式
Print the minimum number of spots you can occupy so the all the castle building conditions hold.
输出满足所有城堡建造条件时,你所能占据的最少格子数。
输入输出样例
输入#1
5 2
输出#1
3
输入#2
6 8
输出#2
3
说明/提示
Here are the heights of some valid castles:
- n = 5, H = 2, [2, 2, 1, 0, ...], [2, 1, 1, 1, 0, ...], [1, 0, 1, 2, 1, 0, ...]
- n = 6, H = 8, [3, 2, 1, 0, ...], [2, 2, 1, 1, 0, ...], [0, 1, 0, 1, 2, 1, 1, 0...] (this one has 5 spots occupied)
The first list for both cases is the optimal answer, 3 spots are occupied in them.
And here are some invalid ones:
- n = 5, H = 2, [3, 2, 0, ...], [2, 3, 0, ...], [1, 0, 2, 2, ...]
- n = 6, H = 8, [2, 2, 2, 0, ...], [6, 0, ...], [1, 4, 1, 0...], [2, 2, 1, 0, ...]
以下是一些合法城堡的高度示例:
- n=5,H=2,[2,2,1,0,…],[2,1,1,1,0,…],[1,0,1,2,1,0,…]
- n=6,H=8,[3,2,1,0,…],[2,2,1,1,0,…],[0,1,0,1,2,1,1,0…](该序列占用了 5 个位置)
两种情况下的第一个序列均为最优解,它们均仅占用了 3 个位置。
以下是一些非法的序列:
- n=5,H=2,[3,2,0,…],[2,3,0,…],[1,0,2,2,…]
- n=6,H=8,[2,2,2,0,…],[6,0,…],[1,4,1,0…],[2,2,1,0,…]
输入解题思路,AI测评打分。不知道怎么写?