अनुक्रम को न्यूनतम करना
n संख्याओं के अनुक्रम को दिया गया है, और आपका कार्य इसे यथासंभव छोटा (लेक्सिकोग्राफिक रूप से) करना है। लेक्सिकोग्राफिक रूप से किसी अनुक्रम को न्यूनतम करने के लिए, आप अनुक्रम के दो अनुमत तत्त्वों को अदल-बदल (swap) कर सकते हैं। आपको जितनी बार चाहें, अदल-बदल करने की अनुमति है। हालांकि, कुछ विशिष्ट इंडेक्स हैं जिनके बीच स्वैप की अनुमति है और कुछ के बीच नहीं।दो अनुक्रमों की लेक्सिकोग्राफिक तुलना
कोई अनुक्रम किसी दूसरे अनुक्रम से लेक्सिकोग्राफिक रूप से छोटा तभी माना जाता है, जब कोई ऐसा पूर्णांक
k (1 ≤ k ≤ n) मौजूद हो ताकि , , …, तथा हो। दूसरे शब्दों में, दो अनुक्रमों के पहले k-1 तत्त्व समान होते हैं, पर अनुक्रम a का k-वाँ तत्त्व अनुक्रम b के k-वें तत्त्व से छोटा होता है।दिए गए स्वैप-अनुमति मैट्रिक्स के अनुसार, आपको यह जानना है कि प्रारंभिक अनुक्रम से आप कौन-सा लेक्सिकोग्राफिक रूप से सबसे छोटा अनुक्रम बना सकते हैं।
इनपुट
• इनपुट की पहली पंक्ति में एक अकेला पूर्णांक
n (1 ≤ n ≤ 300) दिया गया है।• अगली पंक्ति में
n स्पेस से अलग किए गए पूर्णांक (1 ≤ ≤ n) हैं, जो प्रारंभिक अनुक्रम का प्रतिनिधित्व करते हैं, तथा सभी संख्या आपस में भिन्न हैं।• उसके बाद की
n पंक्तियों में n शून्य (0) और एक (1) होते हैं, जो यह दर्शाते हैं कि किसी दो इंडेक्स के बीच स्वैप की अनुमति है या नहीं। यदि पंक्ति i और स्तंभ j का मान 1 हो, तो i-वें और j-वें तत्त्वों के बीच स्वैप की अनुमति है। यदि मान 0 हो, तो स्वैप की अनुमति नहीं है।आउटपुट
कार्यक्रम को उस लेक्सिकोग्राफिक रूप से सबसे छोटे अनुक्रम को प्रिंट करना चाहिए, जो दिए गए प्रारंभिक अनुक्रम से प्राप्त किया जा सकता हो।
उदाहरण
इनपुट | आउटपुट |
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