收费站在哪里

在一条高速公路上，如果已知 n 座收费站的位置 x1,x2,… ,xn（不妨假设 0=x1 ≤ x2 ≤ … ≤ xn），就很容易算出一共有 n(n-1)/2 个距离的值。而比较困难的问题是，在收集了一大堆过路费发票后，我们筛选出了 n(n-1)/2 个距离的值，现在想知道收费站都分布在哪里？

当然对应一组距离值，可能有多组解，你只要输出任何一个即可。

时间限制：1000

内存限制：65536

输入

输入第一行给出正整数 m（< 50），即距离值的数量。 随后一行给出 m 个距离，均为 int 范围内的正整数。

输出

按坐标值升序列出所有收费站的位置，其中 x1=0。同行数字间以 1 个空格分隔，行首尾不得有多余空格。 注：题目保证所有坐标为 int 范围内的非负整数。

样例输入

10
3 4 6 8 1 3 5 2 4 2

样例输出

0 2 4 5 8

从A到B

我们来做一个数字游戏，通过一系列操作把一个数字 A 变成另一个数字 B。设当前数字是 X，规定每次操作可以从以下 3 种里面选一种进行：

- X = X + 1

- X = X - 1

- X = X × N

你的任务就是求出从 A 变成 B 至少需要多少步。

时间限制：1000

内存限制：65536

输入

每组输入包含多个测试用例。先给出一个整数 K（≤ 10），为测试用例的个数。随后 K 行，每行给出一个测试用例的三个整数：A、B、N，其中 -105 ≤ A, B ≤ 105，1 < N < 10。同行数字间以空格分隔。

输出

对每个测试用例，在一行中输出从 A 变成 B 至少需要多少步。

样例输入

3
3 11 2
-5 -12 3
-2 1000 7

样例输出

3
2
13

提示

样例解释： 第 1 组：(3 × 2 × 2)-1=11 第 2 组：(-5+1) × 3 = -12 第 3 组：(((-2+1+1+1+1+1)×7-1)×7+1+1+1)×7-1 = 1000

乘积的最大和

给定两组整数 A 和 B，你可以从 A 中任选一个整数，与 B 中任选的一个整数相乘。注意每个整数至多只能被选中 1 次。将这些乘积加起来，最大值能达到多少？

时间限制：10000

内存限制：65536

输入

输入第一行给出正整数 NA，为 A 组中整数的个数，随后一行给出 A 中的 NA 个整数；然后给出正整数 NB，为 B 组中整数的个数，随后一行给出 B 中的 NB 个整数。数据范围为 1 ≤ NA, NB ≤ 105，最大答案不超过 230。

输出

在一行中输出题面要求的乘积和的最大值。

样例输入

4
1 2 4 -1
4
7 6 -2 -3

样例输出

43

提示

样例解释： 43 = (-1)×(-3)+4×7+2×6

结绳

给定一段一段的绳子，你需要把它们串成一条绳。每次串连的时候，是把两段绳子对折，再如下图所示套接在一起。这样得到的绳子又被当成是另一段绳子，可以再次对折去跟另一段绳子串连。每次串连后，原来两段绳子的长度就会减半。

给定 n 段绳子的长度，你需要找出它们能串成的绳子的最大长度。

时间限制：1000

内存限制：65536

输入

每个输入包含 1 个测试用例。每个测试用例第 1 行给出正整数 n (2 ≤ n ≤ 104)；第 2 行给出 n 个正整数，即原始绳段的长度，数字间以空格分隔。所有整数都不超过104。

输出

在一行中输出能够串成的绳子的最大长度。结果向下取整，即取为不超过最大长度的最近整数。

样例输入

8
10 15 12 3 4 13 1 15

样例输出

14