🗡️ 🏛️ 🕛 बैकएंड डेवलपर्स के बीच प्रोग्रामिंग चैम्पियनशिप की योग्यता का विश्लेषण 🧑🏾‍🤝‍🧑🏻 🚴🏽 👨🏽‍🍳

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

योग्यता एक सप्ताह तक रहती है, और प्रतिभागियों की संख्या हजारों में होती है, इसलिए कार्य तैयार करना, यह पता चलता है, यह एक आसान काम नहीं है। कुल मिलाकर, हमें 24 कार्य करने थे और उन्हें चार विकल्पों के बीच विभाजित करना था ताकि विकल्प जटिलता में तुलनीय हों।

इस बार हम छह कार्यों के साथ आए, जिनमें से प्रत्येक के लिए कई वैकल्पिक योगों के साथ आना संभव था: एक आविष्कार किए गए कार्य ने एक ही बार में चार को जन्म दिया! इस प्रकार, विकल्प जितना संभव हो उतना तुलनीय हो गया।

इसलिए, मैं सभी 24 समस्याओं का विश्लेषण प्रकाशित नहीं करूंगा। इसके बजाय, मैं योग्यता विकल्पों में से एक के छह कार्यों का विश्लेषण करूंगा: दूसरों को इसी तरह से हल किया जाता है।

उ। अलार्म

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

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

प्रोग्रामर अलेक्सी रात में काम करना पसंद करते हैं और देर से काम पर आना पसंद नहीं करते। सुबह ठीक से जागने के लिए, एलेक्सी हर रात शुरू होता है $एन$ अपने फोन पर अलार्म। प्रत्येक अलार्म घड़ी की स्थापना की जाती है ताकि यह हर बजता रहे $X$ उस समय के बिंदु से जब वह लाया था। उदाहरण के लिए, यदि एक अलार्म समय पर एक बिंदु पर सेट किया गया था $t_i$ तब वह कई बार फोन करेगा $t_i$ । $t_i + X$ । $t_i + 2 \ cdot X$ आदि। यदि एक ही समय में कोई दो अलार्म बजने लगते हैं, तो उनमें से केवल एक ही प्रदर्शित होता है।

यह ज्ञात है कि जागने से पहले, एलेक्सी हर सुबह सुनता है $K$ अलार्म घड़ियों, जिसके बाद यह जागता है। उस समय को निर्धारित करें जब एलेक्स उठता है।

सभी अलार्म पूर्णांक समय पर बजते हैं, और सभी अलार्म में एक ही कॉल स्नूज़ अवधि होती है। यदि दो अलार्म समय बिंदुओं पर सेट किए गए हैं $t_i$ और $t_j$ , और समय में ये बिंदु विभाजित होने पर समान शेष देते हैं $X$ , आप केवल एक अलार्म घड़ी छोड़ सकते हैं - वह जो पहले बजता है।

तो पहला कदम अनावश्यक अलार्म से छुटकारा पाने के लिए है: हम उन्हें विभाजन के शेष भाग के मूल्य से जोड़ देंगे $X$ और प्रत्येक समूह से हम केवल एक अलार्म घड़ी को जल्द से जल्द निर्धारित करेंगे।

अब हम सीखेंगे कि एक निश्चित समय में कितने अलार्म बजाने हैं, यह निर्धारित करना है $T$ । यदि अलार्म समय पर सेट किया गया है $t_i$ समय के अनुसार उसकी कॉल की संख्या $T$ बराबर होगा

$अधिकतम \ Big (\ frac {T-t_i} {X}, 0 \ Big)$

सभी अलार्मों के लिए इन मानों को जोड़ने पर, हम समय के साथ रिंगिंग अलार्म की कुल संख्या प्राप्त करते हैं $T$ ।

उसके बाद, प्रारंभिक समस्या को द्विआधारी खोज द्वारा हल किया जाता है $T$ : वृद्धि के साथ $T$ रिंगिंग अलार्म की संख्या कम नहीं होती है (यानी फ़ंक्शन नीरस है); आप प्रारंभिक बाईं सीमा के रूप में 0 का चयन कर सकते हैं, और दाईं ओर की समस्या में अधिकतम संभव उत्तर दे सकते हैं।

