ओलंपिक का शौक। वार्म अप करें

एक शौक के रूप में, मैं ओलंपियाड प्रोग्रामिंग समस्याओं को हल करता हूं। यह रोजमर्रा की समस्याओं से ध्यान भटकाने में मदद करता है, जिससे आपके अपने सूक्ष्म विमान में दुनिया छोड़ने के लिए एक और घंटे की अनुमति मिलती है। मेरा मस्तिष्क, इस शौक के लिए धन्यवाद, निरंतर एथलेटिक रूप में है।



मैंने फैसला किया कि एल्गोरिदम, विचार, परिणाम आपके साथ साझा करने के साथ-साथ समस्याओं को हल करने के मेरे तरीकों की गुणवत्ता की आलोचना करना अच्छा होगा।

हम कार्य करेंगे, इसे भागों में अलग-अलग करेंगे, विश्लेषण करेंगे, विभिन्न समाधानों का आविष्कार करेंगे, सर्वश्रेष्ठ का चयन करेंगे, और फिर "महान न्यायाधीशों" को अदालत में लाएंगे। कई लोगों के लिए, मेरी राय में, उतराई के ऐसे घंटे बहुत उपयोगी होंगे, लेकिन किसी को सिर्फ अपने स्वयं के एल्गोरिथ्म के साथ प्रतिस्पर्धा करने और आने के लिए दिलचस्पी होगी।



मैं साइट http://uva.onlinejudge.org/ से कार्य करूँगा, जहाँ हर स्वाद के लिए कार्यों का एक बड़ा संग्रह है, और वहाँ आप अपने समाधान की जाँच कर सकते हैं। मैं यादृच्छिक रूप से चुनूंगा और हमेशा वही लाऊंगा जो मैंने अंतिम निर्णय के लिए शुरू किया है, जिसे "स्वीकृत" चिह्न (स्वीकृत) द्वारा चिह्नित किया जाएगा। इन समस्याओं को हल करने के लिए, हमें प्रोग्रामिंग भाषाओं में से एक का ज्ञान चाहिए: c, c ++, java, pascal, साथ ही साथ धैर्य, तर्क, और अंग्रेजी भाषा का मूल ज्ञान, हम अंग्रेजी में कार्यों के लिए शर्तें प्राप्त करते हैं।



इसलिए, हम अपनी क्षमताओं का परीक्षण करने के लिए सेट-अप "शुरुआती के लिए" वार्म-अप के लिए एक सरल कार्य के साथ शुरू करेंगे।



समस्या की स्थिति का संक्षिप्त अनुवाद करें (मुफ्त अनुवाद):

सरकार ने सभी लोगों को टैग करने का फैसला किया ताकि उनकी निगरानी की जा सके। ऐसा करने के लिए, एक छोटे कंप्यूटर को प्रत्येक व्यक्ति के लिए प्रत्येक बाईं कलाई में प्रत्यारोपित किया जाता है। इस कंप्यूटर में सभी प्रकार की व्यक्तिगत जानकारी है, साथ ही आंदोलन को नियंत्रित करने के लिए एक ट्रांसमीटर भी है।

प्रत्येक कंप्यूटर में एक विशिष्ट पहचान कोड होता है, जिसमें 50 अक्षरों से अधिक नहीं होता है, जो निचले अक्षरों के अंग्रेजी अक्षरों (26 अक्षरों) से निर्मित होता है। कोड के लिए सेट किया गया वर्ण अनिश्चित रूप से चुना गया है।

मान लीजिए कि 3 अक्षर "a", 2 वर्ण "b" और 1 वर्ण "c" को एक वर्ण सेट के रूप में चुना गया था। इन शर्तों के तहत, 60 अलग-अलग पहचान कोड बनाए जा सकते हैं।



abaabc

abaacb

ababac



ये तीन संभावित कोड हैं, जो उपरोक्त शर्तों के आधार पर, वर्णानुक्रम में सूचीबद्ध हैं।

