← 返回题目列表

Codeforces · 785/C

C. 安东和童话

中文机器翻译题面 查看原题

安东喜欢听童话故事,尤其是安东最好的朋友丹尼克讲的童话故事。现在丹尼克给安东讲了一个童话故事:

“从前,有一个皇帝。他非常富有,有很多粮食。有一天,他下令建造一个巨大的谷仓,把所有的粮食都放在那里。最好的建筑工人花了三天三夜建造那个谷仓。但是他们忽视了,谷仓里留下了一个小洞,每天都有麻雀从里面飞出来。这里飞来一只麻雀,叼起一颗谷子就飞走了……”

更正式地说,以下故事发生在童话故事中。第一天开始时,可​​容纳 n 粒谷物的谷仓已满。然后,每天(从第一天开始)都会发生以下情况:

- m 粒谷物被带到谷仓。如果 m 粒谷物不适合谷仓,谷仓就会满了,不适合的谷物会被带回来(在这个问题中,我们可以假设不适合谷仓的谷物不被考虑在内)。
- 麻雀来吃谷物。第i天我麻雀来了,即第一天一只麻雀来,第二天两只麻雀来,依此类推。每只麻雀吃一粒谷物。如果谷仓是空的,麻雀就什么也不吃。

安东厌倦了听丹尼克描述每只吃谷仓谷物的麻雀。安东不知道童话故事什么时候结束,所以他要求你确定,到哪一天结束时谷仓将第一次变空。帮助安东编写一个程序来确定那天的数字!

输入

输入的唯一行包含两个整数 n 和 m (1 ≤ n, m ≤ 1018) - 谷仓的容量和每天带来的谷物数量。

输出

输出一个整数——谷仓第一次变空的日期。天数从一开始。

示例

输入 #1

5 2

输出 #1

4

输入 #2

8 1

输出 #2

5

注意

在第一个样本中,谷仓的容量为五粒谷物,每天运送两粒谷物。发生以下情况:

- 第一天开始时,谷物被送到谷仓。已经满了,所以什么也没有发生。
- 第一天结束时,一只麻雀来了,吃了一粒​​谷物,所以还剩下 5 - 1 = 4 粒。
- 第二天一开始就带来了两粒谷物。谷仓已经满了,一粒谷物都装不下。
- 第二天快结束时,两只麻雀来了。还剩下5 - 2 = 3粒。
- 第三天开始时,带来了两粒谷物。谷仓又满了。
- 第三天结束时,三只麻雀来吃谷物。还剩下5 - 3 = 2粒。
- 第四天开始时,谷物再次被带来。还剩下2 + 2 = 4粒。
- 第四天结束时,四只麻雀来吃谷物。剩余 4 - 4 = 0 粒。谷仓是空的。

所以答案是 4,因为到第四天结束时谷仓就空了。