ओलंपिक का शौक। फूट डालो और जीतो

सभी के लिए शुभ सोमवार। यदि सोमवार आपके लिए सबसे सुखद दिन नहीं है, तो मेरा सुझाव है कि आप थोड़ा आराम करें और अपने शौक का आनंद लें। मेरा शौक ओलंपियाड प्रोग्रामिंग समस्याओं को हल कर रहा है: यह मस्तिष्क को हिलाता है, कल्पना को उत्तेजित करता है और सक्रिय करता है (हालांकि हमेशा सकारात्मक नहीं)। विश्वास नहीं होता? इसे स्वयं आज़माएं, बस ईमानदारी से समस्या को हल करने की कोशिश करें, लंबे समय से प्रतीक्षित स्वीकार करें, और प्राप्त भावनाओं का आनंद लें।



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





मैं बेतरतीब ढंग से एक कार्य का चयन करता हूं। यदि कोई कार्य बहुत सरल है, या कोई ऐसा कार्य जिसकी मैं कल्पना नहीं कर सकता कि कैसे हल किया जाए, तो कई दिनों की पीड़ा के बाद, मैं एक और विकल्प चुनता हूं। लेकिन गंभीरता से, यादृच्छिकता के अलावा, मैं विभिन्न प्रकार के कार्यों को चुनने की कोशिश करता हूं ताकि केवल एक चीज पर लटका न हो। यह किसी को लग सकता है कि मेरी पसंद बहुत सफल नहीं है, मैं आपको इसे कृपालु रूप से लेने के लिए कहता हूं, क्योंकि यह मेरा काम नहीं है, लेकिन सिर्फ एक शौक है, इसलिए ऐसा होता है कि कार्य बहुत सरल या बहुत विशिष्ट हैं।



आइए, अगर हम एक आसान काम करते हैं, तो हम इसका सबसे तेज़ या सबसे खूबसूरत समाधान पाएँगे, तो हमें यह नहीं लगेगा कि हमने अपना समय बर्बाद किया है। खैर, अपने फैसलों को साझा करना न भूलें, जो निश्चित रूप से मेरी तुलना में अधिक सुंदर और तेज हो सकता है। हो सकता है कि हम एक एल्गोरिथ्म के साथ भी आ सकते हैं, जिसे अभी तक कोई नहीं जानता है, क्योंकि हब पर दर्शक सभ्य हैं;)

टास्क की स्थिति

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

मैं समस्या की स्थितियों का मुफ्त अनुवाद लाता हूं:

राजू और मीना को मार्बल्स (माना जाता है कि खेल का नाम) से प्यार है। उनके पास कई नंबर प्लेट हैं। सबसे पहले, राजू एक के बाद एक नंबरों को आरोही क्रम में रखता है। फिर मीना राजू से पहले नंबर प्लेट का नंबर पता करने के लिए कहती है। वह तीन तक गिना जाता है। अगर राजू सही नंबर पर फोन करता है, तो उसे एक अंक मिलता है, अन्यथा बिंदु मीना को मिल जाता है। प्रयासों की एक निश्चित संख्या के बाद, खेल बंद हो जाता है और सबसे अधिक अंक जीतता है। आज आपके पास राजू के रूप में खेलने का मौका है। उन्नत लोगों के रूप में, आप एक कंप्यूटर का उपयोग कर रहे हैं। लेकिन मीना को कम मत समझिए, आपने सही उत्तर प्राप्त करने में लगने वाले समय को ट्रैक करने के लिए एक कार्यक्रम लिखा है। आपको एक कार्यक्रम लिखने की ज़रूरत है जो आपको राजू की भूमिका निभाने में मदद करे।



इनपुट डेटा:

कई परीक्षण संभव हैं, लेकिन 65 से अधिक नहीं। परीक्षण दो नंबरों से शुरू होता है: एन - प्लेटों की संख्या और क्यू - मीरा के अनुरोधों की संख्या। इसके बाद N लाइन होती है जिसमें N टैबलेट पर लिखे नंबर होते हैं। ये नंबर ऑर्डर नहीं किए गए हैं। अगले प्रश्न के साथ क्यू लाइनें हैं। कोई भी इनपुट नंबर 10000 से अधिक नहीं है, और सभी नंबर गैर-नकारात्मक हैं।

N और Q 0 होने पर इनपुट समाप्त होता है।



आउटपुट डेटा:

एल्गोरिथ्म समय सीमा: 3 सेकंड।

प्रत्येक परीक्षण के लिए, परीक्षण का क्रम संख्या प्रदर्शित किया जाता है।

प्रत्येक अनुरोध के लिए, एक पंक्ति प्रदर्शित होती है। स्ट्रिंग का प्रारूप इस बात पर निर्भर करता है कि लेबल के बीच अनुरोधित संख्या पाई गई है या नहीं। दो विकल्प:

• "X, y पर पाया गया" यदि स्थिति x पर संख्या X के साथ पहला लेबल पाया जाता है। पदों की संख्या इस प्रकार है: 1, 2, 3 ...
• "X नहीं मिला" यदि संख्या x के साथ कोई लेबल नहीं है।

