Minimieren der Sequenz
Gegeben ist eine Sequenz von
n Zahlen , die Sie minimieren sollen. Um eine Sequenz lexikografisch zu minimieren, können zwei erlaubte Elemente der Sequenz miteinander vertauscht werden. Sie dürfen beliebig viele Vertauschungen vornehmen. Allerdings dürfen nur bestimmte Indizes miteinander getauscht werden, während andere nicht erlaubt sind.Lexikografischer Vergleich zweier Sequenzen
Eine Sequenz ist genau dann lexikografisch kleiner als eine Sequenz , wenn es ein
k (1 ≤ k ≤ n) gibt, sodass , , …, und . Anders ausgedrückt gibt es einen Index k, bei dem gilt, während alle vorhergehenden Elemente gleich sind.Anhand der Matrix der erlaubten Vertauschungen sollen Sie die lexikografisch kleinstmögliche Sequenz ermitteln, die sich aus der Anfangssequenz ableiten lässt.
Eingabe
Die erste Zeile der Eingabe enthält eine einzelne ganze Zahl
n (1 ≤ n ≤ 300).In der nächsten Zeile befinden sich
n durch Leerzeichen getrennte ganze Zahlen (1 ≤ ≤ n), die die Anfangssequenz repräsentieren. Dabei sind alle Zahlen unterschiedlich.Die folgenden
n Zeilen enthalten n Nullen und Einsen, die angeben, ob ein Tausch zwischen zwei Indizes erlaubt ist. Steht an Zeile i und Spalte j eine 1, so bedeutet das, dass der Tausch der Elemente an Position i und j erlaubt ist. Steht dort eine 0, ist ein Tausch nicht erlaubt.Ausgabe
Das Programm soll die lexikografisch kleinstmögliche Sequenz ausgeben, die sich aus der gegebenen Anfangssequenz ableiten lässt.
Beispiele
Eingabe | Ausgabe |
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 |
Erklärung
- Wir können folgende Vertauschungen durchführen:
- ↔ ⇒ 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