全国信息学奥林匹克联赛（NOIP2012）复赛 提高组 day1 第 3页 共 7页 【输出】 输出文件名为 vigenere.out。 输出共 1行，一个字符串，表示输入密钥和密文所对应的明文。 【输入输出样例】 vigenere.in vigenere.out CompleteVictory Yvqgpxaimmklongnzfwpvxmniytm Wherethereisawillthereisaway 【数据说明】 对于 100%的数据，输入的密钥的长度不超过 100，输入的密文的长度不超过 1000，且 都仅包含英文字母。 2．国王游戏 (game.cpp/c/pas) 【问题描述】 恰逢 H国国庆，国王邀请 n位大臣来玩一个有奖游戏。首先，他让每个大臣在左、右 手上面分别写下一个整数，国王自己也在左、右手上各写一个整数。然后，让这 n位大臣排 成一排，国王站在队伍的最前面。排好队后，所有的大臣都会获得国王奖赏的若干金币，每 位大臣获得的金币数分别是：排在该大臣前面的所有人的左手上的数的乘积除以他自己右 手上的数，然后向下取整得到的结果。 国王不希望某一个大臣获得特别多的奖赏，所以他想请你帮他重新安排一下队伍的顺序， 使得获得奖赏最多的大臣，所获奖赏尽可能的少。注意，国王的位置始终在队伍的最前面。 【输入】 输入文件为 game.in。 第一行包含一个整数 n，表示大臣的人数。 第二行包含两个整数 a和 b， 之间用一个空格隔开， 分别表示国王左手和右手上的整数。 接下来 n行，每行包含两个整数 a和 b，之间用一个空格隔开，分别表示每个大臣左手 和右手上的整数。 【输出】 输出文件名为 game.out。 输出只有一行，包含一个整数，表示重新排列后的队伍中获奖赏最多的大臣所获得的 金币数。 全国信息学奥林匹克联赛（NOIP2012）复赛 提高组 day1 第 4页 共 7页 【输入输出样例】 game.in game.out 3 1 1 2 3 7 4 4 6 2 【输入输出样例说明】 按 1、2、3号大臣这样排列队伍，获得奖赏最多的大臣所获得金币数为2； 按 1、3、2这样排列队伍，获得奖赏最多的大臣所获得金币数为2； 按 2、1、3这样排列队伍，获得奖赏最多的大臣所获得金币数为2； 按 2、3、1这样排列队伍，获得奖赏最多的大臣所获得金币数为9； 按 3、1、2这样排列队伍，获得奖赏最多的大臣所获得金币数为2； 按 3、2、1这样排列队伍，获得奖赏最多的大臣所获得金币数为9。 因此，奖赏最多的大臣最少获得 2个金币，答案输出 2。 【数据范围】 对于 20%的数据，有 1≤ n≤ 10，0 < a、b < 8； 对于 40%的数据，有 1≤ n≤20，0 < a、b < 8； 对于 60%的数据，有 1≤ n≤100； 对于 60%的数据，保证答案不超过 109； 对于 100%的数据，有 1 ≤ n ≤1,000，0 < a、b < 10000。 3．开车旅行 (drive.cpp/c/pas) 【问题描述】 小 A和小 B决定利用假期外出旅行，他们将想去的城市从 1到 N编号，且编号较小的 城市在编号较大的城市的西边，已知各个城市的海拔高度互不相同，记城市i的海拔高度为 Hi，城市 i 和城市 j 之间的距离 d[i,j]恰好是这两个城市海拔高度之差的绝对值，即 d[i, j] = |𝐻𝑖 − 𝐻𝑗 |。 旅行过程中，小 A和小 B轮流开车，第一天小 A开车，之后每天轮换一次。他们计划 选择一个城市 S作为起点，一直向东行驶，并且最多行驶 X公里就结束旅行。小 A和小 B 的驾驶风格不同，小 B总是沿着前进方向选择一个最近的城市作为目的地，而小 A总是沿 着前进方向选择第二近的城市作为目的地（注意：本题中如果当前城市到两个城市的距离 相同，则认为离海拔低的那个城市更近） 。 如果其中任何一人无法按照自己的原则选择目的 城市，或者到达目的地会使行驶的总距离超出 X公里，他们就会结束旅行。 在启程之前，小 A想知道两个问题： 1．对于一个给定的 X=X0，从哪一个城市出发，小 A开车行驶的路程总数与小 B行驶 的路程总数的比值最小（如果小 B的行驶路程为 0，此时的比值可视为无穷大，且两个无穷