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

आरसीसी 2014 का दूसरा क्वालीफाइंग दौर रविवार, मई 18 को आयोजित किया गया था। राउंड में भाग लेने के लिए पंजीकृत 5451 लोगों ने भाग लिया, जिनमें से 1500 से अधिक ने भाग लिया, जिनमें से कम से कम एक निर्णय 886 प्रतिभागियों ने भेजा। कुल मिलाकर, 4890 फैसले दौर के दौरान भेजे गए थे।



कोरोटकेविच गेनेडी (पर्यटक), आरसीसी 2013 के विजेताओं में से एक, ने आत्मविश्वास से द्वितीय योग्यता दौर के प्रतिभागियों की तालिका में पहली पंक्ति ली, जिसमें कम से कम जुर्माना समय के साथ सभी 5 समस्याओं को हल किया। क्रमशः ए, बी, सी और ई को 4:22, 9:40, 16:25 और 50:29 मिनट में हल करने के लिए राउंड में सभी प्रतिभागियों में गेन्नेडी भी पहले थे। 30:17 मिनट पर पहला, दिमित्री स्यूतिगिन (मोरजेनो) द्वारा कार्य डी हल किया गया था। 2 वें क्वालिफिकेशन राउंड के परिणामों के अनुसार, 200 सर्वश्रेष्ठ स्पोर्ट्स प्रोग्रामर क्वालीफाइंग राउंड में चले गए, और 11 लोगों को न्यायाधीशों द्वारा धोखाधड़ी के लिए अयोग्य घोषित किया गया।



पहले दो राउंड में क्वालीफाई नहीं करने वाले प्रतिभागी 3rd और 4th क्वालिफिकेशन राउंड में भाग ले सकते हैं, जो 24 मई को 19:00 बजे और 1 जून को 13:00 मॉस्को समय पर आयोजित किया जाएगा।



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



टास्क ए टीम ओलंपियाड ।

विचार: विटाली अक्षेनोव।

कार्यान्वयन: एंड्री कोमारोव।

विश्लेषण: विटाली एसेनोव।

इस कार्य में सबसे तार्किक उस प्रकार के कार्यों की संख्या के माध्यम से तुरंत हल करना है जिसे वास्या ने हल किया था। मान लीजिए कि उन्होंने पहले प्रकार की vn समस्याओं को हल किया है, तो यह स्पष्ट है कि दूसरे प्रकार की समस्याओं की अधिकतम संख्या जो वासिका ओलंपिक के लिए हल कर सकती है (n-vn • p) / q है। कुल में, हमारे पास पहले प्रकार की n - vn समस्याएं हैं और दूसरे की m - vm। हमें इन नंबरों की शून्य के साथ तुलना करना नहीं भूलना चाहिए।

हम पहले और दूसरे प्रकार के कार्यों की अधिकतम संख्या की गणना करेंगे जिन्हें ओलंपियाड के लिए हल किया जा सकता है। पहला प्रकार maxn = t / p है, और दूसरा maxm = t / q है। गणना किए गए मानों के लिए धन्यवाद, उत्तर की गणना करना आसान है: 1 + (n - vn + maxn - 1) / maxn + (m - vm + maxm - 1) / maxm।



टास्क बी। तीन बदमाश ।

विचार: जॉर्ज कोर्निव।

कार्यान्वयन: डेमिड कुचेरेंको।

विश्लेषण: विटाली एसेनोव।

ध्यान दें कि आप केवल 3 से वर्ग 3 में बदमाशों को रख सकते हैं। कोई भी अन्य व्यवस्था बदमाशों के इस हस्तांतरण को कम करती है। दो उपाय हैं। पहला बस एक 3 से 3 वर्ग में सभी संभव तीन-बदमाश व्यवस्था पर चला जाता है।

दूसरा 3 बदमाशों की आपसी व्यवस्था के लिए सभी विभिन्न विकल्पों की जाँच करता है:

* (1, 1), (2, 2), (3, 3)। बीट 3 • एन + 3 • एम - 12 सेल।

* (1, 1), (1, 2), (2, 3)। बीट 2 • एम + 3 • एन - 9 सेल।

* (1, 1), (2, 1), (3, 2)। बीट 3 • एम + 2 • एन - 9 सेल।

* (1, 1), (1, 2), (2, 1)। बीट 2 • एन + 2 • एम - 7 सेल।

* (1, 1), (1, 2), (1, 3)। बीट एम + 3 • एन - 6 सेल।

* (1, 1), (2, 1), (3, 1)। एन + 3 • मी - 6 कोशिकाओं को हराया।

अन्य सभी मामलों में, "IMPOSSIBLE" आउटपुट होना चाहिए।



टास्क सी। राजा और रानी ।

विचार: विटालि डीमनिअनुक।

कार्यान्वयन: पावेल क्रोटकोव।

विश्लेषण: पावेल क्रोटकोव।

ध्यान दें कि बोर्ड पर क्षेत्रों की अधिकतम संख्या आठ है। हम सीखेंगे कि उनमें से किसी एक का आकार कैसे खोजना है, और हम कई बार बोर्ड को फ्लिप करके और घुमाकर अन्य सभी के आकार पाएंगे।

निर्देशांक (x, y) के साथ एक कक्ष में रानी को खड़े होने दें, पंक्तियों और स्तंभों को स्क्रैच से क्रमांकित किया जाता है, और हम सीखना चाहते हैं कि ऊर्ध्वाधर रेखा के बाईं ओर स्थित क्षेत्र का आकार कैसे पता लगाएं, जिस पर रानी खड़ी है, और विकर्ण किरण के ऊपर सेल से उत्सर्जित है जिसमें रानी खड़ी है। ध्यान दें कि यदि यह किरण बोर्ड के ऊपरी किनारे (x, y) के विरुद्ध रहती है, तो इसका उत्तर 1 से x - 1. सभी संख्याओं का योग होगा। अन्यथा, इस मात्रा से उन कोशिकाओं की संख्या घटाना आवश्यक है जिन्हें रानी द्वारा पीटा जाएगा। यदि बोर्ड के किनारे के लिए नहीं। ऐसी कोशिकाओं की संख्या 1 से x - y -1 तक की सभी संख्याओं के योग के बराबर है।



टास्क डी। एक पेड़ ।

विचार: अन्ना मालोवा।

कार्यान्वयन: आर्टीम वासिलिव।

विश्लेषण: विटाली अक्षोनोव।

एक पेड़ को दिया जाता है जिसे दो कार्यों में एक शीर्ष से प्राप्त करने की आवश्यकता होती है: किनारे को काट लें और शीट में 2 कोने जोड़ दें। इस समस्या को हल करने के लिए, पहले हमें यह देखना चाहिए कि क्या डिग्री का एक शीर्ष है कम से कम 4. यदि यह है, तो पेड़ प्राप्त नहीं किया जा सकता है।



किसी अन्य मामले में, आप एक पेड़ का निर्माण कर सकते हैं। ऐसा करने के लिए, हम डिग्री 2 के वर्टिस v 2 और डिग्री 3 के v3 की गणना करते हैं। यदि डिग्री 2 का एक शीर्ष है, तो इसके प्रारंभिक एक को चुनते समय, हम एक पेड़ का निर्माण करेंगे (v 2 - 1) · 2 + (v 3 + 1), अन्यथा क्रियाओं की संख्या है ( v 2 + 1) · 2 + v 3. यह सच है क्योंकि डिग्री 3 के एक आंतरिक शीर्ष को प्राप्त करने के लिए, आपको दूसरे प्रकार के एक ऑपरेशन को लागू करने की आवश्यकता है, और डिग्री 2 के एक आंतरिक शीर्ष को प्राप्त करने के लिए आपको 2 कार्यों को लागू करने की आवश्यकता है।



टास्क ई। यात्रा कर ।

विचार: बोरिस मिनाएव।

कार्यान्वयन: बोरिस मिनाएव।

विश्लेषण: बोरिस मिनाएव।

ध्यान दें कि कर राजस्व हमेशा समान होता है, क्योंकि शहरों के किसी भी जोड़े के लिए दो निवासी हैं जो उन्हें जोड़ने वाले मार्ग के साथ ड्राइव करने जा रहे हैं।

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



हम उस आय की गणना करेंगे जो राष्ट्रपति को प्राप्त होगी यदि सभी सड़कों पर किराए जितना संभव हो उतना कम हो। इस राशि को आवश्यक से घटाएं। यदि हमें ऋणात्मक संख्या मिलती है, तो करों का एक भी संतोषजनक सेट नहीं है। ध्यान दें कि यदि हम एक गैर-नकारात्मक संख्या प्राप्त करते हैं, तो सड़कों की कुल संख्या 600 से अधिक नहीं होती है।



अब हमें बैकपैक समस्या के कुछ संशोधन को हल करने की आवश्यकता है। इसे डायनेमिक प्रोग्रामिंग की विधि द्वारा हल किया जाता है। हम बदले में सभी सड़कों पर विचार करेंगे। हम केवल एक निश्चित सड़क उपसर्ग का उपयोग करके एक निश्चित राशि एकत्र करने के कई तरीकों का समर्थन करेंगे। आइए अधिक विस्तार से विचार करें कि अगली सड़क को कैसे संभालना है। मान लीजिए कि इस सड़क पर टोल पर कर में वृद्धि से कुल लाभ में सी मौद्रिक इकाइयां जुड़ती हैं, और सड़क पर किराया 0 से अधिकतम तक हो सकता है। कैसे पता करें कि कुल आय मीटर प्राप्त करने के कितने तरीके हैं? वास्तव में, यह संख्या दो शब्दों के अपवाद के साथ कुल लाभ m - c प्राप्त करने के तरीकों की संख्या के साथ मेल खाती है। ये शब्द इस तथ्य के अनुरूप हैं कि हम किराया 0 के बराबर सेट कर सकते हैं, लेकिन हम अधिकतम + 1. नहीं कर सकते हैं, अर्थात, गतिशील प्रोग्रामिंग के प्रत्येक मूल्य की गणना तीन पहले से ही गणना मूल्यों का उपयोग करके की जा सकती है। इस प्रकार, अगली सड़क को ओ (मैक्स) में संसाधित किया जा सकता है, जहां मैक्स वह लाभ है जिसे राष्ट्रपति प्राप्त करना चाहता है।