← 返回题目列表

Codeforces · 760/B

B. 佛罗多和枕头

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

n 个霍比特人计划在佛罗多的家里过夜。佛罗多有 n 张排成一排的床和 m 个枕头(n ≤ m)。每个霍比特人都需要一张床和至少一个枕头来睡觉,但是,每个人都想要尽可能多的枕头。当然,并不总是可以平等地共用枕头,但是如果任何霍比特人的枕头比某些邻居少至少两个枕头,他就会受伤。

Frodo 将睡在该行的第 k 张床上。他最多可以拥有多少个枕头,以便每个霍比特人至少有一个枕头,每个枕头都给某个霍比特人,并且没有人受伤?

输入

唯一一行包含三个整数 n、m 和 k (1 ≤ n ≤ m ≤ 109, 1 ≤ k ≤ n)——霍比特人的数量、枕头的数量和佛罗多床的数量。

输出

打印单个整数 - 佛罗多可以拥有的最大枕头数量,这样就不会有人受伤。

示例

输入 #1

4 6 2

输出 #1

2

输入 #2

3 10 3

输出 #2

4

输入 #3

3 6 1

输出 #3

3

注意

在第一个示例中,Frodo 最多可以有两个枕头。在这种情况下,他可以给第一个床上的霍比特人两个枕头,给第三个和第四个床上的霍比特人各一个枕头。

在第二个例子中,Frodo 最多可以拿四个枕头,给其他人每人三个枕头。

在第三个例子中,佛罗多可以拿三个枕头,两个枕头给中间的霍比特人,一个枕头给第三张床上的霍比特人。