Minimizzare la Sequenza
Data una sequenza di
n numeri , l’obiettivo è minimizzarla. È possibile rendere la sequenza lessicograficamente minima scambiando due elementi ammessi della sequenza. Sei autorizzato a effettuare tutti gli scambi necessari. Tuttavia, non tutte le coppie di indici possono essere scambiate: soltanto alcuni accoppiamenti specificati sono permessi.Confronto lessicografico di due sequenze
Una sequenza è considerata lessicograficamente più piccola di un’altra sequenza se e solo se esiste un intero
k (1 ≤ k ≤ n) tale che , , …, e . In altre parole, esiste un indice k per cui , mentre tutti i numeri precedenti all’indice k sono uguali.Sulla base della matrice che specifica quali scambi sono ammessi, devi determinare la sequenza lessicograficamente più piccola che si può ottenere a partire da quella iniziale.
Input
La prima riga dell’input contiene un singolo intero
n (1 ≤ n ≤ 300).La riga successiva contiene
n interi separati da spazi (1 ≤ ≤ n) che rappresentano la sequenza iniziale, in cui tutti i numeri sono diversi.Le successive
n righe contengono n zeri e uno che indicano se lo scambio tra due indici è ammesso. Se il valore nella riga i e nella colonna j è 1, significa che lo scambio tra gli elementi all’indice i e j è ammesso. Se il valore è 0, lo scambio non è consentito.Output
Il programma deve stampare la sequenza lessicograficamente più piccola che si può ottenere da quella data.
Esempi
Input | Output |
5
4 2 1 5 3
00100
00011
10010
01101
01010 | 1 2 3 4 5 |
7
5 2 4 3 6 7 1
0001001
0000000
0000010
1000001
0000000
0010000
1001000 | 1 2 4 3 6 7 5 |
Spiegazione
- Possiamo effettuare i seguenti scambi:
- ↔ ⇒ 1 2 4 5 3
- ↔ ⇒ 1 2 4 3 5
- ↔ ⇒ 1 2 3 4 5
- ↔ ⇒ 1 2 4 5 3
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB