【题目描述】

在所有的N位数中，有多少个数中有偶数个数字3？由于结果可能很大，你只需要输出这个答案对12345取余的值。

比如：在所有的2位数字，包含0个3的数有72个，包含2个3的数有1个，共73个。（请注意：1位数指1~9这9个数，不包含数字0）

【输入描述】

一个整数N（1<=N<=1000）

【输出描述】

N位数中含有偶数个数组3的个数

【样例输入】

2

【样例输出】

73

说明

输入一个$n$行$m$列的数组，输出他的转置，具体来说

输出的第$i$行第$j$个数字，应是输入的第$\mathrm{<br><br>}$j行第$i$个数字。

$\mathrm{<br><br>}$1≤n≤20000;1≤m≤20000;1≤n∗m≤20000;1≤a[i][j]≤1000

特别注意，你并不能声明一个两维的大小都是$20000$二维数组。（数组不能太大，二维数组的大小是两维的乘积）

二维数组本质上和一维数组等价，所以你只需要一个大小为$20000$的一维数组。

输入格式

第一行两个整数$n$, $m$表示数组的行数和列数;

接下来$\mathrm{<br><br>}$n行，每行$m$个整数表示数组内容。

输出格式

第一行先输出$m$, $n$。 接下来输出转置的结果，共$m$行$n$列。 其中第$i$行第$\mathrm{<br><br>}$j个数字，应是输入的第$j$j行第$i$个数字。

样例

3 2  1 2  3 4  5 6

2 3  1 3 5  2 4 6

题目描述

在一个拥有无限大小的二维平面的原点处，有一个舞蹈机器人，这个机器人将在这个平面上跳舞。

这个机器人每次可以向自己的前方移动一个单位的长度，由于它需要在移动的过程中跳舞，因此，舞蹈机器人每移动一次，就必须向左或右方向旋转 ，即如果此次机器人往上或下方向进行了一次移动，那么，下一次就只能往左或右方向进行一次移动。最开始时，它可以选择上下左右四个方向中的任意一个作为初始方向。

现在，机器人根据上述规则一共移动了 步，请问，机器人最终可以到达多少个不同的终点？机器人到达终点时的方向可以忽略。

输入格式

输入共一行，包含一个整数 ，表示机器人总共移动的步数。

输出格式

输出共一行，包含一个整数，表示机器人最终能够到达的不同终点的个数。

样例 1 输入

1

样例 1 输出

4

样例 1 解释

因为总共只移动了一次，则有上下左右四个方向的四个答案。

样例 2 输入

2

样例 2 输出

4

样例 2 解释

因为总共会移动两次，且第二次的方向必须向左或向右旋转 ，因此，最终能到的终点只有原点左上、右上、左下、右下四个与原点距离为 的点。

样例 3 输入

3

样例 3 输出

12

样例 4 输入

597

样例 4 输出

179400

【题目描述】

我们大多都有在银行排队的经历，唉，那坑爹的排队啊！现在就让我们来算算我们这些客户平均需要等多久吧。

每天刚开始时银行会开m个窗口来为我们total个客户办理业务，当有客户需要办理业务时，先选择可以办理业务的窗口，如果有多个窗口可以办理业务就选择空闲时间最长的窗口，如果有多个窗口空闲的时间一样长，则选择序号小的窗口办理业务。假设我们每个人来到的时间和办理业务所需要的时间（为了简化问题，采用整数表示时间）都知道了。现在请你算算我们平均需要等待多久呢？

【输入描述】

有多组测试数据，每组数据开始有两个正整数m(<20)和total(<200)，后面有total对整数，对应客户先后到来的时间以及办理业务所需的时间。

【输出描述】

【样例输入】

2 6 1 3 4 1 5 3 9 2 13 4 13 3  3 14 0 3 2 2 2 4 5 4 7 2 11 3 12 3 12 4 12 1 13 3 15 4 19 1 22 3 23 2  2 5 0 6 0 5 0 6 7 1 7 2

【样例输出】

0.00  0.29  1.20

【题目描述】

仙境的居民们决定举办一场程序设计区域赛。裁判委员会完全由自愿组成，他们承诺要组织一次史上最公正的比赛。他们决定将选手的电脑用星形拓扑结构连接在一起，即将它们全部连到一个单一的中心服务器。为了组织这个完全公正的比赛，裁判委员会主席提出要将所有选手的电脑等距离地围绕在服务器周围放置。为购买网线，裁判委员会联系了当地的一个网络解决方案提供商，要求能够提供一定数量的等长网线。裁判委员会希望网线越长越好，这样选手们之间的距离可以尽可能远一些。

该公司的网线主管承接了这个任务。他知道库存中每条网线的长度（精确到厘米），并且只要告诉他所需的网线长度（精确到厘米），他都能够完成对网线的切割工作。但是，这次，所需的网线长度并不知道，这让网线主管不知所措。