बी स्पोर्ट्स टूर्नामेंट

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

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

टूर्नामेंट गेम ग्राफ को पुनर्स्थापित करके इस समस्या को हल किया जा सकता है। शुरू करने के लिए, यह प्रत्येक प्रतिभागी के लिए स्पष्ट है कि वह टूर्नामेंट के किस चरण में पहुंचा है: यह उसकी भागीदारी के साथ खेलों की संख्या से निर्धारित होता है।

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

टूर्नामेंट योजना को बहाल करने के बाद, यह केवल उत्तर मुद्रित करने के लिए रहता है।

सी। दिलचस्प खेल

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

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

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

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

इस कार्य में सबसे महत्वपूर्ण बात यह है कि प्रत्येक नई चाल के बाद कौन से खिलाड़ी और कितने अंक से सम्मानित किए जाते हैं, इस शर्त को सही ढंग से समझना है, और यह भी कि किस परिस्थिति में खिलाड़ी उन्हें कमाता है।

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

इस कार्य के कुछ संस्करणों में, खिलाड़ियों को उसी कार्ड के लिए एक ही समय में अंक प्राप्त करने की स्थिति को संभालना आवश्यक था।

यह कार्य योग्यता के सभी कार्यों में से सबसे आसान था।

डी। अपवाद विश्लेषक

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

हम एक प्रोग्रामिंग भाषा के सिंटैक्स का वर्णन करते हैं $EX$ :

func f() {...} - फ़ंक्शन घोषणा (कोष्ठक में - निकाय)
maybethrow Exc एक कमांड है, जो कि maybethrow Exc का अपवाद फेंक सकता है, या नहीं फेंक सकता है।
try {...} suppress Exc - यदि इस ब्लॉक के अंदर Exc टाइप का अपवाद होता है, तो इसे दबा दिया जाता है।
f() लिए एक कॉल है।

भाषा में $EX$ फ़ंक्शन की घोषणाओं को छोड़कर सभी निर्देश केवल एक फ़ंक्शन के शरीर में हो सकते हैं। कार्यों को अन्य कार्यों के अंदर घोषित नहीं किया जा सकता है। एक फ़ंक्शन को परिभाषित करने से पहले, साथ ही साथ अपने स्वयं के शरीर में भी बुलाया जा सकता है। भाषा में कार्यों और अपवादों के नाम $EX$ नियमित अभिव्यक्ति से मेल खाना चाहिए $[a-zA-Z0-9 \ _] +$ , अद्वितीय maybethrow और कीवर्ड के maybethrow मेल न करें, try , maybethrow , maybethrow ।

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

यह कार्य सभी योग्यता कार्यों के लिए सबसे कठिन निकला।

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

हम कुछ अपवादों और सभी कार्यों को चुनेंगे जो इसे जन्म दे सकते हैं। इन कार्यों को अन्य कार्यों से बुलाया जाता है; शायद कॉल्स try {...} suppress अंदर हैं try {...} suppress ब्लॉक try {...} suppress दबाएं - इस मामले में अपवाद उस फ़ंक्शन पर लागू नहीं होता है जिसमें कॉल होती है। इस प्रकार, उन सभी फ़ंक्शंस को निर्धारित करना संभव है, जिनसे ग्राफ की चौड़ाई ट्रावरल का उपयोग करके इस अपवाद को फेंक दिया जा सकता है।

सभी संभावित अपवादों के लिए बाईपास किए जाने के बाद, यह केवल एक उत्तर बनाने के लिए रहता है।

ई। डिकोडिंग

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

