APPIATTISCI

PROBLEMA
 

Questo passatempo è basato su una serie di N pile, ognuna delle quali può contenere uno o più mattoncini (vedi Figura 1). Le pile sono identificate dai numeri interi da 1 a N. Una mossa di questo gioco consiste in una coppia data dal numero di una pila, diciamo p, e da un altro numero positivo, diciamo m. Quando si effettua questa mossa, m mattoncini vengono trasferiti dalla pila p a ciascuna delle pile adiacenti (si veda la Figura 2 per un esempio). La pila p ha due vicini, p-1 e p+1 se 1<p<N, il solo vicino 2 se p=1, e il solo vicino N-1 se p=N. Notate che per poter fare la mossa indicata, la pila p deve contenere almeno 2m mattoncini se ha due vicini, e almeno m mattoncini se ha un solo vicino.

L'obiettivo del gioco è di "appiattire" tutte le pile, cioè di fare in modo che tutte contengano lo stesso numero di mattoncini, facendo il minor numero possibile di mosse. Se ci sono più soluzioni, se ne deve comunque riportare una sola.
 
 
FIGURE1 FIGURE1
Figura 1. Cinque pile con 0, 7, 8, 1 e 4 mattoncini.  Figura 2. Configurazione assunta dopo la mossa: p=2, m=2.

ASSUNZIONI

     
  • E' garantito che sia possibile appiattire le pile con al più 10000 mosse.
  • 2 <= N <= 200
  • 0 <= Ci <= 2000 dove Ci  dove i è il numero di mattoncini nella pila i all'inizio del gioco (1 <= i <= N).
INPUT

L'input è contenuto in un file flat.inp che contiene due righe.

     
  • La prima riga contiene il numero N di pile. 
  • Sulla seconda riga ci sono N interi, l'i-esimo dei quali è l'intero non negativo Ci. 
Questi ultimi interi sono separati da uno spazio bianco.

OUTPUT

L'output va prodotto su un file di nome flat.out..

     
  • La prima riga contiene il numero di mosse. (Chiameremo questo valore M.) 
  • Ciascuna delle seguenti M righe contiene due interi che rappresentano una mossa, separati da uno spazio: p, m. Il primo intero identifica una pila e il secondo è il numero di mattoni specificato per la mossa.
L'ordine delle mosse nel file è l'ordine con cui le mosse devono essere eseguite: quindi la prima mossa sarà quella scritta sulla seconda riga del file di output, e così via.
 
 

ESEMPIO

flat.inp:
  
5

0 7 8 1 4

flat.out
  
5

5 2

3 4

2 4

3 1

4 2

 

NOTA SULLA VALUTAZIONE

Il programma dovrà terminare la propria esecuzione entro 3 secondi.

Per avere un punteggio pieno, A, per un file di test, il numero di mosse prodotte, x, deve essere minore o uguale al numero B di mosse previste dal programma di valutazione (si noti che B non è necessariamente il minimo numero di mosse possibile: in effetti, B è scelto seguendo una semplice strategia senza mosse ridondanti). E' possibile ottenere un punteggio parziale, calcolato arrotondando all'intero più vicino il valore ottenuto secondo la seguente formula:
 
A se x < B
2*A* (3/2 * B - x) /B se B < x < 3/2*B 
0  if x > 3/2*B 

Soluzione

Euristica (vedi codice).