L’ascensore di Hulk

Hulk ha perso il proprio posto di lavoro come uomo verde nel cinema, trovando lavoro in una grande azienda di recapito di pacchi, dove gestisce il magazzino per lo smistamento interno.
Il magazzino ha N piani per lo smistamento, con esattamente P pacchi per piano.

Ogni pacco è etichettato con un intero da 1 a N, a indicare la sua destinazione.
Per esempio, se sul piano i c’è un pacco con etichetta j, Hulk deve spostare tale pacco portandolo dal piano i al piano j per mezzo di un ascensore.

Le etichette sui vari pacchi sono tali che ci sono esattamente P pacchi con etichetta i, sparsi nei vari piani.
Conseguentemente, alla fine dello smistamento interno, ogni piano i conterrà esattamente P pacchi con etichetta i.

Dopo aver caricato e scaricato alcuni pacchi al piano i, Hulk effettua un movimento dell’ascensore, premendo il tasto UP (per andare al piano i+1 se i < N) oppure DOWN (per andare al piano i-1 se i > 1).
Non è però obbligato a caricare/scaricare ad ogni piano (anche se il movimento dell’ascensore deve essere comunque considerato).
Hulk, volendo, può spostare pacchi dal piano di partenza a uno o più piani intermedi, prima di raggiungere il piano di destinazione finale.
Infatti, l’uso di tappe intermedie gli permette una maggiore flessibilità nello smistamento, sfruttando anche il fatto che l’ascensore contiene M pacchi.

Hulk ha fretta di iniziare il suo solito trattamento radioattivo per diventare ancora più verde.
Aiutalo a effettuare pochi movimenti con l’ascensore!

Dati in Input

Il file input.txt contiene sulla prima riga i tre interi positivi N, P e M, separati da uno spazio.
Le successive N righe (per i = 1, 2, …, N) contengono ciascuna P numeri interi positivi in ordine non-decrescente (per es., 2 2 3 7 7 7 9…), separati da uno spazio e compresi tra 1 e N, a rappresentare le destinazioni dei pacchi dell’i-esimo piano.

Dati in Output

Il programma, dopo aver letto il file di input, deve scrivere K+1 righe nel file output.txt.
La prima riga contiene l’intero K che rappresenta il numero di movimenti effettuati da Hulk con l’ascensore.
Le K righe successive corrispondono ai K movimenti dell’ascensore.
Ogni riga descrive tale movimento riportando

1. una sequenza non-descrescente di M interi, ciascuno seguito da uno spazio separatore, per rappresentare gli M pacchi contenuti nell’ascensore immediatamente prima di muoversi verso il piano superiore o inferiore;
2. la lettera U oppure D (in MAIUSCOLO!) per indicare il movimento dell’ascensore verso il piano superiore (tasto UP) o inferiore (tasto DOWN), rispettivamente.

Nota per la risoluzione dell’esercizio

Non è richiesto di calcolare il numero ottimo S di movimenti ma di avvicinarsi il più possibile ad esso fornendo un valore K ≥ S (se la soluzione fornita è corretta!).
Negli esempi mostrati in seguito, vale K = S.
La differenza relativa in percentuale rispetto all’ottimo, D = (K – S)/S x 100, sarà utilizzata nella correzione degli esercizi per valutare i singoli file di input come segue:

• 6 punti se D = 0
• 4 punti se 0 < D ≤ 5
• 3 punti se 5 < D ≤ 15
• 2 punti se 15 < D ≤ 30
• 1 punto se 30 < D ≤ 50
• 0 punti se D > 50 oppure la risposta è errata.

Assunzioni

1. 2 ≤ N ≤ 128
2. 1 ≤ P ≤ 32
3. 1 ≤ M ≤ 16
4. K ≥ 2
5. Inizialmente l’ascensore si trova al piano 1 e contiene M pacchi tutti etichettati con la destinazione fittizia 0.
6. Inizialmente, tra i pacchi nel piano 1, ce ne è almeno uno avente come destinazione il piano N.
7. Durante i movimenti ci sono P pacchi per piano e M pacchi nell’ascensore (segue dal fatto che inizialmente si usano M pacchi con destinazione 0).
8. Alla fine l’ascensore deve essere riportato al piano 1 (vanno considerati gli eventuali movimenti per portarcelo) e deve contenere tutti i pacchi con destinazione fittizia 0.

Esempi

Nota