OI题库

【题目描述】

这是一个均分纸牌的游戏。有N列纸牌，每列有纸牌若干张（可能是零张），如图1所示。纸牌列用从1到N的整数标号，1和N分别是纸牌列两端的标号。在移动纸牌时你需要指定一个确定的列P和一个确定的数字m。而后从p列上移动m张纸牌到每一个相邻的列上，参见图2．如果1＜p＜N的话，则p列有两个相邻的列，分别是p-1和p+1；如果p=1的话，则只有一个相邻列，其列号为2；如果P=N的话，则只有一个相邻列，其列号为N-1。

   注意，如果p列有两个相邻的列．则进行上述移动时，p列至少要有2m张纸牌；如果p列只有一个相邻的列，则进行这样的移动时p列就需要至少m张纸牌。

   这个游戏的目的是”均分”所有的纸牌列，使每列都有相同的纸牌数，而且用最少的移动达到这一目的。假定有超过一种符合上述要求的移动方法，你只需给出其中一种。

图1．五列纸牌，分别有0：7，8，1，4张纸牌     

图2．图1的纸牌列在执行完移动P=2，m=2后的状态

Ø 假设条件

u 最大的移动次数保证不多于10，000次。

u 2≤N≤200。

u 0≤Ci≤2000，在这里Ci是游戏开始时第i列的纸牌数（1≤I≤N）。

【输入格式】

输入有两行。

 第一行是纸牌的总列数N；

 第二行有N个整数，其中第i个数是Ci的值。

【输出格式】

第一行是移动的次数（称为M）。

以下M行每行包含两个整数，分别表示移动中的p和m。

   移动的输出次序必须和移动的执行次序相同。因此，第一次移动应该写在输出文件的第二行上。

【输入输出样例】

flat.in ：

 5

 0  7  8  1  4

flat.out：

5

5  2

3  4

2  4

3  1

4  2

【提示】

对于每个测试点，你的得分将由如下规则给出：

若你给出的操作序列不能均分纸牌，那么你在这个测试点得0分。

假设这个测试点的分值是A，你的答案步数是x，而标准答案的步数是B。

你的得分为：

A                                    if x<=B

2A(1.5B-x)/B                         if B<x<1.5B

0                                    if x>=1.5B

【来源】

IOI1999