27 मई को Mail.Ru Group Programming Contest रूसी कोड कप 2012 का पहला चरण पूरा हुआ । कुल मिलाकर, एक हजार से अधिक लोगों ने RCC'12 में भाग लिया, जिनमें से 200 सर्वश्रेष्ठ प्रतियोगिता के सेमीफाइनल में क्वालीफाइंग दौर में गए। पहले क्वालिफिकेशन राउंड के विजेता निज़नी नोवगोरोड से यूएनएन के मैक्मथ, व्लादिस्लाव एपिफ़ानोव के छात्र थे। प्रतिभागियों ने 3391 फैसले भेजे, जिनमें से 1066 को सिस्टम ने सच माना। 634 लोगों या कुल प्रतिभागियों में से 63% ने कम से कम एक समस्या हल की।

रूसी कोड कप एक व्यक्तिगत खेल प्रोग्रामिंग प्रतियोगिता है जो प्रतिवर्ष Mail.Ru Group द्वारा आयोजित की जाती है। यह पारंपरिक रूप से तीन चरणों में होता है: गर्मियों की शुरुआत में तीन क्वालीफिकेशन राउंड होते हैं, फिर क्वालीफाइंग राउंड में सर्वश्रेष्ठ भाग लेते हैं, फाइनल में क्वालीफाइंग राउंड प्रतियोगिता के पहले पचास विजेता। व्यक्तिगत उपस्थिति के लिए केवल उनमें से अंतिम की आवश्यकता होगी, जबकि शेष ऑनलाइन आयोजित की जाती है। सभी फाइनलिस्ट को बहुमूल्य उपहार से सम्मानित किया जाएगा, और प्रथम स्थान वाले प्रतिभागी के लिए पुरस्कार $ 10,000 होगा। दूसरे और तीसरे स्थान के लिए 5,000 और 3,000 डॉलर का भरोसा करते हैं।

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


कुल मिलाकर, दौरे के लिए पांच कार्य प्रस्तावित किए गए थे: "बॉक्स", "पेरेस्त्रोइका", "वार", "लेबल", "जावनी हथियार"।

"समानताएं"

"पैरेल्लेपिप्ड" का कार्य बारह मैचों की ज्ञात लंबाई से जांचना था कि क्या समानांतर चतुर्भुज का फ्रेम उनसे चिपकाया जा सकता है। यह कार्य सबसे सरल था और सभी प्रतिभागियों ने इसे हल करना शुरू कर दिया।

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

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

#include <iostream> #include <cstdio> using namespace std; int main() { int a[12]; while (true) { bool ex = true; for (int i = 0; i < 12; i++) cin >> a[i]; for (int i = 0; i < 12; i++) if (a[i] != 0) ex = false; if (ex) break; bool ans = true; for (int i = 0; i < 12; i++) { int k = 0; for (int j = 0; j < 12; j++) k += (a[i] == a[j]); if (k % 4 != 0) ans = false; } cout << ((ans) ? "yes" : "no") << endl; } } 

पैरेल्लेपिपड कार्य को पारित करने के लिए 1479 प्रयास हुए, जिनमें से 639 सफल (43%) थे। यह कार्य सबसे अधिक सुलभ है - प्रयासों की संख्या अन्य कार्यों की तुलना में दोगुने से अधिक है, एक उच्च सफलता दर।
रशियनकोडकोड.उ: समस्या का बयान
रशियनकोडकोड.रू: पार्सिंग कार्य

"पेरेस्त्रोइका"

दूसरा कार्य अधिक कठिन था।

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

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

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

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

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



इसलिए, इस सरलतम मामले में, उत्तर शून्य विकल्प है।

यदि हम दो समूहों के साथ काम कर रहे हैं, अर्थात् दो जुड़े घटक हैं, तो विकल्पों की संख्या की गणना निम्नानुसार की जाती है।

