#P18371. Clubs
Clubs
Clubs
Clubs 是一个双人合作游戏。两人各自手中有一些牌,其中一部分是梅花牌。每个人知道自己有多少张梅花牌,但不知道对方有多少张。
最优合同由两人梅花牌的总数决定:总数小于 时,最优合同为 ;否则,最优合同为 。
两人通过叫价确定合同。第一位玩家先提出一个正整数作为合同。之后两人轮流行动。轮到一名玩家时,他可以接受上一次提出的合同,或者提出一个严格更大的正整数合同。有人接受合同后游戏结束;只有结束时的合同恰好等于最优合同,才算成功。
Algosia 和 Bajtek 正在玩这个游戏。两人都知道 ,也都知道:Algosia 的梅花牌数量是 中的一个,Bajtek 的梅花牌数量是 中的一个。游戏开始前,每个人只获知自己实际持有的梅花牌数量。
求最小的 ,使两人存在一种叫价策略,对所有可能的牌数组合都能保证成功。Algosia 始终先手。可以证明这样的最小值一定存在。
注意:本题只要求输出这个最小的 ,不需要模拟交互或输出策略。 可以为 0,但每次提出的合同仍必须是正整数。
输入格式
第一行包含三个整数 ,分别表示使最优合同变为 的梅花牌总数下界,以及两人各自可能的梅花牌数量的个数。
第二行包含严格递增的 个整数 。
第三行包含严格递增的 个整数 。
输出格式
输出一个整数,表示能够保证达成最优合同的最小 。
数据范围
- ;
- ;
- ;
- 。
输入只有一组数据。
样例输入 1
13 5 3
1 5 7 10 12
2 6 9
样例输出 1
3
样例输入 2
2 1 1
1
1
样例输出 2
0
样例说明
第一个样例中, 时可以使用以下策略。
若 Algosia 有 5、7 或 10 张梅花牌,她先提出合同 1:
- 若 Bajtek 有 6 张,他提出合同 2。此时 Algosia 若有 5 张,就提出合同 3,由 Bajtek 接受,两人共 11 张;若她有 7 或 10 张,就提出合同 4,由 Bajtek 接受,两人共 13 或 16 张。
- 若 Bajtek 有 2 张,他提出合同 3,Algosia 接受。两人共 7、9 或 12 张。
- 若 Bajtek 有 9 张,他提出合同 4,Algosia 接受。两人共 14、16 或 19 张。
若 Algosia 有 1 或 12 张梅花牌,她先提出合同 2。无论 Bajtek 有多少张,他都提出合同 3。Algosia 若有 1 张,就接受,两人共 3、7 或 10 张;若她有 12 张,就提出合同 4,由 Bajtek 接受,两人共 14、18 或 21 张。
可以证明 时不存在保证成功的策略。
第二个样例中,。Algosia 提出合同 ,Bajtek 接受即可。