[IOI1999]纸牌问题

Grade Open Time Friday, 19 September 2014, 10:07 am
Discount 0.8 Time Discount Friday, 26 September 2014, 10:07 am
Allow late Yes Close Time Friday, 26 September 2014, 10:07 am
Input file flat.in Output file flat.out

【题目描述】


这是一个均分纸牌的游戏。有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