रूसी कोड कप का अंतिम क्वालीफाइंग दौर समाप्त हो गया है। क्वालीफाइंग दौर में सर्वश्रेष्ठ 600 प्रतिभागी सेमीफाइनल में गए। 16 जून को हम मन की लड़ाई देखेंगे, पचास विजेता फाइनल में जाएंगे, जहां 18 हजार डॉलर की दौड़ होगी।



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

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

क्वालीफाइंग राउंड के कार्य काफ़ी अधिक जटिल और इससे भी अधिक दिलचस्प होंगे। वेबसाइट पर 16 जून को 11:00 बजे "चीयर" के लिए आओ।

"चॉकलेट"

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

जाहिर है, अगर कोई जोड़ी "बाएं आधे की चौड़ाई" - "दाएं आधे की चौड़ाई" कुल मिलाकर n नहीं देती है - चॉकलेट बार की चौड़ाई, "हां" लिखें।

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

"खेल"

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

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

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


नतीजतन, समस्या का समाधान बेहद सरल हो जाता है - एक चाल में पहले खिलाड़ी की जीत को प्रदर्शित करने के लिए, यदि अंकों के बीच की दूरी निर्दिष्ट सीमा से कम या बराबर है, और अन्य मामलों में "इन्फिनिटी" प्रदर्शित करते हैं।

"घंटे"

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

आरंभ करने के लिए, मिनट हाथ की स्थिति के लिए बहुत सारे मान तैयार करें।

