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

RCC 2014 का तीसरा क्वालीफाइंग राउंड 24 मई शनिवार को हुआ था। राउंड में भाग लेने के लिए 5483 लोगों ने पंजीकरण कराया था, जिनमें 1500 से अधिक ने भाग लिया था, जिनमें से कम से कम एक निर्णय के लिए 893 प्रतिभागियों द्वारा भेजा गया था।



प्रिविशेंको बोगडान (लेब्रोन), लविवि नेशनल यूनिवर्सिटी के छात्र। इवान फ्रेंको, समस्या ए (त्रिकोण) को हल करने के लिए 2:25 मिनट पर पहला। समस्या बी (ओरिगामी) 4:44 मिनट पर पहली बार युलदाशेव मारत (स्नोबैबर), टास्क सी (मिता और काउंट) द्वारा हल की गई, सबसे पहले 10:34 मिनट पर मैक्सिम अहमदोव (ज़ोलेबेर) ने हल किया, समस्या डी (पुरस्कार) का सही समाधान 26:45 मिनट पर। सर्गेई कोपेलोविच (बुरुंडुक 1), और अंतिम कार्य ई (क्रिप्टोग्राफ़िक कुंजियाँ) द्वारा भेजा गया था, जो पावेल पोनमारेव (स्पर्म) द्वारा 54:38 मिनट पर सबसे जल्दी हल किया गया था।



तीसरे योग्यता दौर के परिणामों के अनुसार, धोखा देने के लिए कोई अयोग्यता नहीं थी, और 200 सर्वश्रेष्ठ खेल प्रोग्रामर क्वालीफाइंग दौर में चले गए।



जिन प्रतिभागियों ने पिछले तीन क्वालीफाइंग राउंड के दौरान क्वालीफाई नहीं किया है, उनके पास चौथे क्वालीफाइंग राउंड में भाग लेकर राउंड क्वालीफाई करने का अवसर है, जो 1 जून को 13:00 मॉस्को समय पर आयोजित किया जाएगा।



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



पहले ही तीसरे दौर की पूर्व संध्या पर, हमने आरसीसी में प्रयुक्त लगभग सभी प्रोग्रामिंग भाषाओं के संकलक संस्करणों को अपडेट किया। उन्होंने GNU C ++ (विजुअल C ++ 2013 पहले से ही C ++ 11 का समर्थन करता है) के तहत C ++ 11 में समाधान भेजने की क्षमता को जोड़ा और जावा 8 (जावा 7 भी अभी के लिए बना हुआ है) को जोड़ा। आप चैंपियनशिप नियमों के पेज < www.russiancodecup.ru/rules > पर संकलनकर्ताओं और संकलन लाइनों के वर्तमान संस्करणों को देख सकते हैं।



समस्या ए त्रिकोण ।

विचार: एंड्री स्टानकेविच।

कार्यान्वयन: अन्ना मालोवा।

विश्लेषण: अन्ना मालोवा



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



हम सेगमेंट के सभी संभावित ट्रायल पर जाते हैं। एक त्रिभुज तीन खंडों से बना हो सकता है यदि त्रिभुज असमानता रखती है, अर्थात, किसी भी दो पक्षों का योग तीसरे पक्ष की लंबाई से अधिक है।



लंबाई के बढ़ते क्रम में a, b, c सेगमेंट पर विचार करें। यदि समानता c2 = a2 + b2 रखती है, तो त्रिभुज आयताकार है, यदि c2 <a2 + b2 तीव्र-कोण है, और यदि c2> a2 + b2 है, तो आपत्तिजनक है



समस्या बी। Origami ।

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

कार्यान्वयन: निकोले वेदरनिकोव।

विश्लेषण: निकोले वेदरनिकोव।



समस्या में, यह जांचना आवश्यक है कि क्या आयत में b ऑन में क्षेत्र S का उप आयत मौजूद है जिसके किनारे मूल के समानांतर हैं।



ऐसा करने के लिए, हम संख्या एस के सभी एक्स-डिविजर्स के माध्यम से सॉर्ट करते हैं और जांचते हैं कि क्या x ≤ a और S ≤ x sort b है। यदि कम से कम एक जोड़ी x और S ying x अवरोधों को संतुष्ट करते हैं, तो एक समाधान मौजूद है।



एक परीक्षण मामले हे (sqrt (S)) के लिए परिचालन समय।



समस्या सी। मीता और गणना ।