एक उदाहरण:

इनपुट:

४ १

2

3

5

1

5

५ २

1

3

3

3

1

2

3

० ०



निष्कर्ष:

मामला # 1:

4 पर 5 मिला

मामला # 2:

2 नहीं मिला

3 पर 3 मिली

यह कार्य एल्गोरिथमिक समस्याओं की श्रेणी से संबंधित है, और "डिवाइड और विजय" खंड के लिए अधिक सटीक है।



यह सभी के लिए एक छोटा सा सुराग है। अब मैं आगे पढ़ने के बिना अपना खुद का समाधान बनाने की सलाह देता हूं। फिर मेरे लिए परिणाम की तुलना करना आपके लिए दिलचस्प होगा।



हमारा कार्य: प्लेटों को संख्याओं के साथ व्यवस्थित करना और नंबर के साथ पहली प्लेट की संख्या का पता लगाना। मैं इस समस्या को हल करने के लिए दो विकल्पों के साथ आया था (केवल छोटी संख्या की संख्या निर्धारित करने के साथ एक संख्या की खोज में - जो कि माथे में है)। इसलिए, हम क्रमिक रूप से दोनों विकल्पों पर विचार करेंगे और निर्धारित करेंगे कि कौन सा बेहतर है और क्यों।

निर्णय

विकल्प 1

मैंने तय किया कि यह सरणी को सॉर्ट करने के लायक है, और फिर इसमें एक नंबर ढूंढें। मुझे पता है कि अब कई लोग मुझे "कैप" कहेंगे। साइट पर जहां मैं कार्य लेता हूं, समाधान की गुणवत्ता के लिए मुख्य मानदंड कार्यक्रम का निष्पादन समय है। हमारे एल्गोरिथ्म के निष्पादन समय को तेज करने के लिए, हम त्वरित छंटाई, साथ ही साथ सरणी में बाइनरी खोज का उपयोग करेंगे। यानी समस्या को हल करने के लिए, हम क्रमिक रूप से संख्याओं के साथ इनपुट सरणी के त्वरित छँटाई के लिए एल्गोरिथ्म को लागू करते हैं, और फिर बाइनरी सर्च एल्गोरिथ्म।



इन एल्गोरिदम का ज्ञान, और सबसे महत्वपूर्ण बात, उन्हें लागू करने की क्षमता, वास्तविक प्रोग्रामिंग में उपयोगी है, इसलिए मैं अनुशंसा करता हूं कि आप अपने आप को उन एल्गोरिदम से परिचित कराएं जिन्होंने उन्हें पहले कभी लागू नहीं किया है, खासकर जब से वे दोनों बहुत सरल हैं।



त्वरित सॉर्ट एल्गोरिथ्म यहाँ अच्छी तरह से वर्णित है । मैं केवल चरणों में इसका संक्षिप्त विवरण दूंगा:

1. एक तत्व को सरणी में चुना जाता है - संदर्भ एक। आमतौर पर वे केंद्रीय तत्व लेते हैं, लेकिन ऐसे समय होते हैं जब कुछ अन्य तत्वों को चुनना बेहतर होता है, यह सरणी के गुणों पर निर्भर करता है।

2. संदर्भ संख्या से कम सभी तत्व सरणी के बाईं ओर ले जाए गए हैं, और तत्व दाईं ओर संदर्भ से बड़े हैं। इस प्रकार हम सरणी को दो सबसेट में विभाजित करते हैं। सहायक तत्व के बाईं ओर सहायक तत्व की तुलना में छोटे तत्व हैं, और दाईं ओर इसके विपरीत।

3. दोनों उपप्रकारों में, सभी चरणों को फिर से किया जाता है यदि तत्वों की संख्या कम से कम दो हो।



क्विकॉर्ट में ऐसे संशोधन हैं जो इसके काम को गति देते हैं। यदि आप रुचि रखते हैं, तो संशोधन को लागू करने का प्रयास करें और व्यवहार में एल्गोरिदम के त्वरण की जांच करें।



एक क्रमबद्ध सरणी में द्विआधारी खोज एल्गोरिथ्म और भी सरल है।

1. सरणी का केंद्रीय तत्व चुना गया है, जो सरणी को दो उप-वर्गों में विभाजित करता है।

2. यदि चयनित आइटम वांछित से बड़ा है, तो उसी योजना के अनुसार बाईं सबर्रे में खोज जारी रखें। अगर कम है, तो सही में।

नतीजतन, हम जल्दी से वांछित तत्व को प्राप्त करते हैं।



केवल एक चीज जिस पर आपको ध्यान देने की आवश्यकता है: द्विआधारी खोज में वांछित संख्या की पहली घटना के लिए जरूरी नहीं है, अगर एक ही संख्या के साथ प्लेटें हों। द्विआधारी खोज प्रक्रिया को लागू करना आवश्यक है ताकि वांछित संख्या की पहली घटना का सूचकांक निर्धारित हो।



पहला समाधान: 0.368 स्वीकृत

विकल्प 2