你需要编写一个程序，帮助网线主管确定一个最长的网线长度，并且按此长度对库存中的网线进行切割，能够得到指定数量的网线。

【输入描述】

第一行包含两个整数N和K，以单个空格隔开。N（1 ≤ N ≤ 10000）是库存中的网线数，K（1 ≤ K ≤ 10000）是需要的网线数量。

接下来N行，每行一个数，为库存中每条网线的长度（单位：米）。所有网线的长度至少1m，至多100km。输入中的所有长度都精确到厘米，即保留到小数点后两位。

【输出描述】

网线主管能够从库存的网线中切出指定数量的网线的最长长度（单位：米）。必须精确到厘米，即保留到小数点后两位。

若无法得到长度至少为1cm的指定数量的网线，则必须输出“0.00”（不包含引号）。

【样例输入】

4 11  8.02  7.43  4.57  5.39

【样例输出】

2.00

【题目描述】

k路归并问题

把k个有序表合并成一个有序表。

元素共有n个。

【输入描述】

读入K。接下来K行。每i行第一个数为Ci表示接下来这一行有Ci个数，表示第i个序列。

总数小于100000。

【输出描述】

【样例输入】

6  3 1 2 3  3 4 5 6  3 7 10 13  3 8 11 14  3 9 12 15  3 0 16 17

【样例输出】

0  1  2  3  4  5  6  7  8  9  10  11  12  13  14  15  16  17

【题目描述】

每年奶牛们都要举办各种特殊版本的跳房子比赛，包括在河里从一个岩石跳到另一个岩石。这项激动人心的活动在一条长长的笔直河道中进行，在起点和离起点L远 (1 ≤ L≤ 1,000,000,000) 的终点处均有一个岩石。在起点和终点之间，有N (0 ≤ N ≤ 50,000) 个岩石，每个岩石与起点的距离分别为Di (0 < Di < L)。

在比赛过程中，奶牛轮流从起点出发，尝试到达终点，每一步只能从一个岩石跳到另一个岩石。当然，实力不济的奶牛是没有办法完成目标的。

农夫约翰为他的奶牛们感到自豪并且年年都观看了这项比赛。但随着时间的推移，看着其他农夫的胆小奶牛们在相距很近的岩石之间缓慢前行，他感到非常厌烦。他计划移走一些岩石，使得从起点到终点的过程中，最短的跳跃距离最长。他可以移走除起点和终点外的至多M (0 ≤ M ≤ N) 个岩石。

请帮助约翰确定移走这些岩石后，最长可能的最短跳跃距离是多少？

【输入描述】

第一行包含三个整数L, N, M，相邻两个整数之间用单个空格隔开。

接下来N行，每行一个整数，表示每个岩石与起点的距离。岩石按与起点距离从近到远给出，且不会有两个岩石出现在同一个位置。

【输出描述】

【样例输入】

25 5 2  2  11  14  17  21

【样例输出】

4

【题目描述】

Joe觉得云朵很美，决定去山上的商店买一些云朵。商店里有n朵云，云朵被编号为1，2，…，n，并且每朵云都有一个价值。但是商店老板跟他说，一些云朵要搭配来买才好，所以买一朵云则与这朵云有搭配的云都要买。

但是Joe的钱有限，所以他希望买的价值越多越好。

【输入描述】

第1行n，m，w，表示n朵云，m个搭配，Joe有w的钱。

第2~n+1行，每行ci，di表示i朵云的价钱和价值。

第n+2~n+1+m行，每行ui，vi，表示买ui就必须买vi，同理，如果买vi就必须买ui。

【输出描述】

【样例输入】

5 3 10  3 10  3 10  3 10  5 100  10 1  1 3  3 2  4 2

【样例输出】

1

【数据范围】

30%的数据保证：n≤100；

50%的数据保证：n≤1,000；m≤100；w≤1,000；

100%的数据保证：n≤10,000；0≤m≤5000；w≤10,000。

【题目描述】

某个地区有n(n<=1000)个犯罪团伙，当地警方按照他们的危险程度由高到低给他们编号为1-n，他们有些团伙之间有直接联系，但是任意两个团伙都可以通过直接或间接的方式联系，这样这里就形成了一个庞大的犯罪集团，犯罪集团的危险程度由集团内的犯罪团伙数量唯一确定，而与单个犯罪团伙的危险程度无关（该犯罪集团的危险程度为n）。现在当地警方希望花尽量少的时间（即打击掉尽量少的团伙），使得庞大的犯罪集团分离成若干个较小的集团，并且他们中最大的一个的危险程度不超过n/2。为达到最好的效果，他们将按顺序打击掉编号1到k的犯罪团伙，请编程求出k的最小值。

【输入描述】

【输出描述】

【样例输入】

7  2 2 5  3 1 3 4  2 2 4  2 2 3  3 1 6 7  2 5 7  2 5 6

【样例输出】

1