if (m == -1) { //     , //       mins = new int[60]; for (int i = 0; i < 60; i++) mins[i] = i; } else { //   ,       () mins = new int[]{m}; } 

दक्षिणावर्त के साथ भी ऐसा ही करें:

  if (h == -1) {//     , //       hours = new int[12]; for (int i = 0; i < 12; i++) hours[i] = i; } else { //   ,       () hours = new int[]{h}; } 

अगला, हम इन सेटों के पूरे उत्पाद के माध्यम से जाते हैं और एक दूसरे के सापेक्ष तीरों की सही स्थिति की जांच करते हैं।

मिनट का हाथ	0-11	12-23	24-35	36-47	48-59
घंटे का हाथ (मि। डिवीजनों में)	5 * एच + 1	5 * एच + 2	5 * एच + 3	5 * एच + 4	5 * एच + 5
	5 * एच + इंट (एम / 12)

सही स्थिति की जाँच करने का सूत्र सरल है - 5 * h + mm / 12।

 for (int hh : hours) { //          for (int mm : mins) {//       int hhh = hh; // hhh –       if (hours.length != 1) hhh = hhh * 5 + mm / 12; //         //  check .  // a =      // b =      ans += check(a, b, hhh, mm, h == -1, m == -1) ? 1 : 0; } } 

चेक सहायक फ़ंक्शन यह जांचता है कि मिनट और घंटे के हाथों की सापेक्ष स्थिति मौजूद हो सकती है या नहीं और हाथों की स्थिति उनकी दृश्यता के अनुरूप है या नहीं।

 boolean check(int a, int b, int hh, int mm, boolean hInside, boolean mInside) { // a =      // b =      // hh =       // mm =    // hInside =     // mInside =     boolean hOk = inside(a, b, hh) ^ hInside; boolean mOk = inside(a, b, mm) ^ mInside; return hOk && mOk && (hh % 5 == mm / 12); } // ,    m   a,b boolean inside(int a, int b, int m) { if (a <= b) return a <= m && m <= b; return inside(a, 59, m) || inside(0, b, m); } 

GAS "कतार"

इस कार्य के लिए शर्त यह है कि इसे पूर्ण रूप से यहां लाया जाए:

“पिछले कुछ वर्षों में, इलेक्ट्रॉनिक लाइनों ने रोजमर्रा की जिंदगी में मजबूती से प्रवेश किया है। कई सरकारी एजेंसियों में, आप एक ऐसे टर्मिनल से मिल सकते हैं जो एक नंबर के साथ कागज के एक टुकड़े को प्रिंट करता है, और सामान्य प्रश्न पूछे बिना कि कौन अंतिम है? ”, आगंतुक इलेक्ट्रॉनिक स्कोरबोर्ड का उपयोग यह पता लगाने के लिए करेंगे कि उन्हें कितना समय इंतजार करना होगा और कब उनकी बारी होगी।

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

यह ज्ञात है कि प्रत्येक व्यक्ति में चिड़चिड़ापन के रूप में ऐसी कसौटी है। यदि यह पैरामीटर w के बराबर है, तो लाइन में प्रतीक्षा करने के टी घंटों के बाद, यह व्यक्ति अधिकारी के सिर पर क्रोध और दुर्व्यवहार की बिल्कुल wt इकाइयों को नीचे लाएगा। इसलिए, यदि किसी आगंतुक को उसके आने के तुरंत बाद सेवा दी जाती है, तो अधिकारी को नुकसान नहीं होगा, और अगर आगंतुक तीसरे घंटे की शुरुआत में आया, और उसकी सेवा केवल पांचवें की शुरुआत में शुरू हुई - क्रोध की मात्रा 2w होगी।

यह भी ज्ञात है कि प्रत्येक आगंतुक को सेवा देने में ठीक एक घंटा लगता है, और प्रत्येक आगंतुक एक घंटे की शुरुआत में आता है। आपका कार्य यह निर्धारित करना है कि आपके चिड़चिड़ापन संकेतकों और आगंतुकों के आगमन के समय के अनुसार ग्राहक सेवा के इष्टतम आदेश के साथ एक अधिकारी को कितनी नकारात्मकता मिलेगी।

पहली पंक्ति में एक एकल पूर्णांक t है - उन मामलों की संख्या जिन्हें आपको संभालना है। निम्नलिखित मामलों के विवरण स्वयं हैं।

प्रत्येक मामले के विवरण में निम्न शामिल हैं: पहली पंक्ति में नंबर n - आगंतुकों की संख्या, और स्वयं आगंतुकों का एन विवरण। प्रत्येक आगंतुक के लिए, एक अलग लाइन में, दो पूर्णांक री और wi (1, ri, wi - 106) को इंगित किया जाता है - उस समय की संख्या जिस पर आगंतुक पहुंचे, और उसकी चिड़चिड़ापन गुणांक क्रमशः।

एक परीक्षण के सभी मामलों में आगंतुकों की कुल संख्या 1,000,000 से अधिक नहीं है।

प्रत्येक मामले के लिए, एक अलग लाइन पर, उत्तर प्रदर्शित किया जाना चाहिए - अधिकारी को प्राप्त होने वाली नकारात्मक की न्यूनतम कुल राशि। "

कार्य का एक उदाहरण वर्णित सिद्धांत को प्रदर्शित करता है। उदाहरण में, तीन आगंतुक अधिकारी के पास आए। इनमें से, दो - क्रमशः चिड़चिड़ापन "3" और "4" के साथ पहले घंटे की शुरुआत में। और एक और - चिड़चिड़ापन "5" के साथ दूसरे घंटे की शुरुआत में। प्रत्येक को सेवा देने में एक घंटा लगता है, इसलिए पहले घंटे की शुरुआत में दो विकल्प होते हैं - आगंतुक को चिड़चिड़ापन "4" या चिड़चिड़ापन "3" के साथ आगंतुक के आगे छोड़ दें। जिसे याद नहीं किया गया है वह अगले घंटे तक चलता है, जहां एक और आगंतुक "5" जोड़ा जाता है, और दो और विकल्प हैं - नए व्यक्ति को छोड़ दें, या जो लाइन में खड़ा है।

	-सेंट से नाराज जो आया था	विकल्प 1	विकल्प 2	विकल्प 3	विकल्प 4
1 घंटे की शुरुआत	३, ४	पी (3), आरएफ = 0	पी (3), आरएफ = 0	पी (4), आरएफ = 0	पी (4), आरएफ = 0
2 घंटे की शुरुआत	5	पी (4), आरएफ = 4 × 1 = 4	पी (5), आरएफ = 4 × 1 = 4	पी (3), आरएफ = 3 × 1 = 3	पी (5), आरएफ = 3 × 1 = 3
3 घंटे की शुरुआत	-	पी (5), आरएफ = 4 + 5 = 9	पी (4), आरएफ = 4 × 2 = 8	पी (5), आरएफ = 3 + 5 = 8	पी (3), आरएफ = 3 × 2 = 6
					न्यूनतम

दो घंटे के लिए, अधिकारी न्यूनतम चिड़चिड़ापन 6 प्राप्त करता है।

इस समस्या को हल करने वाला एल्गोरिथ्म काफी सरल है, अगर आप इस तथ्य का अनुमान लगाते हैं कि हर पल उस व्यक्ति की सेवा करना सबसे अधिक लाभदायक है जो इस समय पहले ही आ चुका है, तो अभी तक सेवा नहीं दी गई है, और जिसकी चिड़चिड़ापन बाकी लोगों की तुलना में कम नहीं है।

इस कथन को सिद्ध करते हैं। आइए हम इस नियम के अनुसार निर्मित कुछ अनुसूची और कुछ इष्टतम कार्यक्रम निर्धारित करें। समय टी ₁ में पहले बिंदु पर विचार करें जिस पर वे भिन्न होते हैं। बता दें कि जिस व्यक्ति को इस क्षण में सबसे ज्यादा शेड्यूल दिया जाता है, उसमें चिड़चिड़ापन w _{1 होता है} , और जो व्यक्ति इस पल में दूसरे की सेवा करता है - चिड़चिड़ापन w ₂ । इष्टतम शेड्यूल में, इस व्यक्ति को समय टी ₂ में कुछ बिंदु पर परोसा जाता है, और टी ₂ > टी ₁ (आखिरकार, जब तक कि टी ₁ शेड्यूल समान नहीं थे)। इसका मतलब यह है कि अगर हम इन दो लोगों के स्थानों को इष्टतम अनुसूची में बदल देते हैं, जो कि, जाहिर है, किया जा सकता है, क्योंकि समय टी ₁ और समय टी _{2 पर} वे दोनों उपलब्ध हैं (चूंकि दोनों अनुसूचियाँ वैध हैं), फिर इष्टतम अनुसूची में कुल गुस्सा परिवर्तन (टी ₂ - टी ₁ ) × डब्ल्यू ₁ + (टी ₁ - टी ₂ ) × डब्ल्यू ₂ , जो (टी ₂ - टी ₁ ) × (डब्ल्यू ₁ - डब्ल्यू ₂ ) के बराबर है।

चूंकि टी ₂ > टी ₁ (जैसा कि ऊपर कहा गया है), और डब्ल्यू ₂ > डब्ल्यू ₁ (अध्ययन अनुसूची का निर्माण करके), क्रोध परिवर्तन की संकेतित राशि नकारात्मक होगी, जिसका अर्थ है कि इष्टतम अनुसूची में सुधार हुआ है। जाहिर है, अन्य सभी विसंगतियों के लिए इस तरह का तर्क इस तथ्य को जन्म देगा कि ऊपर वर्णित कतार एल्गोरिदम सही है।

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

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

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

आप इस एल्गोरिथ्म के बारे में यहाँ विस्तार से जान सकते हैं: http://www.rsdn.ru/article/submit/heap/heaps.xml#EKLAC

"हस्तक्षेप"

इस समस्या में, ज्ञात बहुपद धमनियों से क्षतिग्रस्त डेटा (34 बिट्स के संदेशों का एक सेट) को पुनर्प्राप्त करने के लिए एक एल्गोरिदम लिखना आवश्यक था। एक संदेश को पुनर्स्थापित करना आवश्यक है जो मूल से सबसे कम बिट्स के साथ भिन्न होता है जिसमें समान हैश होता है।

समस्या के एक विस्तृत विवरण के लिए, रूसीकोडसुप्पन देखें

सभी 34-बिट संख्याओं के माध्यम से छंटनी - और यह 17 बिलियन मान है - बहुत लंबा समय लगेगा। एन्यूमरेशन को ऑप्टिमाइज़ करने के लिए, मीट-इन-बीच नामक एक विधि का उपयोग किया जाता है।

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

हमारे मामले में, हमें पहले n / 2 बिट्स और nn / 2 बिट्स के लिए सभी प्रकार के विकल्पों के लिए अलग से हैश की गणना करने की आवश्यकता है। प्रत्येक छमाही में, अधिकतम 2 ¹⁷ = 131072 विकल्प प्राप्त होते हैं।

 int m = (len + 1) / 2; //  ó  Pair[] h1 = new Pair[1 << m]; //    for (int i = 0; i < h1.length; i++) { h1[i] = new Pair(i, countHash(i)); //     } Pair[] h2 = new Pair[1 << (len – m)]; for (int i = 0; i < h2.length; i++) { h2[i] = new Pair(i, countHash(((0L + i) << m))); //   } 

चूँकि हमें एक निश्चित ज्ञात हैश h के साथ एक संदेश प्राप्त करने की आवश्यकता है, इसलिए बिट्स h ₁ के पहले भाग के लिए हैश मान के प्रत्येक संस्करण को बिट्स h ₂ के दूसरे भाग के लिए एक से अधिक हैश मान के साथ जोड़ा गया है जैसे कि h = (h ₁ + h ₂ ) mod M ।

यह प्रत्येक संस्करण h _{1 के} लिए सीखना बना रहता है ताकि h ₂ के संबंधित मान _को जल्दी से खोजा _जा सके। आप जावा में C ++ या ट्रीसेट और हैशसेट में सेट किए गए डेटा स्ट्रक्चर्स का उपयोग कर सकते हैं।

आप आरोही क्रम में पहली और दूसरी छमाही के लिए सभी प्रकार के हैश को सॉर्ट कर सकते हैं और "दो पॉइंटर्स" के विचार का उपयोग कर सकते हैं।

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

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

• पहली योग्यता से डिबेटिंग
• दूसरी योग्यता से डिबेटिंग

अलाइव रउफ,
अनुसंधान और शिक्षा निदेशक
Mail.Ru Group