Минимизация последовательности
Дана последовательность из
n чисел . Требуется привести её к минимальному виду. Последовательность можно лексикографически уменьшить, меняя местами два разрешённых элемента. Количество обменов не ограничено. При этом существуют пары индексов, которые можно менять между собой, а есть такие, которые менять нельзя.Лексикографическое сравнение двух последовательностей
Последовательность лексикографически меньше последовательности тогда и только тогда, когда существует такое целое число
k (1 ≤ k ≤ n), что , , …, и . Иными словами, лексикографическая разница определяется первым индексом k, на котором , при условии, что все предыдущие элементы совпадают.Имея матрицу разрешённых обменов, необходимо определить, какую лексикографически наименьшую последовательность можно получить из исходной.
Входные данные
В первой строке входных данных содержится одно целое число
n (1 ≤ n ≤ 300).Во второй строке записаны
n чисел (1 ≤ ≤ n), разделённых пробелами, которые образуют исходную последовательность. Все числа в ней различны.В следующих
n строках содержится по n символов 0 или 1, определяющих, разрешён ли обмен между элементами под номерами i и j. Если в позиции строки i и столбца j стоит 1, значит элементы i-го и j-го индексов можно поменять местами. Если там 0, то такой обмен не допускается.Выходные данные
Программа должна вывести лексикографически наименьшую последовательность, которую можно получить из заданной.
Примеры
Input | Входные данные |
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 |
Пояснение
- Можно выполнить следующие перестановки:
- ↔ ⇒ 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