विचार: जूरी।

कार्यान्वयन: विटालिक अक्षोनोव।

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



पहला अवलोकन इस प्रकार है: ग्राफ एक एज कैक्टस होना चाहिए। यदि यह उस तरह से काम नहीं करता है, तो निश्चित रूप से एक समान चक्र होगा। चूंकि यह एक कैक्टस है, इसलिए चक्रों की संख्या m - (n - 1) है। और चूंकि प्रत्येक चक्र में कम से कम 3 कोने होते हैं, तो 3 · (m - (n - 1)) at m। यह इस प्रकार है कि किनारों की अधिकतम संख्या 3 · (n - 1) / 2 है।



विषम एन के लिए, यह एक चक्की है, अर्थात 1 वर्टेक्स के साथ 3 चौराहे की लंबाई का एक चक्र है, और विषम एन के लिए यह लगभग समान है, लेकिन एक और लटका हुआ शीर्ष एक किनारे से किसी अन्य से जुड़ा हुआ है।



टास्क डी। पुरस्कार ।

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

कार्यान्वयन: विटालिक अक्षोनोव।

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



हम जानते हैं कि प्रतिभागियों को दी जाने वाली कैंडी की संख्या समूह संख्या के आधार पर घटनी चाहिए। यह सत्यापित करना आसान है कि मिठाई के किसी भी संतोषजनक विभाजन को निम्नलिखित तरीके से दर्शाया जा सकता है:



पहले समूह में, बच्चे n कैंडीज़ प्राप्त करते हैं, दूसरे में - n-1 कैंडीज़, ..., आखिरी में - 1 कैंडी। अगला, हम समूह उपसर्ग पर सभी बच्चों के लिए एक कैंडी जोड़ सकते हैं। इसका मतलब यह है कि हम संख्या पी का चयन कर सकते हैं और किसी भी i choose पी के लिए एक के बाद एक को बढ़ा सकते हैं।



चूंकि हमने प्रारंभिक वितरण का चयन किया है, इसलिए n · a1 + ... + 1 · तुरंत कैंडी की कुल संख्या से घटाया जा सकता है। यह देखना आसान है कि वितरण ऑपरेशन bp = a1 + ... + ap को घटाता है। यही है, हमें यह जांचने की आवश्यकता है कि क्या हम कुछ बी 1, ..., बीएन के रूप में डी का प्रतिनिधित्व कर सकते हैं, और यह एक मानक बैकपैक समस्या है।



रनटाइम O (nd)।



समस्या ई। क्रिप्टोग्राफिक कुंजी ।

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

बोध: विटालि दुमंजुक।

विश्लेषण: विटाली डमींजुक



संख्या a1, a2, ..., a के समुच्चय को देखते हुए। वह एनसीडी और एनओसी के संचालन के संबंध में बंद था। यह पता लगाना आवश्यक है कि क्या एक दी गई संख्या v एक बंद सेट एस से संबंधित है।



हम p1q1p2q2 के रूप में v का प्रतिनिधित्व करते हैं ... pkqk, qi> 0, जहां p1, P2, ..., pk primes हैं। S से संबंधित v के लिए, यह आवश्यक है कि प्रत्येक i, 1 ≤ i there k के लिए, वहाँ मौजूद j, 1, j ≤ n हो, जैसे कि piqi andaj और piqi + 1 .aj। यह तथ्य इस तथ्य से अनुसरण करता है कि हम NOC (GCD (...), GCD (...), ..., GCD (...)) के रूप में किसी भी संख्या का प्रतिनिधित्व कर सकते हैं, क्योंकि min (a, max) बी, सी)) = अधिकतम (न्यूनतम (ए, बी), मिनट (ए, सी)) और अधिकतम (ए, मिनट (बी, सी)) = न्यूनतम (अधिकतम (ए, बी), अधिकतम (ए, सी) )। हम ci को संख्या aj के सबसे बड़े सामान्य भाजक के बराबर सेट करते हैं जैसे कि piqi iaj। यदि सभी ci को विभाजित करते हैं, तो v, S. से संबंधित है। इसे सभी ci के सबसे छोटे सामान्य गुणकों के रूप में प्राप्त किया जा सकता है। अन्यथा, v का संबंध S से नहीं है (यह GCD और LCL के संचालन के गुणों से आता है)।



ऑपरेटिंग समय O (nk + sqrt (v)), जहां k v के प्रधान विभाजकों की संख्या है।