303948: CF760B. Frodo and pillows

Memory Limit:256 MB Time Limit:1 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

Frodo and pillows

题意翻译

有n个霍比特人去Frodo家里,Frodo家有n个床和m个枕头(n<=m),每个人至少需要1个枕头。然而,如果一个霍比特人比他的邻床的枕头少至少2个,那么他的心灵就会受到伤害。 现在,已知Frodo睡在第k个床,而Frodo想拥有最多的枕头,那么在不伤害到任何人的情况下,Frodo能拥有的枕头数最多是多少? 注意:根据样例理解,Frodo也是霍比特人,包括在n个人中,不算作另外的人。 Translated by @孤独·粲泽

题目描述

$ n $ hobbits are planning to spend the night at Frodo's house. Frodo has $ n $ beds standing in a row and $ m $ pillows ( $ n<=m $ ). Each hobbit needs a bed and at least one pillow to sleep, however, everyone wants as many pillows as possible. Of course, it's not always possible to share pillows equally, but any hobbit gets hurt if he has at least two pillows less than some of his neighbors have. Frodo will sleep on the $ k $ -th bed in the row. What is the maximum number of pillows he can have so that every hobbit has at least one pillow, every pillow is given to some hobbit and no one is hurt?

输入输出格式

输入格式


The only line contain three integers $ n $ , $ m $ and $ k $ ( $ 1<=n<=m<=10^{9} $ , $ 1<=k<=n $ ) — the number of hobbits, the number of pillows and the number of Frodo's bed.

输出格式


Print single integer — the maximum number of pillows Frodo can have so that no one is hurt.

输入输出样例

输入样例 #1

4 6 2

输出样例 #1

2

输入样例 #2

3 10 3

输出样例 #2

4

输入样例 #3

3 6 1

输出样例 #3

3

说明

In the first example Frodo can have at most two pillows. In this case, he can give two pillows to the hobbit on the first bed, and one pillow to each of the hobbits on the third and the fourth beds. In the second example Frodo can take at most four pillows, giving three pillows to each of the others. In the third example Frodo can take three pillows, giving two pillows to the hobbit in the middle and one pillow to the hobbit on the third bed.

Input

题意翻译

有n个霍比特人去Frodo家里,Frodo家有n个床和m个枕头(n<=m),每个人至少需要1个枕头。然而,如果一个霍比特人比他的邻床的枕头少至少2个,那么他的心灵就会受到伤害。 现在,已知Frodo睡在第k个床,而Frodo想拥有最多的枕头,那么在不伤害到任何人的情况下,Frodo能拥有的枕头数最多是多少? 注意:根据样例理解,Frodo也是霍比特人,包括在n个人中,不算作另外的人。 Translated by @孤独·粲泽

加入题单

上一题 下一题 算法标签: