🙆🏾 👨🏽‍🎤 👩‍🎨 रूसी कोड कप 2013: पहले योग्यता दौर के कार्यों का विश्लेषण 👩‍👧‍👧 👸🏾 ⬛️

शनिवार, 13 अप्रैल, 2013 को 19 बजे पहला क्वालीफाइंग राउंड हुआ। प्रतीत होता है कि अशुभ तारीख के बावजूद, इस दिन के लिए, इसके विपरीत, बहुत सफल रहा था।
इस पोस्ट में हम पहले योग्यता दौर के परिणामों के बारे में संक्षेप में बात करेंगे और उन कार्यों का विस्तार से विश्लेषण करेंगे जो हमने प्रतिभागियों को प्रस्तावित किए थे।
आज के विश्लेषण में शामिल हैं:

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

चलो योगों के साथ शुरू करते हैं। 765 लोगों ने योग्यता में भाग लिया (ध्यान दें कि यह उन प्रतिभागियों की संख्या है, जिन्होंने अपने समाधान भेजे थे;
प्रतिभागियों को समस्याओं को हल करने के लिए 2 घंटे का समय दिया गया। कार्य स्वयं क्वालिफिकेशन राउंड की शुरुआत में सीधे साइट पर प्रकाशित किए गए थे, इसलिए, कोई भी प्रतिभागी खुद को उनके साथ पहले से परिचित नहीं कर सकता था - सभी एक समान पायदान पर थे।
प्रतिभागियों का भौगोलिक वितरण वास्तव में वैश्विक निकला, हालांकि, निश्चित रूप से, रूसी प्रतिभागियों की संख्या अधिकतम थी। तो, घटते क्रम में:

रूस - 540
यूक्रेन - 81
बेलारूस - 46
यूएसए - 21
आर्मेनिया - 20
कजाकिस्तान - १५
उजबेकिस्तान - ६
जॉर्जिया - 6
जर्मनी - 6
स्विट्जरलैंड - 5
स्वीडन - 2
ग्रेट ब्रिटेन - २
नीदरलैंड - २
किर्गिस्तान - 2
पोलैंड - 2
आइसलैंड - 1
तजाकिस्तान - १
आयरलैंड - 1
जापान - १
स्पेन - 1
लिथुआनिया - १
इज़राइल - 1
चेक गणराज्य - 1

201 लोगों ने क्वालीफाइंग दौर में प्रवेश किया। नीचे उन 10 प्रतिभागियों की सूची दी गई है जो पहली बार क्वालीफाई करने वाले थे:
1. व्लादिस्लाव एपिफ़ानोव
2. सर्जी रोगुलेंको
3. इवान पोपलीशेव (तीसरा स्थान)
3. प्योत्र मित्रीचेव (एक और तीसरा स्थान)
5. एंटन रायचुक
6. व्लादिस्लाव इसेनबायेव विंगर
7. एंटोन लुनेव
8. ईगोर कुलिकोव
8. गेनेडी कोरोटकेविच
8. रोमन रिज़वानोव
जैसा कि सूची से देखा जा सकता है, कुछ प्रतिभागियों ने एक ही नंबर के तहत स्थानों को साझा किया, क्योंकि उन्होंने समान अंक बनाए।
अब कार्यों के विश्लेषण के लिए आगे बढ़ते हैं। प्रतिभागी अपने निर्णयों को सत्यापित करने में सक्षम होंगे, और जिन्होंने अभी तक योग्यता पास नहीं की है वे अपने संस्करणों का अभ्यास और जांच कर सकेंगे (वैसे, निम्नलिखित योग्यता के दौर 11 मई और 2 जून हैं)।

समस्या ए ओलंपिक
विचार: विटाली अक्षोनोव
बोध: विटालि अक्ष्योनोव
विश्लेषण: विटाली अक्षोनोव

समस्या का विस्तृत विवरण

समय सीमा - 1 सेकंड
256 एमबी मेमोरी सीमा
अब ग्नोमलैंड में आगामी ओलंपिक की तैयारी कर रहा है। गनोम-ब्रिगेडियर को हर्टबॉल, जॉर्डनबॉल और मेडवेबॉल खेलने के लिए खेतों के निर्माण का काम दिया गया था। प्रत्येक क्षेत्र एक आयत है। खेल के नियमों के अनुसार, खेतों को स्थित होना चाहिए ताकि उनके पक्ष उत्तर-दक्षिण और पश्चिम-पूर्व दिशाओं के समानांतर हों।
गनोमलैंड में जमीन बहुत महंगी है, इसलिए खेल आयोजक जमीन खरीदने पर जितना संभव हो उतना कम पैसा खर्च करना चाहते हैं। चूंकि हर्टबॉल, जॉर्डनबॉल और मेडवेबोल प्रतियोगिताओं को अलग-अलग समय पर आयोजित किया जाएगा, इसलिए फ़ील्ड ओवरलैप हो सकती हैं।
बौनों को न्यूनतम क्षेत्र खोजने में मदद करें जो निर्माण के बाद तीन क्षेत्रों पर कब्जा कर सकते हैं।
पहले उदाहरण में संभव इष्टतम फ़ील्ड लेआउट में से एक को चित्र में दिखाया गया है।

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

समस्या को हल करने के लिए, आप देख सकते हैं कि एक इष्टतम समाधान है जिसमें दिए गए सभी तीन आयतों में एक कोने में आम है।
प्रत्येक फ़ील्ड को लंबवत या क्षैतिज रूप से सम्मिलित करने के लिए गणना करें। हमने खेतों की स्थिति तय करने के बाद, यह केवल आयतों के संघ के क्षेत्र की गणना करने के लिए पर्याप्त है। इसकी गणना निम्न प्रकार से की जा सकती है: S = S ₁ + S ₃ + S ₃ - S ₁₂ - S ₂₃ - S ₁₃ + S ₁₂₃ , जहाँ S _i ith आयत का क्षेत्र है, S _ij दो आयतों का चौराहा क्षेत्र है जहाँ पर मैं और j, और S ₁₂₃ तीनों आयतों का प्रतिच्छेदन क्षेत्र है।

समस्या बी। ट्रेपेज़ॉइड मानचित्र और ट्रेपेज़ॉइड
विचार: विटालि डीमनिअनुक
बोध: विटालि दुमंजुक
विश्लेषण: विटाली डमींजुक

समस्या का विस्तृत विवरण

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

दो सेटों को अलग माना जाता है अगर पहले सेगमेंट से संबंधित सेगमेंट है और दूसरे से संबंधित नहीं है। प्रत्येक सेट में लिए गए सेगमेंट की संख्या जोड़ीदार होनी चाहिए।
छात्रों को ऐसे सेटों की संख्या ज्ञात करने में सहायता करें।
इनपुट प्रारूप
पहली पंक्ति में नंबर t है - इसलिए कई बार एंटोन ने अपने छात्रों को यह काम दिया। निम्नलिखित 2t लाइनों में सभी कार्यों का वर्णन है।
प्रत्येक कार्य के विवरण में दो लाइनें होती हैं। विवरण की पहली पंक्ति में संख्या n है - बोर्ड पर खींचे गए खंडों की संख्या। समस्या के वर्णन की दूसरी पंक्ति एन पूर्णांक एआई देती है - उनकी लंबाई (4 ≤ n description 5000, 1 1 ai for 108 सभी के लिए 1 से n तक)।
सभी कार्यों में सभी खंडों की कुल संख्या 5000 से अधिक नहीं है।
आउटपुट स्वरूप
एक अलग लाइन में प्रत्येक कार्य के लिए एक नंबर प्रिंट करें - वांछित संख्या सेट।

क्रमशः ए और बी द्वारा, और पक्षों की लंबाई के द्वारा ट्रेपेज़ॉइड के छोटे और बड़े समानांतर पक्षों की लंबाई को निरूपित करें। तब एक ट्रेपोजॉइड की रचना केवल तभी की जा सकती है यदि a + 2c> b। A, b और c के ऊपर जाने पर, हमें O (n ³ ) में एक समाधान मिलता है।
ध्यान दें कि फिक्स्ड बी और बढ़ते सी के लिए, न्यूनतम संभव घट जाती है। हम बढ़ते क्रम में b से अधिक पुनरावृति करेंगे और निश्चित b के लिए, हम बढ़ते क्रम में c पर भी पुनरावृति करेंगे। जब सी पर पुनरावृत्ति होती है, तो हम न्यूनतम संभव के लिए एक सूचक बनाए रखेंगे। बी, सी, न्यूनतम संभव ए, और सरल दहनशील सूत्रों का उपयोग करके जानना, चार खंडों के सेट की संख्या की गणना करना आसान है जो दिए गए मापदंडों के साथ एक ट्रेपोजॉइड बनाते हैं।
इसके अलावा, उन मामलों को संभालना न भूलें जिनमें ए = बी, ए = सी, बी = सी, और ध्यान से सुनिश्चित करें कि प्रत्येक चार में सेगमेंट की संख्या जोड़ीदार अलग है। परिणामी जटिलता हे (n ² )।

टास्क सी। मालुरन का भंडारण
विचार: विटाली अक्षेनोव
एहसास: पावेल क्रोटकोव
विश्लेषण: पावेल क्रोटकोव

समस्या का विस्तृत विवरण

2 सेकंड की समय सीमा
256 एमबी मेमोरी सीमा
2345 में खोजा गया, रासायनिक तत्व मुरान बहुत रेडियोधर्मी है। मुरान के अनुचित हैंडलिंग से अप्रत्याशित परिणाम हो सकते हैं, इसलिए इसका उपयोग करते समय, इसका भंडारण और परिवहन करते समय विशेष सावधानी बरतनी चाहिए।
मुरानो के कई अलग-अलग समस्थानिक हैं, जिनमें से प्रत्येक की विशेषता एक प्राकृतिक संख्या है - इसका परमाणु द्रव्यमान। आइसोटोप के किसी भी जोड़े के एक साथ लंबे समय तक भंडारण के दौरान, द्रव्यमान का योग k "क्रिटिकल नंबरों" में से एक के बराबर होता है, आइसोटोप की यह जोड़ी प्रतिक्रिया करती है और एक विस्फोट होता है। यह ज्ञात है कि सभी महत्वपूर्ण संख्याएं दो की गैर-नकारात्मक शक्तियां हैं।
फ्लैटलैंड परमाणु प्रयोगशाला में, मुरानो के नमूने दो विशेष गोदामों में रखे जाते हैं। वैज्ञानिकों ने मुरन के अलग-अलग आइसोटोप प्राप्त करने में कामयाबी हासिल की, जिनमें से जन संख्या 1 से n तक है। अब आपको भंडारण के लिए गोदामों में आइसोटोप वितरित करने की आवश्यकता है। भंडारण के सुरक्षित तरीके वे हैं जिनमें प्रत्येक आइसोटोप बिल्कुल एक गोदाम में संग्रहीत किया जाता है, और किसी भी दो अलग-अलग आइसोटोप जिनके द्रव्यमान का योग "महत्वपूर्ण संख्याओं" में से एक के बराबर होता है, विभिन्न गोदामों में संग्रहीत होते हैं।
वैज्ञानिकों को यह पता लगाने में मदद करें कि म्लुरान को स्टोर करने के कितने अलग-अलग सुरक्षित तरीके हैं।
इनपुट प्रारूप
कार्य के इनपुट में कई परीक्षण सूट शामिल हैं। प्रत्येक सेट के विवरण में दो लाइनें होती हैं।
विवरण की पहली पंक्ति में दो पूर्णांक n और k (1 ≤ n, 1018, 1 ≤ k number 61) हैं - समस्थानिकों की संख्या जिन्हें संग्रहीत किया जाना चाहिए, और "महत्वपूर्ण संख्याओं" की संख्या। अगली पंक्ति में k अलग-अलग प्राकृतिक संख्याएँ हैं, जिनमें से प्रत्येक दो की शक्ति है और 2n - महत्वपूर्ण संख्याओं से अधिक नहीं है। महत्वपूर्ण संख्या रिक्त स्थान से अलग होती है।
प्रत्येक परीक्षण में डेटा सेट की संख्या 10,000 से अधिक नहीं होती है। परीक्षण की अंतिम पंक्ति में दो शून्य होते हैं।
आउटपुट स्वरूप
एक अलग लाइन पर सेट किए गए प्रत्येक परीक्षण के लिए, दो गोदामों में सभी आइसोटोपों को संग्रहीत करने के सुरक्षित तरीकों की संख्या प्रिंट करें, modulo 109/7 लिया।

पहले हम एक समाधान लागू करते हैं जो रैखिक समय में काम करता है। हम बढ़ते हुए क्रम में आइसोटोप के द्रव्यमान पर विचार करते हैं, 1 से शुरू करते हैं। Let k वर्तमान संख्या है, और 2 ^t k की तुलना में दो की न्यूनतम शक्ति है। इस मामले में:

यदि k दो या 2 ^t की शक्ति है, "महत्वपूर्ण संख्या" के सेट में नहीं है, तो द्रव्यमान का आइसोटोप किसी भी गोदाम में संग्रहीत किया जा सकता है
अन्यथा, द्रव्यमान k का एक समस्थानिक केवल एक गोदाम में संग्रहीत किया जा सकता है जहाँ द्रव्यमान 2 ^t - k का समस्थानिक नहीं होता है

ध्यान दें कि उत्तर 2 ^{x + d है} , जहाँ d दो की शक्तियों की संख्या 1 से कम नहीं है और n से अधिक नहीं है, और x संख्याओं की संख्या है जो दो की शक्तियाँ नहीं हैं, जैसे कि उनकी दो की बड़ी बड़ी शक्ति "महत्वपूर्ण संख्या" के सेट में नहीं है। "। इसलिए, सभी नंबरों को 1 से n में लॉग ₂ एन सेगमेंट में विभाजित करना संभव है, जिनमें से सीमाएं दो की आसन्न शक्तियां हैं, फिर वांछित खंडों का चयन करें और उनकी लंबाई का योग करें।

टास्क डी। ग्रह की रक्षा करना
विचार: विटाली अक्षोनोव
अहसास: निकोले वेदरनिकोव
विश्लेषण: निकोले वेदरनिकोव

समस्या का विस्तृत विवरण

2 सेकंड की समय सीमा
256 एमबी मेमोरी सीमा
हाल ही में एक उल्कापिंड के उरल्स में गिरने के बाद, कई देशों की सरकारों ने पृथ्वी को क्षुद्रग्रहों से बचाने के बारे में सोचा। इसके लिए, अंतर्राष्ट्रीय एंटी-उल्कापिंड एजेंसी (MAMA) बनाई गई थी, जिसमें खगोल भौतिकी के क्षेत्र में सर्वश्रेष्ठ वैज्ञानिकों को आमंत्रित किया गया था।
कई हफ्तों के लिए, वैज्ञानिकों ने पाया है कि n क्षुद्र ग्रह पृथ्वी के तत्काल आसपास के क्षेत्र में उड़ते हैं, और अगर क्षुद्रग्रह पृथ्वी से आर से अधिक सख्ती से है, तो यह इसके लिए खतरा पैदा नहीं करता है। सरलता के लिए, वैज्ञानिकों ने सुझाव दिया कि पृथ्वी के निकट सभी क्षुद्रग्रह एक सीधी रेखा में उड़ते हैं, और शून्य समय पर अपनी स्थिति और वेग वेक्टर निर्धारित करते हैं। अब, वैज्ञानिक सीखना चाहते हैं कि किसी समय में कितने क्षुद्रग्रह पृथ्वी के लिए खतरा पैदा करते हैं, इस बारे में प्रश्नों का जवाब देना चाहते हैं।
सुविधा के लिए, हम एक आयताकार कार्तीय समन्वय प्रणाली का परिचय देते हैं। पृथ्वी का निर्देशांक (0, 0, 0) है। सभी क्षुद्रग्रहों और पृथ्वी को अंतरिक्ष में भौतिक बिंदु माना जाता है।
विशिष्ट समय के बारे में कई प्रश्न पूछे गए थे। उनमें से प्रत्येक के लिए, यह निर्धारित करना आवश्यक है कि इस समय कितने क्षुद्रग्रह पृथ्वी के लिए खतरा पैदा करते हैं।
इनपुट प्रारूप
पहली पंक्ति में दो पूर्णांक n और R (1 ≤ n, 100000, 1 ≤ R) 106) हैं - क्षुद्रग्रहों की संख्या और खतरे के क्षेत्र की त्रिज्या।
अगली अगली पंक्तियों में छह पूर्णांक xi, yi, zi, vxi, vyi और vzi (i106 − xi, yi, zi, 106, −100, vxi, vyi, vzi ≤ 100) शामिल हैं - निर्देशांक जो प्रारंभिक निर्दिष्ट करते हैं i-th क्षुद्रग्रह की स्थिति और वेग वेक्टर। यह गारंटी है कि वेग वेक्टर 0 के बराबर नहीं है।
अगली पंक्ति में एक पूर्णांक m (1 ≤ m) 100000) शामिल है - वैज्ञानिकों द्वारा रुचि रखने वाले समय बिंदुओं की संख्या।
अगली एम लाइनों में से प्रत्येक में एक पूर्णांक ती (0 ≤ ti) 107) शामिल है - एक ऐसा समय जो वैज्ञानिकों को रुचता है।
आउटपुट स्वरूप
समय के प्रत्येक क्षण के लिए एक ही पूर्णांक प्रिंट करें - क्षुद्रग्रहों की संख्या जो खतरे के क्षेत्र में हैं।

