1724. [USACO Dec02]奶牛职业网球赛

【题目描述】

参加职业网球赛的奶牛们有着职业牛网球赛协会（BTP）的排名。

有时候，预测一场网球赛的结果是可能的。如果参赛的两头牛排名之间的差距大于一个给定的常数K（0<=K<=N-1），即|Rank1-Rank2|>K（其中Rank1,Rank2分别表示奶牛1与奶牛2的排名），那么排名较高的奶牛总是会赢得比赛的胜利。

下周将有一个大型的淘汰赛制的赛事，有N（N=2^t,t<=16,t∈N）头奶牛参赛，产生一个冠军。在第一轮，N/2对选手进行比赛，获胜的N/2个选手进入下一轮。同样，下面的每轮比赛中，都是获胜的一半进入下一轮，直到只剩一头牛。

场外的牛们在对比赛下赌注，想知道随着一轮一轮的比赛，最后有可能夺冠的牛中排名最低的牛的排名。

你的工作就是计算这个最低排名，并且给出一种能使这头牛获胜的场次安排。

【输入格式】

第1行：两个空格隔开的数N和K。

【输出格式】

一行一个整数，即所有可能夺冠的牛中排名最低的牛的排名。

【样例输入】

16 3

【样例输出】

11

【提示】

你只需要输出可能获胜的牛的最低排名，不必输出具体方案。

对于样例，方案之一是：

第一轮：(3 1) (5 2) (6 4) (7 16) (8 13) (9 14) (10 15) (11 12)，其中每一对数表示一个对局，前一个是获胜者。

第二轮：(5 3) (8 6) (9 7) (11 10)

第三轮：(8 5) (11 9)

第四轮：(11 8)

【来源】

USACO Dec 02 绿组

Romanian Olympiad via Stroe,2002

翻译：庄乐