Minimiser la séquence
Étant donné une séquence de
n nombres , l’objectif est de la rendre aussi petite que possible. Une séquence peut être minimisée de manière lexicographique en échangeant deux éléments autorisés de la séquence. Vous pouvez effectuer autant d’échanges que nécessaire. Cependant, il existe certaines paires d’indices dont l’échange est permis et d’autres non.Comparaison lexicographique de deux séquences
Une séquence est plus petite (au sens lexicographique) qu’une séquence si et seulement si il existe un entier
k (1 ≤ k ≤ n) tel que , , …, et . Autrement dit, à l’indice k, on trouve , et tous les éléments précédant k sont identiques dans les deux séquences.Étant donné la matrice indiquant quels échanges sont autorisés, il s’agit de déterminer la plus petite séquence (au sens lexicographique) que l’on peut obtenir à partir de la séquence initiale.
Entrée
La première ligne de l’entrée contient un entier
n (1 ≤ n ≤ 300).La ligne suivante contient
n entiers séparés par des espaces (1 ≤ ≤ n) représentant la séquence initiale, où tous les nombres sont différents.Les
n lignes suivantes contiennent n zéros et des uns, indiquant si l’échange entre deux indices est autorisé. Si la valeur à la ligne i et la colonne j vaut 1, cela signifie que l’échange entre les éléments d’indices i et j est permis. Si la valeur vaut 0, l’échange n’est pas autorisé.Sortie
Le programme doit afficher la plus petite séquence (au sens lexicographique) qu’il est possible d’obtenir à partir de la séquence initiale.
Exemples
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 |
Explication
- On peut effectuer les échanges suivants :
- ↔ ⇒ 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