प्रत्येक उल्कापिंड पर विचार करें और खतरे के क्षेत्र में प्रवेश और निकास के समय का पता लगाएं। ऐसा करने के लिए, क्षेत्र x ² + y ² + z ² = R ² के समीकरण में ^{, हम} उस रेखा के समीकरण को प्रतिस्थापित करते हैं जो उल्कापिंड के प्रक्षेपवक्र को परिभाषित करता है, अर्थात x = x ₀ + dx • t, y = y ₀ + dy • t, z = z ₀ + z + dz • t। हमें समय के लिए द्विघात समीकरण मिलता है। जड़ें वह समय होगा जो हमें रुचती है। इस समस्या में, फ़्लोटिंग-पॉइंट नंबरों की सटीकता के साथ समस्याएं पैदा हो सकती हैं, इसलिए यदि समीकरण की जड़ एक पूर्णांक के करीब थी, तो इसे गोल करना पड़ा।
इन समयों को प्रश्नों में जोड़ें और उन्हें बढ़ते क्रम में क्रमबद्ध करें। यदि समय मेल खाता है, तो वे समय जो प्रविष्टि के समय के अनुरूप हैं, पहले जाएंगे, फिर अनुरोध करेंगे, और अंत में - खतरे के क्षेत्र को छोड़ने का समय। हम एक काउंटर शुरू करेंगे जो यह बताता है कि हमारे पास कितने उल्कापिंड हैं जो खतरे के क्षेत्र में हैं। यदि वर्तमान समय में प्रवेश का समय है, तो इसे बढ़ाएं; यदि यह एक अनुरोध है, तो हम इस अनुरोध का उत्तर लिखते हैं, अन्यथा हम उत्तर को कम कर देते हैं।
रनटाइम O ((n + m) • लॉग (n + m))

