Movable Type Printer (मूवेबल टाइप प्रिंटर)
आपके पास एक movable type printer है, जो एक पुराना प्रिंटिंग उपकरण है। इसमें आपको छोटे धातु के अक्षरों को क्रमवार लगाकर शब्द बनाने होते हैं। यह प्रिंटर तीन ऑपरेशनों की अनुमति देता है:
- वर्तमान शब्द के अंत में एक अक्षर जोड़ना
- अगर उपलब्ध हो तो अंतिम अक्षर हटाना
- वर्तमान शब्द को प्रिंट करना
आपका काम ऐसा प्रोग्राम लिखना है, जो इनपुट के रूप में दिए गए
n शब्दों को प्राप्त करके सभी शब्दों को किसी भी क्रम में प्रिंट करने के लिए जरूरी न्यूनतम ऑपरेशनों की संख्या ढूँढ़े। साथ ही, आपको उन ऑपरेशनों का क्रम भी आउटपुट में देना है जो इस न्यूनतम संख्या को संभव बनाते हैं।इनपुट
इनपुट की पहली पंक्ति में एकल integer
n (1 ≤ n ≤ 25,000) होगा, जो प्रिंट किए जाने वाले शब्दों की संख्या दर्शाता है।इसके बाद
n पंक्तियाँ होंगी, जिनमें से प्रत्येक पंक्ति में एक शब्द होगा। ये शब्द छोटे अक्षरों ('a' - 'z') से बने होंगे और इनकी लंबाई 1 से 20 के बीच (दोनों सहित) होगी। सभी शब्द एक-दूसरे से भिन्न होंगे।आउटपुट
आउटपुट में पहले एक integer
m प्रिंट करें, जो इन सभी शब्दों को प्रिंट करने के लिए आवश्यक न्यूनतम ऑपरेशनों की संख्या दर्शाता है।इसके बाद की
m पंक्तियों में से प्रत्येक में एक वर्ण हो, जो किए गए ऑपरेशन को दर्शाता है। ऑपरेशनों का संकेत इस प्रकार देना है:- कोई नया अक्षर जोड़ने के लिए उसी छोटे अक्षर को प्रिंट करें।
- अंतिम अक्षर हटाने के लिए वर्ण
-(माइनस, ASCII कोड 45) इस्तेमाल करें।
- वर्तमान शब्द को प्रिंट करने के लिए वर्ण
P(बड़ा अक्षर P) का उपयोग करें।
Examples
इनपुट | आउटपुट |
3
print
the
poem | 20
t
h
e
P
-
-
-
p
o
e
m
P
-
-
-
r
i
n
t
P |
Constraints
Time limit: 4 seconds
Memory limit: 512 MB
Output limit: 1 MB