La tavola rotonda di Camelot

 

A Camelot, nel periodo di maggior splendore, ogni amicizia è corrisposta.
Ogni cavaliere è amico di oltre la metà dei suoi compagni d’arme, ossia, se N è il numero dei cavalieri, ciascuno di essi può contare su almeno N/2 validi amici.

La tavola rotonda è disposta in un enorme salone, circondata da N sedie, con una sedia per cavaliere.
Com’è facilmente immaginabile, ogni cavaliere pretende di avere amici ai suoi due lati, altrimenti rifiuta di sedersi al tavolo.

Tutti contano su Mago Merlino per disporre i cavalieri intorno al tavolo nella soddisfazione generale di tutti.
Ma il poverino ha perso la formula magica per ottenere ciò in men che non si dica!

Aiuta Merlino, nei limiti delle tue possibilità, a disporre i cavalieri intorno al tavolo in modo che ogni cavaliere abbia degli amici ai suoi lati.

Dati in Input

Il file input.txt contiene nella prima riga l’intero N, il numero dei cavalieri della tavola rotonda.
I cavalieri sono numerati da 1 a N.

Ognuna delle successive N righe contiene una sequenza di N valori 0 oppure 1, separati da uno spazio.
La sequenza contenuta nell’i-esima di tali righe rappresenta le relazioni di amicizia del cavaliere numero i.
In particolare, il j-esimo valore in tale riga indica se i cavalieri i e j sono amici (valore=1) o meno (valore=0).

Poiché l’amicizia è sempre corrisposta, se il cavaliere i è amico del cavaliere j allora il cavaliere j è amico del cavaliere i.

Dati in Output

Il file output.txt deve contenere una sola riga contenente una sequenza di N numeri separati da uno spazio, per rappresentare la disposizione dei cavalieri attorno alla tavola rotonda.

• Il primo numero è sempre 1, a rappresentare il cavaliere numero 1.
• Il resto della sequenza è una permutazione dei numeri 2, 3, …, N (cioè una disposizione in un qualche ordine, senza ripetizioni).
• Per ogni coppia i e j di numeri adiacenti nell’intera sequenza, i cavalieri i e j devono essere amici.
• Inoltre, il cavaliere alla fine della sequenza deve essere amico del cavaliere numero 1, in quanto vicini di posto.

 

Assunzioni

• 1 < N < 4000

 

Valutazione delle soluzioni

• Non è richiesto di soddisfare le richieste di tutti i cavalieri (anche se ciò è sempre possibile).
• Il punteggio è quindi a scalare in base al numero di coppie di cavalieri che sono scontenti perché sono vicini di posto pur non essendo amici.
• 3 punti se tutti i cavalieri sono soddisfatti (nessuna coppia scontenta).
• 2 punti se una sola coppia è scontenta.
• 1 punto se il numero delle coppie scontente è compreso tra 2 e 10.
• 0 punti altrimenti (il numero di coppie scontente è superiore a 10).

 

Esempio