IOI '99 - Antalya-Belek, Turkey
A solitaire game is played given a row of piles where each pile contains zero or more chips. See Figure 1. Piles are identified by integers through . In a move of this game you point to a pile, say , and specify a number, say . Then chips are transferred from the pile to each of its neighboring piles. See Figure 2 for an example. Pile has two neighbors, and if , and the neighbor if , and the neighbor if . Note that to be able to make such a move the pile must have at least chips if it has two neighbors, and it must have at least chips if it has only one neighbor.
The object of the game is to "flatten" all piles, that is make them have the same number of chips, by making as small as possible number of moves. In case there is more than one solution you are required to report only one of them.
Figure 1. Five piles with and chips. | Figure 2. Configuration of same piles after a move: . |
Input Specification
The first line contains the integer .
The second line contains integers, ,
where is the number of chips in the pile
( at the start of the game, but not necessarily later
on.)
It is guaranteed that it is possible to flatten the given piles, and that doing so will require no more than moves.
Output Specification
The first line should contain the number of moves used by your
solution.
Each of the following lines should describe one move as two
space-separated integers and . should be the id number of the
pile and the number of chips transferred to each adjacent pile (not
necessarily the total number of chips transferred.) Of course, the moves
should be in the correct order in the output file.
Sample Input
5
0 7 8 1 4
Sample Output
5
5 2
3 4
2 4
3 1
4 2
Scoring
The judges have set a target number of moves for each test case. If your program supplies a correct solution that uses moves, your score, a number between 0 and 1, will be determined as follows:
If your program supplies an incorrect solution, you will receive a score of zero for that test case.
Comments