#P17739. [ICPC 2019 Xuzhou R] Interesting game
[ICPC 2019 Xuzhou R] Interesting game
题目描述
Amy 和 Bob 是好朋友。今天他们想玩一个游戏。
游戏过程如下:
- 总共有 个物品。第 个物品对 Amy 来说价值为 ,对 Bob 来说价值为 。
- Bob 先从游戏中移除 个物品,这样两人都不能选择这些物品。()
- Amy 首先选择一个物品,假设她拿了第 个物品,则她得到 分。
- Bob 再选择一个物品,假设他拿了第 个物品,则他得到 分。
- 游戏结束。
现在他们想知道,如果双方都采取最优策略, 的值是多少。
(Amy 希望 尽可能大,Bob 希望 尽可能小)
请你对于 从 到 的每个取值,帮助他们计算出相应的值。
输入格式
第一行包含一个整数 ()—— 物品的数量。
接下来的 行,每行包含两个整数 和 ()—— 表示第 个物品对 Amy 的价值为 ,对 Bob 的价值为 。
输出格式
输出 个整数,每行一个。
第 行表示当 Bob 恰好移除 个物品时, 的值。()
5
2 2
3 2
4 4
5 6
6 6
0
0
0
0
3
4 100
5 98
1 100
-95
-96
提示
翻译由 DeepSeek V4 Pro 完成