इन पहचान कोड को बनाने में मदद करने के लिए आपको एक कार्यक्रम लिखने की आवश्यकता है। कार्यक्रम को वर्णों के अनुक्रम को स्वीकार करना चाहिए (50 से अधिक लोअरकेस अक्षर जिन्हें दोहराया जा सकता है) और यदि कोई मौजूद है, तो अगले पहचान कोड को वर्णमाला क्रम में प्रिंट करें। यदि दिए गए कोड वर्णों के दिए गए सेट के लिए अंतिम (वर्णमाला के क्रम में) है, तो "कोई उत्तराधिकारी" न छापें।

इनपुट में लाइनों की एक श्रृंखला होगी, जिनमें से प्रत्येक एक पहचान कोड का प्रतिनिधित्व करेगा। प्रतीक "#" इनपुट के अंत का संकेत देगा

आउटपुट में प्रत्येक इनपुट कोड के लिए एक अगला कोड होना चाहिए।

यदि abaacb को इनपुट में खिलाया जाता है, तो हमारे प्रोग्राम को ababac का जवाब देना चाहिए।



इस स्थान पर, रुचि रखने वालों को लेख को रोल करना चाहिए और समस्या को स्वयं हल करने का प्रयास करना चाहिए। मैं गारंटी देता हूं कि जब आप "स्वीकृत" प्राप्त करते हैं, तो आप एक हल्का आध्यात्मिक लिफ्ट महसूस करेंगे और ताक़त बढ़ा सकते हैं।



जाहिर है, यह "क्रमपरिवर्तन" के क्षेत्र से एक समस्या है, अर्थात्। ababacb के बाद ababac अगली lexicographic पुनर्व्यवस्था है। मेरी राय में, यह एल्गोरिथ्म यहां बहुत अच्छी तरह से वर्णित है, इसलिए हम विशेष रूप से इसका विश्लेषण नहीं करेंगे। आइए हम अपने लिए एल्गोरिथम के मुख्य चरण लिखें:

1. कार्यक्रम के पहले चरण में, सरणी के अंत से आगे बढ़ते हुए, पड़ोसी तत्वों की तुलना करें, यदि पिछला (सरणी में स्थान) तत्व अगले से बड़ा है, तो आगे बढ़ें, यदि कम हो, तो रोकें और उसकी संख्या (एम) को याद रखें, यह तत्व बदल जाएगा।
2. Mth के बाईं ओर के तत्व उत्परिवर्तनीय नहीं हैं। दाईं ओर के तत्वों के बीच, आपको तत्व (k) का चयन करने की आवश्यकता है, जिसे mth को प्रतिस्थापित करना चाहिए। यह उन लोगों में सबसे छोटा तत्व है, जो मट से बड़े हैं।
3. हम mth और kth तत्वों को बदलते हैं।
4. यह नए mth तत्व के दाईं ओर आरोही क्रम में क्रमबद्ध रहता है, लेकिन तब से उन्हें अवरोही क्रम में आदेश दिया जाता है, बस उन्हें लपेटो।

मुख्य बात जो आपको याद रखनी चाहिए, वह यह है कि यदि हमें अगला क्रमचय नहीं मिला, तो हमें "नो उत्तराधिकारी" को वापस करना होगा।



यह केवल यह मूल्यांकन करने के लिए बनी हुई है कि हमारा कार्यक्रम कितनी खराब परिस्थितियों में काम करेगा, ताकि 3 सेकंड की समय सीमा में कूद न जाए। मान लीजिए कि इनपुट अनुक्रम में वर्णों की संख्या है। सबसे खराब परिस्थितियों में, पहले चरण में, कार्यक्रम को एन तुलना करना होगा (सभी तत्वों को बढ़ते क्रम में व्यवस्थित किया गया है)। दूसरे चरण में, न्यूनतम की खोज की जाती है - यह एन तुलना है। तीसरे और चौथे चरण में, हम एन तत्वों की अदला-बदली करते हैं, जिन्हें सरणी में एन रीड / राइट ऑपरेशन की आवश्यकता होगी। नतीजतन, हमें 2N तुलना और एन पुनर्लेखन मिलता है। बशर्ते कि एन 50 (समस्या की स्थिति) से अधिक नहीं है, हमारे एल्गोरिथ्म के संचालन में कुछ मिलीसेकंड लगेगा।



अच्छा, चलो इसे ले चलते हैं । मेरा C ++ समाधान यहाँ डाउनलोड किया जा सकता है ।



स्वीकृत (0.008)। आपको भी शुभकामनाएँ!