结绳

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

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

时间限制：1000

内存限制：65536

输入

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

输出

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

样例输入

8

10 15 12 3 4 13 1 15

样例输出

14

从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，其中 -10 ≤ A, B ≤ 10 ，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 ≤ 10^5，最大答案不超过230。

输出

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

样例输入

4

1 2 4 -1

4

7 6 -2 -3

样例输出

43

提示

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

输入

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

输出

按坐标值升序列出所有收费站的位置，其中 x1=0。同行数字间以 1 个空格分隔，行首尾不得有多余空格。

注：题目保证所有坐标为 int 范围内的非负整数。

样例输入

10

3 4 6 8 1 3 5 2 4 2

样例输出

0 2 4 5 8