पहले आपको यह पता लगाने की जरूरत है कि कौन सी पसलियां "पुल" हैं - क्योंकि जब आप इन पसलियों को हटाते हैं, तो हम ऊपर दिए गए पहले विकल्प के लिए सब कुछ लाते हैं। हम उन्हें वापस नहीं जोड़ सकते, क्योंकि समस्या की स्थितियों के अनुसार, आप उन्हें केवल वहीं जोड़ सकते हैं जहाँ कोई किनारा नहीं था। चूंकि अंत में हमें एक जुड़ा हुआ ग्राफ प्राप्त करना होता है, इसलिए जोड़े गए किनारे को अलग-अलग कनेक्ट किए गए घटकों से कोने को जोड़ना चाहिए - कनेक्ट किए गए ग्राफ़ को डिस्कनेक्ट किए गए ग्राफ़ से बाहर करने के लिए। N और M शीर्षकों के दो समूह NxM विधियों द्वारा परस्पर जुड़े हो सकते हैं। नतीजतन, हमें प्राप्त होने वाले सुधारों की संख्या NxMxC है, जहां C = किनारों की संख्या, उन पुलों को छोड़कर।



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

किनारों की कुल संख्या को कोने की संख्या से गणना की जा सकती है: n * (n-1)) / 2 (जहां n = कोने की संख्या)। जो किनारों को जोड़ा जा सकता है, उनकी गणना उपलब्ध किनारों की कुल संख्या से घटाकर की जाती है। तो हम पहला शब्द प्राप्त करते हैं - किनारों की संख्या जो पुल नहीं हैं, उन किनारों की संख्या से गुणा की जाती हैं जिन्हें जोड़ा जा सकता है।



"पुल" को हटाते समय, हमें एक किनारे के साथ दो परिणामी जुड़े घटकों को जोड़ना होगा, कोने के decoupled समूह। ऐसा करने के तरीकों की संख्या पुल के दाईं ओर पुल के दाईं ओर स्थित पुल के दाईं ओर के उत्पाद के बराबर है, एक से घटाकर, क्योंकि हम समस्या की स्थिति से पुल को वापस नहीं डाल सकते हैं।

परिणामस्वरूप, इस समस्या को हल करने के लिए, ग्राफ सिद्धांत से निम्नलिखित एल्गोरिदम का ज्ञान आवश्यक है:

• जुड़े घटकों की संख्या की गिनती;
• पुलों का पता लगाना;
• पुल के प्रत्येक तरफ चोटियों की संख्या की गिनती।

जुड़े घटकों की संख्या का पता लगाना

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

एल्गोरिथम विवरण और उदाहरण: e-maxx.ru/algo/connected_compords

पुलों का पता लगाना

पुलों को खोजने के लिए एल्गोरिथ्म "चक्र" की खोज पर आधारित है - चोटियों के बीच वैकल्पिक मार्ग। अगर ऐसा कोई रास्ता नहीं मिलता है, तो रिब एक पुल है।

एल्गोरिथम विवरण और उदाहरण: e-maxx.ru/algo/bridge_searching

इस एल्गोरिदम को पुल के विभिन्न किनारों पर कोने की संख्या का पता लगाने के लिए संशोधित किया जा सकता है।

पेरेस्त्रोइका कार्य को पारित करने के लिए 621 प्रयास थे, जिनमें से 137 सफल (22%) थे।

रशियनकोडकोड.उ: समस्या का बयान
रशियनकोडकोड.रू: पार्सिंग कार्य
सी ++ समाधान (पास्टबिन)

"युद्ध"

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

• यूनिट में सैनिकों की संख्या, यदि रैंक में वे गैर-वृद्धि या उनकी वृद्धि में कमी न करने के क्रम में हैं;
• 0 अन्यथा।

जनरल ने यह भी तय किया कि सेना की शक्ति सभी इकाइयों की क्षमताओं के उत्पाद के बराबर है।
जनरल सेना के एक डिवीजन को इकाइयों में खोजना चाहता है ताकि पूरी सेना की शक्ति अधिकतम हो। इस समस्या को हल करने में उसकी मदद करें। ”

वास्तव में, कार्य एक संख्या को मोनोटोन सेगमेंट में विभाजित करने के लिए उबलता है, ताकि उनकी लंबाई का उत्पाद अधिकतम हो। यह स्पष्ट है कि यदि एक बड़े खंड को कई उप-खंडों में विभाजित किया जा सकता है, तो लंबाई का उत्पाद बड़े खंड की लंबाई से अधिक होगा। यह तब किया जा सकता है यदि खंड की लंबाई तीन से अधिक है: यदि n then 4, तो 2 (n - 2) = 2n - 2। N।

अब आप गतिशील प्रोग्रामिंग का उपयोग करके समस्या को हल कर सकते हैं - प्रत्येक उपसर्ग के लिए, आपको इष्टतम उत्तर की गणना करने की आवश्यकता है और इस उपसर्ग पर अंतिम खंड कितने समय तक है।

ऐसा करने के लिए, यह छांटना आवश्यक है कि खंड (1, 2 या 3) को कितना समय लिया जाना चाहिए, यह जांचें कि उस पर अनुक्रम नहीं बढ़ता या घटता है, और उपयुक्त विकल्पों में से अधिकतम का चयन करें।

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

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

"युद्ध" कार्य को पारित करने के प्रयास 879 थे, जिनमें से 184 सफल (21%) थे।

रशियनकोडकोड.उ: समस्या का बयान
रशियनकोडकोड.रू: पार्सिंग कार्य
सी ++ समाधान (पास्टबिन)
जावा सॉल्यूशन (बिगिंट) (पास्टबिन)

"जावानीस हथियार"

“प्राचीन काल से, हर जावा में तीन हथियारों का एक सेट होता है: ब्रेड पर मक्खन फैलाने के लिए एक लेजर तलवार, एक लेजर कृपाण और एक लेजर चाकू (अचानक जावा भूख लगी है)।

लेकिन चूंकि यह एक जावनी हथियार है, एक साधारण नहीं, सेट में शामिल वस्तुओं की लंबाई पर निम्नलिखित प्रतिबंध लगाए गए हैं:

चाकू की लंबाई d1 है, कृपाण की लंबाई d2 है, तलवार की लंबाई d3 है अभाज्य संख्याएँ होनी चाहिए;

• d1 ≤ d2 ≤ d3;
• (d1 + d2) ² - 1 को d3 से विभाजित किया जाता है;
• (d2 + d3) ² - 1 को d1 से विभाजित किया जाता है;
• (d3 + d1) ² - 1 को d2 से विभाजित किया जाता है।

डार्ट जेनेरिक इंडस्ट्रीज अपने संख्या के हिसाब से लेक्सिकोग्राफिक ऑर्डर में जवानी के हथियारों के किसी भी सेट को बेचती है। अर्थात्, हम गैर-घटते हुए d1 में सभी जावानीस सेटों को क्रमबद्ध करते हैं, गैर घटते हुए d2 में बराबर d1 के साथ, और d3 को बढ़ाने में बराबर d1 और d2 के लिए, हम उन्हें इस क्रम में 1 से अनंत तक क्रमबद्ध करते हैं। फिर दिए गए k के लिए, आप इस क्रम में k-th सेट खरीद सकते हैं।

Java Anykey k-th सेट खरीदना चाहता है। उसे अपने हथियार का आकार बताओ। ”

हम दिखाते हैं कि हथियार की लंबाई पर लगाए गए शर्तों में से, यह d1 = d2 है । कोई तीन संख्या बराबर होने दें, फिर d1 <d2 <d3 । स्थिति (d1 + d2) ² - 1 = (d1 + d2 + 1) (d1 + d2 - 1) d3 द्वारा विभाज्य है, क्योंकि d3 अभाज्य है, कारकों में से एक d3 द्वारा विभाज्य है।