यदि आप प्रतिबंध पर ध्यान देते हैं, जो इस स्थिति में वर्णित है: कोई भी इनपुट संख्या 10000 से अधिक नहीं है, तो एक और समाधान दिखाई देता है। गोलियों पर संख्या दर्ज करने से पहले, हम 10,000 तत्वों के लिए एम की एक सरणी बना सकते हैं।

M [i] = 0 यदि संख्या I के साथ कोई प्लेट नहीं है

M [i] = r, जहाँ r, नंबर I के साथ प्लेटों की संख्या है



संख्या दर्ज करते समय हम तुरंत इस सरणी को भर सकते हैं। सरणी को भरते समय, हम अद्वितीय संख्याओं की संख्या निर्धारित करेंगे।



अगला, हम दो और सरणियाँ (या यदि आप चाहें तो संरचनाओं की एक सरणी) बनाएंगे। पहले तत्वों के सरणी में आरोही क्रम में अद्वितीय संख्याएँ होंगी। पदों की दूसरी सरणी में वह स्थिति होगी जहां स्थिति [i] तत्वों की संख्या की पहली स्थिति की संख्या है [i]। हम सरणी के माध्यम से एक पास के साथ इन सरणियों को भर सकते हैं।

0. पॉज़ = 0 - वर्तमान स्थिति, जे = 0 - वर्तमान अद्वितीय संख्या

1. हम एम [i] के लिए देख रहे हैं! = 0

2. तत्वों में नई संख्या डालें [j] = i

3. पद [i] = स्थिति

4. हम एम [i], j ++ पर पॉज़ शिफ्ट करते हैं

5. यदि हमने सभी 10,000 नंबरों को पास नहीं किया है (या आप काम को गति देने के लिए अधिकतम याद कर सकते हैं), तो चरण 1 पर जाएं



अब हमारे पास तत्वों की एक सरणी है, जहां हम फिर से बाइनरी खोज का उपयोग करके संख्याओं की तलाश करेंगे। हम तत्वों की सरणी में पाया संख्या के सूचकांक के साथ पदों की सरणी से उत्तर जारी करेंगे।



दूसरा समाधान: 0.248 स्वीकृत



दूसरा विकल्प पहले से तेज क्यों था? इन दो दृष्टिकोणों के बीच मुख्य अंतर यह है कि दूसरे संस्करण में हमने छंटाई को छोड़ दिया, जो सबसे अधिक समय लेने वाला है। समय की बर्बादी को रोकने के बजाय, हमने आवश्यकता से अधिक रैम चुरा लिया। और एक बाइनरी खोज उन मामलों में कम तत्वों के साथ एक सरणी में आयोजित की जाती है जहां समान संख्याओं के साथ प्लेट होते हैं।

दूसरा विकल्प अनुचित होगा यदि इनपुट नंबर केवल 4 बाइट्स की क्षमता तक सीमित थे। ओलंपिक में, कभी-कभी इस प्रकार की स्थितियों पर ध्यान देना सार्थक होता है, जो वे अक्सर बनाते हैं, समस्या के वैकल्पिक समाधान पर इशारा करते हैं।



फिर, क्या कार्य एल्गोरिदम के विभाजन और विजय अनुभाग से संबंधित है? क्योंकि उपयोग किए गए दोनों एल्गोरिदम इस खंड से संबंधित हैं, क्योंकि त्वरित सॉर्टिंग में हमने सरणी को दो भागों में विभाजित किया, और फिर इसे सॉर्ट किया, और बाइनरी खोज में हमने लगातार वांछित क्षेत्र को आधे में विभाजित करके खोज को सीमित कर दिया।



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

आप यहां अपना निर्णय (पंजीकरण आवश्यक) देख सकते हैं।



PS वेबसाइट http://uva.onlinejudge.org/ , जहां से कार्य आया, मैंने अचानक FF में लोड करना बंद कर दिया। मुझे यकीन नहीं है कि यह एक ब्राउज़र समस्या है, लेकिन साइट अन्य ब्राउज़र में खुलती है। ध्यान रखें यदि आप अचानक उसी समस्या का सामना करते हैं।



मेरे निर्णय, हमेशा की तरह, डाउनलोड किए जा सकते हैं: विकल्प 1 और विकल्प 2 ।



स्वीकृत (0.248)। सौभाग्य है



UPD: श्री डिमोकोलस के संकेतों के लिए धन्यवाद, मैं दूसरे विकल्प को स्वीकार करने में तेजी लाने में कामयाब रहा (0.108) ( डाउनलोड )

UPD: इसके अलावा, कृपया श्री कापीजेआई के निर्णय पर ध्यान दें , जिसकी निष्पादन गति 0.104 है



UPD: हब के रीडर, अलेक्सी, uva.onlinejudge.org साइट के सभी उपयोगकर्ताओं के बीच सबसे अच्छा समय (0.052) प्राप्त करने में कामयाब रहे। यहाँ उसका समाधान है। बधाई!

पीएस जिनके पास अतिरिक्त निमंत्रण है, वे एलेक्सी के लिए अफसोस न करें, मुझे लगता है कि उनके पास हमारे साथ साझा करने के लिए कुछ है।