最近的斐波那契数

斐波那契数列 Fn 的定义为：对 n ≥ 0 有 Fn+2 = Fn+1 + Fn，初始值为 F0 = 0 和 F1 = 1。所谓与给定的整数 N 最近的斐波那契数是指与 N 的差之绝对值最小的斐波那契数。

本题就请你为任意给定的整数 N 找出与之最近的斐波那契数。

时间限制：1000

内存限制：65536

输入

输入在一行中给出一个正整数 N（≤ 108）。

输出

在一行输出与 N 最近的斐波那契数。如果解不唯一，输出最小的那个数。

样例输入

305

样例输出

233

提示

样例解释 部分斐波那契数列为 { 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, ... }。可见 233 和 377 到 305 的距离都是最小值 72，则应输出较小的那个解。

构造性证明

关于数学定理证明，也有高下之分。最暴力的证明方法是“构造性证明”，即当需要证明某种解存在时，直接把解构造出来，而不是仅通过推理证明解之存在。

下面有一个定理：

设 ai（i=1, … , 5）均为正实数。则一定存在 4 个互不相同的下标 i、j、k、l，使得 |ai / aj - ak / al| < 1/2。

作为程序员，就请你编写程序构造出正确的下标，验证这个结论。

时间限制：1000

内存限制：65536

输入

输入在一行中顺序给出 5 个正实数。为保证计算中不产生浮点溢出，我们令输入的数字在 [10-10, 1010] 区间内，且小数点后不超过 10 位小数。

输出

在一行中首先输出使得定理结论成立的下标有多少套，随后输出最小的一套下标。数字间以 1 个空格分隔，行首尾不得有多余空格。 注：所谓下标集 {i1, …, i4} 小于下标集 {j1, …, j4}，是指存在 1 ≤ k ≤ 4 使得 il=jl 对所有 l < k 成立，且 ik < jk。

样例输入

3.12 5.27 0.0007 9825.4413 10

样例输出

18 1 4 3 2

提示

样例解释： 易验证 |a1/a4-a3/a2|=|3.12/9825.4413 - 0.0007/5.27| < 1/2。满足条件的解有 18 个，例如 5、4、3、2 就是另一套解。

环形公路出口

一条环形高速路上有 N 个出口。给定任意一对出口，请你算出这两个出口之间的最短距离。

时间限制：1000

内存限制：65536

输入

输入第一行给出区间 [3,105] 内的整数 N，以及 N 个整数距离 D1 D2 … DN，其中 Di 是第 i 和第 i+1 个出口之间的距离，DN 是第 N 和第 1 个出口之间的距离。同行数字间以空格分隔。 第二行给出正整数 M (≤ 104)。随后 M 行，每行给出一对出口的编号（出口从 1 到 N 顺序编号）。题目保证公路全长不超过 107。

输出

输出 M 行，每行给出对应输入的一对出口之间的最短距离。

样例输入

5 1 2 4 14 9

3

1 3

2 5

4 1

样例输出

3

10

7

子串和子列

子串是一个字符串中连续的一部分，而子列是字符串中保持字符顺序的一个子集，可以连续也可以不连续。例如给定字符串 atpaaabpabtt，pabt 是一个子串，而 pat 就是一个子列。

现给定一个字符串 S 和一个子列 P，本题就请你找到 S 中包含 P 的最短子串。若解不唯一，则输出起点最靠左边的解。

时间限制：1000

内存限制：65536

输入

输入在第一行中给出字符串 S，第二行给出 P。S 非空，由不超过 104 个小写英文字母组成；P 保证是 S 的一个非空子列。

输出

在一行中输出 S 中包含 P 的最短子串。若解不唯一，则输出起点最靠左边的解。

样例输入

atpaaabpabttpcat

pat

样例输出

pabt

拼大数

如何随机生成一个有 n 位数的大数呢？一种方法是，找到 n 个小朋友，每人发一张卡片，卡片一面写着编号（这里假设小朋友们从 1 到 n 编号），另一面让他们随便写下一个 1 位数字。然后让小朋友们把自己的卡片在墙上钉成一排，要求一张挨着一张，按他们的编号升序排列，显示他们自己写的数字。

但是，让十万个孩子都按指令行动，可太难了。结果是卡片乱七八糟满墙都是，有些甚至显示的不是正确的面。例如第 23 号小朋友在卡片上写了 8，我们应该在墙上看到 8，但是却看到了 23…… 你的任务就是把这些卡片整理好，得到我们真想要拼成的大数。

时间限制：6000

内存限制：65536

输入

输入第一行给出一个正个整数 n (≤ 105)，随后 n 行，每行按 n1 n2的格式给出一张卡片两面的数字。

输出

在一行中输出我们真想要拼成的 n 位大数。 如果卡片两面都是 1 位数，那么就很难说哪个数字是编号，哪个数字是小朋友自己写的，所以解可能是不唯一的。这时候需要输出能得到的最小的数字。

样例输入

12

7 11

8 9

3 1

2 12

4 6

10 0

5 1

2 5

6 8

1 4

7 2

9 3

样例输出

359114268072