उदाहरण के लिए, (d1 + d2 + 1) को d3 से विभाजित किया जाए । यह d1 <d2 <d3 कि d1 + d2 + 1 = d3 की स्थिति से अनुसरण करता है। लेकिन तब (d2 + d3) ² -1 = (2d2 + d1 + 1) ² -1 = 4d2 ² + 4d2 + 4d1d2 + d1 ² + 2d1। शर्त से, यह संख्या d1 से विभाजित है, जिसका अर्थ है 4d2 ² + 4d2 d1 द्वारा विभाजित है। तो या तो d1 = 2, या d1 = d2, या d1 = d2 + 1।

तीसरी स्थिति के समान तर्क को लागू करते हुए, हम यह प्राप्त करते हैं कि या तो d2 = 2, या d1 = d2, या d2 = d1 + 1। इन शर्तों के सभी जोड़ों में से, केवल d1 = d2 और d1 = 2, d2 = 3 संगत हैं । लेकिन बाद के मामले में, उपयुक्त डी 3 चुनना संभव नहीं है। इसलिए डी 1 = डी 2।

इसी तरह, हम मामले को मानते हैं (d1 + d2 - 1) d3 द्वारा विभाजित।

पी के रूप में डी 1 = डी 2 को निरूपित करें। इसलिए, (p + p) ² -1 = (2p - 1) (2p + 1) को d3 से विभाजित किया जाता है, और चूंकि यह सबसे सरल और सबसे बड़ा है, यह केवल (2p-1) या (2p + 1) के बराबर हो सकता है । इसलिए, सभी त्रिभुजों के पास फॉर्म (पी, पी, 2 पी -1) या (पी, पी, 2 पी + 1) होना चाहिए। चूंकि, समस्या की स्थितियों के अनुसार, पहली अभाज्य संख्या पहले 60,000 हज़ार के बीच है, यह 10 ⁷ से अधिक नहीं है। इसलिए, ऐसे प्रतिबंधों के तहत, आप एराटोस्थनीज की छलनी लगा सकते हैं - प्राइम नंबर खोजने के लिए एक एल्गोरिथ्म।

एराटोस्थनीज की छलनी

एराटोस्थनीज के सिद्धांत खोज एल्गोरिथ्म की भविष्यवाणी इस प्रकार है। उदाहरण के लिए, आपको 1 से लेकर कुछ N <= 10 ⁷ तक की रेंज में primes खोजने की आवश्यकता है। हम एन तत्वों की एक सरणी बनाते हैं और इसे "सच" मान के साथ भरते हैं। फिर हम क्रमिक रूप से इसके माध्यम से एन की जड़ तक जाते हैं, और जहां भी हम सही पाते हैं, एन को इसकी सभी कई संख्याओं को पार करते हैं। पहले चरण में, सभी सम संख्याओं को पार किया जाता है (क्योंकि पहला अभाज्य 2 है), दूसरे पर, तीन के सभी गुणक आदि। घ।

एल्गोरिथ्म का उदाहरण और उदाहरण: http://habrahabr.ru/post/91112/

जावानीस हथियारों के काम को आत्मसमर्पण करने के 303 प्रयास हुए, जिनमें से 126 सफल (42%) थे।

रशियनकोडकोड.उ: समस्या का बयान
रशियनकोडकोड.रू: पार्सिंग कार्य
सी ++ समाधान (पास्टबिन)

"लेबल"

शायद यह कार्य सभी के लिए सबसे कठिन था, हालाँकि उसकी व्याख्या शायद सबसे सरल में से एक है।

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

समस्या यह थी कि यह सभ्यता संक्रमण के संकेत का उपयोग नहीं करती थी। जैसे ही लाइन समाप्त हुई, बस अगली पंक्ति से पढ़ना जारी रहा। जब पुस्तकों को डिक्रिप्ट करते हैं, तो इससे कोई असुविधा नहीं होती थी, लेकिन लेबल में पुस्तक से महत्वपूर्ण अंतर होता है - लेबल को बोतल पर चिपकाया जाता था ताकि एक पूरा सिलेंडर प्राप्त हो, जिस पर एक सर्कल में पाठ लिखा गया था। पाठ को पढ़ते समय, आपको ग्लूइंग के स्थान से पहली पंक्ति को पढ़ना शुरू करना चाहिए, ग्लूइंग के स्थान पर पहुंचने के बाद, दूसरी पंक्ति पर जाएं, फिर तीसरी और इतने पर। लेकिन वैज्ञानिक अभी तक उस जगह का निर्धारण नहीं कर पाए हैं जहां लेबल चिपकाया गया था! इसलिए समय के लिए, पाठ के बजाय, अक्षरों और वर्णों से मिलकर, उसी लंबाई की लाइनों का एक सेट होता है "।", जिनका उपयोग इस सभ्यता द्वारा रिक्त स्थान के बजाय किया जाता था।
सौभाग्य से, लेबल के अलावा, एक शब्दकोश है जो उन सभी संभावित शब्दों को सूचीबद्ध करता है जो इस सभ्यता द्वारा उपयोग किए गए थे। अब, इन आंकड़ों के आधार पर, आपको यह निर्धारित करने की आवश्यकता है कि gluing स्थान के लिए कितने विकल्प मौजूद हैं। अधिक औपचारिक रूप से, आपको यह निर्धारित करने की आवश्यकता है कि कितने गैर-नकारात्मक मूल्य हैं <k इस तरह मौजूद हैं कि आपके द्वारा दिए गए सभी रेखाओं का संघन चक्रवाती रूप से बाईं ओर टी वर्णों में स्थानांतरित हो गया है, शब्दकोश से शब्दों का एक संग्रह है, जिसे एक या अधिक वर्णों द्वारा अलग किया गया है ""। इसके अतिरिक्त, आपको इन सभी t मानों को प्रिंट करने की भी आवश्यकता है।

इस समस्या को हल करने के लिए, किसी को स्ट्रिंग्स और पात्रों की अवधारणा से मूल्यों और संख्याओं के सरणियों में जाना चाहिए - यह समाधान को बहुत सरल करेगा और इसे समय और मेमोरी सीमा में फिट होने की अनुमति देगा।

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

स्ट्रिंग से बहुपद हैश की गणना i-th वर्ण के कोड के उत्पादों के योग के रूप में n i से की जाती है। इस तरह के हैश का उपयोग अक्सर स्ट्रिंग में सबस्ट्रिंग की खोज को गति देने के लिए किया जाता है: यदि दो तार तीसरे होते हैं, तो उनका हैश एक साधारण अंकगणितीय निर्भरता H3 = H1 + k * H2 में होता है, जहाँ k = हैश बेस को पहले स्ट्रिंग की लंबाई तक बढ़ाया जाता है।

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

प्रारंभिक स्थिति के लिए, आप आसानी से सभी शब्दों के हैश की गणना कर सकते हैं, लाइन से लाइन तक शब्द के शब्द को ध्यान में रखते हुए।

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

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

बहुपद हैश

एल्गोरिथ्म का विवरण: http://habrahabr.ru/post/142589/

लेबल कार्य को पारित करने के लिए 109 प्रयास थे, जिनमें से केवल 6 सफल (5%) थे। यह कार्य प्रतिभागियों के लिए सबसे कठिन निकला।

रशियनकोडकोड.उ: समस्या का बयान
रशियनकोडकोड.रू: पार्सिंग कार्य
जावा समाधान (पास्टबिन)

---

• दूसरी योग्यता से डिबेटिंग
  तीसरी योग्यता से कार्यों का विश्लेषण
  
  
  अलाइव रऊफ
  अनुसंधान और शिक्षा निदेशक
  प्रोजेक्ट मैनेजर रूसी कोड कप
  Mail.Ru Group