इंटरनेट पर एक नई सेवा सामने आई है। दुर्भाग्य से, उसके पास कोई दस्तावेज नहीं है। जाहिर है, सर्वर से स्ट्रिंग s प्राप्त हुआ था। हालाँकि, इस पंक्ति के कुछ अक्षर एन्कोडेड हैं - वास्तविक उत्तर पाने के लिए, आपको कई बार इस लाइन को डिकोड करना होगा। चूंकि सेवा के लिए कोई दस्तावेज नहीं है, इसलिए आगे के प्रयोगों के लिए यह निर्धारित करना आवश्यक है कि गैर-तुच्छ तरीके से इस लाइन की अधिकतम संख्या को कितनी बार डिकोड किया जा सकता है। डिकोडिंग प्रक्रिया निम्नानुसार है: आपको फॉर्म के सभी सबस्ट्रिंग को खोजने की आवश्यकता है ~XY , जहां X और Y बड़े या छोटे हेक्साडेसिमल अंक हैं और उन्हें एक साथ ASCII कोड वाले चरित्र के साथ प्रतिस्थापित करना है $16X + Y$ (प्रत्येक प्रतिस्थापन का अपना है)। यदि इस प्रकार का कोई पदार्थ नहीं है, तो डिकोडिंग को तुच्छ कहा जाता है।

एक पंक्ति में मूल स्ट्रिंग के लगातार गैर-तुच्छ डिकोडिंग की अधिकतम संख्या प्रिंट करें।

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

परिणामी डिकोड किए गए स्ट्रिंग के प्रत्येक चरित्र के लिए, आपको यह याद रखना चाहिए कि मूल स्ट्रिंग को डिकोड करने के लिए इसे कितनी बार प्राप्त करना है। यह स्पष्ट है कि स्ट्रिंग में जोड़ा गया वर्ण शून्य बार डिकोड किया गया है। यदि प्रतीक डिकोड हो जाते हैं, तो अगले डिकोडिंग ऑपरेशन में भाग लेते हैं $r_1, r_2, ..., r_k$ कई बार, तब उनके द्वारा बनाए गए प्रतीक की आवश्यकता होती है $अधिकतम (r_1, r_2, ..., r_k) + 1$ डिकोडिंग ऑपरेशन।

बता दें कि अंतिम डिकोडेड स्ट्रिंग में अक्षर हैं $a_1, ..., a_k$ , जिसे प्राप्त करने के लिए क्रमशः डिकोडिंग करना आवश्यक था, $r_1, ..., r_k$ समय। तो जवाब है मात्रा

$अधिकतम (r_1, ..., r_k)$

एफ। एक ब्रेकिंग कमिटमेंट ढूँढना

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

यैंडेक्स खोज तथाकथित "ग्रीन ट्रंक" नीति को लागू करता है: कोई भी कोड जो कुछ कैविटीज़ के साथ रिपॉजिटरी में प्रवेश करता है, को विधानसभा और परीक्षणों को नहीं तोड़ने की गारंटी दी जाती है।

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

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

संसाधनों को बचाने के लिए, परीक्षण प्रणाली एक समय में केवल एक प्रतिबद्ध जांच कर सकती है। आपको एक प्रोग्राम लिखने की ज़रूरत है जो संख्या एम निर्धारित करेगा।

इस कार्य का हमारे उत्पादन में एक प्रोटोटाइप है: खोज घटकों के कुछ परीक्षण वास्तव में बहुत जटिल हैं, वे प्रत्येक प्रतिबद्ध के लिए चलाने के लिए बहुत महंगे हैं, और उनके लिए कार्य में वर्णित एक के समान ब्रेकडाउन खोजने की प्रक्रिया लागू की गई है। बेशक, डेवलपर्स प्री-ऑडिट सत्यापन का उपयोग कर सकते हैं और, एक नियम के रूप में, ऐसा करते हैं, इसलिए इस प्रक्रिया की इतनी बार आवश्यकता नहीं है।

कार्य के विभिन्न संस्करणों को एक ही समय में जांचे जाने वाले कमिट की संख्या में भिन्नता है।

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

क्वालिफिकेशन राउंड टास्क की चर्चा कोडफोर्स ट्रेनिंग के रूप में उपलब्ध है। हमने फाइनल के कार्यों पर एक प्रशिक्षण भी किया।

बैकएंड डेवलपर्स के बीच प्रोग्रामिंग चैम्पियनशिप की योग्यता का विश्लेषण

उ। अलार्म

बी स्पोर्ट्स टूर्नामेंट

सी। दिलचस्प खेल

डी। अपवाद विश्लेषक

ई। डिकोडिंग

एफ। एक ब्रेकिंग कमिटमेंट ढूँढना

More articles: