IOI'94 - Giorno 2 - Problema 2: Gli autobus

Un uomo arriva ad una fermata d'autobus alle 12:00, e vi rimane per il periodo 12:00-12:59. La fermata viene usata da un certo numero di linee di autobus. L'uomo prende nota degli istanti di arrivo degli autobus, che sono dati come input del problema.

Gli autobus di una certa linea arrivano a intervalli regolari dalle 12:00 alle 12:59.
Gli istanti di arrivo sono numeri interi fra 0 e 59.
Ogni autobus si ferma almeno due volte durante l'ora.
Il numero di linee è <=17.
Autobus di linee diverse possono arrivare nello stesso momento.
Diverse linee di autobus possono avere lo stesso istante di prima fermata e/o la stessa frequenza. Se due linee di autobus hanno lo stesso istante di prima intervata e intervallo, gli istanti di fermata vengono comunque presentati come distinti.

Si trovi il minimo numero di linee di autobus che soddisfino l'input. Per ogni linea, si dia l'istante di prima fermata e la frequenza (cioè, il tempo che intercorre fra un arrivo e il successivo).

Dati di input

Il file di input, INPUT.TXT, contiene un numero n (n<=300) che indica quanti arrivi di autobus sono stati registrati, seguito dai tempi di arrivo in ordine crescente. Nel nostro esempio:

17
0 3 5 13 13 15 21 26 27 29 37 39 39 45 51 52 53

Dati di output

I risultati vanno scritti sul file OUTPUT.TXT con una riga per ciascuna linea di autobus. Ogni linea contiene l'istante del primo arrivo e la frequenza, in minuti. L'ordine in cui compaiono le linee non è importante; se ci sono più soluzioni, se ne deve comunque produrre una sola. Nel nostro esempio:

0 13
3 12
5 8