Minimizar a Sequência
Dada uma sequência de
n números , pretende-se minimizá-la. Para obter a forma lexicograficamente mínima, é possível efetuar trocas entre dois elementos permitidos da sequência. Podem ser realizadas tantas trocas quantas forem necessárias. No entanto, existem pares de índices que podem ser trocados entre si e outros que não podem.Comparação lexicográfica de duas sequências
Uma sequência é menor em termos lexicográficos do que outra sequência se e somente se existir um inteiro
k (1 ≤ k ≤ n) tal que , , …, e . Em outras palavras, há um índice k em que , enquanto todos os números anteriores a k são iguais.Dada a matriz de trocas permitidas, é necessário determinar qual é a menor sequência que pode ser obtida, em termos lexicográficos, a partir da sequência inicial.
Entrada
A primeira linha da entrada contém um único inteiro
n (1 ≤ n ≤ 300).A linha seguinte contém
n inteiros separados por espaço (1 ≤ ≤ n), representando a sequência inicial, em que todos os números são diferentes entre si.As próximas
n linhas contêm n valores 0 ou 1, indicando se é permitida a troca entre dois índices. Se o valor na linha i e coluna j for 1, significa que a troca entre os elementos nas posições i e j é permitida. Se for 0, então a troca não é permitida.Saída
O programa deve imprimir a menor sequência possível em ordem lexicográfica, obtida a partir da sequência dada.
Exemplos
Entrada | Saída |
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 |
Explicação
- Podemos realizar as seguintes trocas:
- ↔ ⇒ 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