समस्या ई। दूरसंचार
विचार: अन्ना मालोवा
कार्यान्वयन: बोरिस मिनाएव
विश्लेषण: बोरिस मिनाएव

समस्या का विस्तृत विवरण

2 सेकंड की समय सीमा
256 एमबी मेमोरी सीमा
वर्ष 2112 करीब आ रहा था, और आप समान विचारधारा वाले लोगों की एक छोटी टीम के साथ, एक परित्यक्त देश में खजाने की तलाश में जाने का फैसला किया। इस देश के शहर सड़कों से जुड़े हुए हैं जिसके साथ आप दोनों दिशाओं में जा सकते हैं। आप जानते हैं कि इस देश के निवासी इन सड़कों के किनारे अपने खजाने को दफनाना पसंद करते थे। इसलिए, आप इस देश की सभी सड़कों पर ड्राइव करना चाहते हैं और दफन खजाने को ढूंढना चाहते हैं। आपको पहले से एक प्रभावी यात्रा योजना बनाने की आवश्यकता है। ऐसा करने के लिए, एक शहर चुनें जहां से आपकी यात्रा शुरू हो। फिर, सड़कों के किनारे चलते हुए, कुछ और शहरों की यात्रा करें। तैयार की गई योजना को प्रभावी कहा जाता है यदि प्रत्येक सड़क आपके द्वारा ठीक एक बार देखी जाएगी।
योजना एक तथ्य से जटिल है। शहरों के कुछ जोड़े टेलीपोर्टर्स द्वारा जुड़े हुए हैं। उदाहरण के लिए, यदि शहर ए और सिटी बी टेलीपोर्ट से जुड़े हुए हैं, तो, शहर ए के लिए एक सड़क पर आने से, आप तुरंत शहर बी को टेलीपोर्ट करेंगे और केवल उन सड़कों के साथ ड्राइविंग जारी रख सकते हैं जो शहर बी से जुड़े हुए हैं। इसी तरह, अगर आप सड़क से आते हैं सिटी बी, फिर तुरंत शहर ए को टेलीपोर्ट करें और उन सड़कों के साथ जारी रहें जो शहर ए से जुड़े हुए हैं।
प्रत्येक शहर को एक से अधिक दूसरे शहर में नहीं भेजा जा सकता है। आपको एक प्रभावी यात्रा योजना बनाने की आवश्यकता है।
इनपुट प्रारूप
इनपुट में कई परीक्षणों का वर्णन है। प्रत्येक परीक्षण में निम्नलिखित संरचना होती है। पहली पंक्ति में तीन पूर्णांक n, m, k (1 ≤ n 1 105, 1 ≤ m ≤ 105, 0, k) 105) - शहरों की संख्या, सड़कों की संख्या और टेलीपोर्टर्स की संख्या शामिल है। अगली मी लाइनों में दो अलग-अलग संख्याएँ हैं - उन शहरों की संख्या जो अगली सड़क से जुड़े हुए हैं। अगला, k लाइनों में दो अलग-अलग संख्याएं हैं जो शहरों के जोड़े का वर्णन करती हैं जो टेलीपोर्टर्स द्वारा जुड़े हुए हैं।
दो शहरों के बीच कई सड़कें हो सकती हैं। कोई भी शहर अपने आप में एक सड़क से नहीं जुड़ा है। किसी भी शहर को खुद को टेलीपोर्ट नहीं किया जाता है। किसी भी शहर को एक दूसरे शहर से अधिक नहीं भेजा जाता है।
यह गारंटी है कि सभी परीक्षणों में कुल शहरों की संख्या 105 से अधिक नहीं है। इसी तरह, सड़कों की कुल संख्या और टेलीपोर्टर्स की कुल संख्या भी 105 से अधिक नहीं है। इनपुट की अंतिम पंक्ति में तीन शून्य हैं। उन्हें संसाधित करने की आवश्यकता नहीं है।
आउटपुट स्वरूप
प्रत्येक डेटा सेट के लिए, निम्न प्रारूप में उत्तर को प्रिंट करें: यदि एक प्रभावी यात्रा योजना तैयार नहीं की जा सकती है, तो केवल पंक्ति में ही प्रिंट करें अन्यथा, पहली पंक्ति में हां, और दूसरे में - एम संख्या सड़क संख्या को दर्शाती है। सड़कों को उस क्रम में प्रदर्शित किया जाना चाहिए जिसमें उन्हें जाना चाहिए। जिस क्रम में उन्हें इनपुट दिया गया है, उसी क्रम में सड़कें एक से क्रमांकित हैं। प्रत्येक परीक्षण के लिए, सड़कों को स्वतंत्र रूप से गिना जाता है।

सुविधा के लिए, हम उन सड़कों की संख्या दर्शाते हैं जो शहर की ओर ले जाती हैं, जैसे कि _मैं । पहले, हमें यह निर्धारित करने की आवश्यकता है कि क्या कोई प्रभावी यात्रा योजना है। सबसे पहले, अगर दो शहर हैं i और j ऐसे हैं जो _i with 0 के साथ हैं और _j and 0 के साथ हैं और i और j के बीच कोई रास्ता नहीं है, तो हम एक योजना नहीं बना सकते हैं। यह ध्यान दिया जाना चाहिए कि पथ में न केवल सड़कें हो सकती हैं, बल्कि टेलीपोर्टर्स भी हो सकते हैं।
मान लीजिए हमने पहले से ही कुछ रास्ता बनाया है जो सभी सड़कों से गुजरता है। यह स्पष्ट है कि सभी शहरों के लिए जो टेलीपोर्ट से नहीं जुड़े हैं, वे रास्ते में पहला या आखिरी शहर नहीं हैं, _मैं भी होना चाहिए। यदि दो शहर i और j टेलीपोर्ट से जुड़े हुए हैं और उनमें से कोई भी रास्ते में न तो पहला और न ही आखिरी शहर है, तो _{i के} साथ _यह _{j के} बराबर होना चाहिए।
गौर कीजिए कि उन शहरों का क्या होता है जो रास्ते के छोर पर स्थित हैं। सबसे पहले, अगर शहर i को j के लिए teleported किया जाता है और रास्ते के अंत में स्थित है, तो _i = _j + 1 के साथ (मामले के अलावा जब j भी पथ का अंत है)। इसके अलावा, यदि मार्ग शहर i में शुरू और समाप्त होता है, तो _i = _j + 2 के साथ। यदि शहर टेलीपोर्ट द्वारा दूसरे से जुड़ा नहीं है और पथ के एक छोर पर है, तो यह मेरे साथ विषम हो सकता है।
परिणामस्वरूप, एक पथ के अस्तित्व को सत्यापित करने के लिए, निम्नलिखित किया जाना चाहिए। हम प्रत्येक शहर के लिए एक निश्चित मान _{i की} गणना करते हैं। यदि शहर i को j द्वारा टेलीपोर्ट से जोड़ा जाता है, तो एक _i = अधिकतम (0, c _i - c _j )। अन्यथा, एक _i = _i mod 2. यदि सभी _i का योग दो या शून्य के बराबर है, तो पथ मौजूद है, अन्यथा नहीं।
देश की यात्रा की योजना का निर्माण एक नियमित स्तंभ में यूलर पथ के निर्माण के समान है। _I to 0 के साथ शीर्ष से खोज शुरू करना आवश्यक है; यदि कोई नहीं है, तो _i moving 0. वाले किसी भी व्यक्ति के साथ। अगले शीर्ष पर जाते समय, यदि यह टेलीपोर्ट द्वारा किसी अन्य शीर्ष से जुड़ा हुआ है, तो आपको बस इसके पास जाने और आगे के रास्ते की खोज जारी रखने की आवश्यकता है। पथ जो वास्तव में पूरी तरह से पाया गया है वह एक नियमित ग्राफ में यूलर पथ के अस्तित्व के प्रमाण के समान है।
परिणामी कठिनाई हे (n + m + k) है।

समस्याओं के सभी समाधान रूसी कोड कप की आधिकारिक वेबसाइट पर भी प्रकाशित किए जाएंगे। जो लोग अंत तक पढ़ चुके हैं और उत्साह महसूस करते हैं, वे अगले क्वालीफाइंग दौर के लिए पंजीकरण कर सकते हैं - अभी भी समय है!

रूसी कोड कप 2013: पहले योग्यता दौर के कार्यों का विश्लेषण

More articles: