पिछले शनिवार, 16 जून को, रूसी कोड कप 2012 का क्वालीफाइंग राउंड समाप्त हो गया। क्वालीफाइंग राउंड के कार्य योग्यता की तुलना में अधिक जटिल हैं - ठीक है, यही कारण है कि यह सेमीफाइनल है। मैंने पहले ही बात की थी कि प्रतिभागियों को पिछली ऑनलाइन यात्राओं पर क्या ऑफर किया गया था, समाधान के विकल्पों ( Q1 , Q2 , Q3 ) का विस्तार से विश्लेषण किया।

क्वालीफाइंग दौर में 600 लोगों को आमंत्रित किया गया था। 434 लोग कम से कम एक समस्या को हल करने में सक्षम थे। सभी कार्य केवल दो द्वारा हल किए गए थे। 50 सर्वश्रेष्ठ फाइनल में गए। दौरे के केवल 3 घंटों में, 3190 समाधान परीक्षण प्रणाली को भेजे गए थे।

तो, चलिए कार्यों को स्वयं करते हैं। मैंने उन्हें समझाने की कोशिश की ताकि खेल प्रोग्रामिंग में (और वास्तव में प्रोग्रामिंग में वास्तव में) पहला कदम उठाने वालों के लिए भी निर्णय स्पष्ट थे।

Eprestanovka

समस्या का सार यह निर्धारित करना था कि क्या एक मनमाना क्रम में दो प्रकार के क्रमपरिवर्तन को लागू करने से, मूल्यों की सूची में एक तत्व को एक निर्दिष्ट स्थान से एक निर्दिष्ट स्थान पर स्थानांतरित करना संभव है। समस्या की स्थिति से, तथाकथित क्रमपरिवर्तन को लागू करना संभव था, जो पहले दो तत्वों को स्वैप करता है, और एक नियम-मान (a1, a2, ..., aN) द्वारा परिभाषित एक जटिल क्रमपरिवर्तन, जहां प्रत्येक मान उस स्थिति की क्रम संख्या निर्धारित करता है जहां आप स्थानांतरित कर सकते हैं। इस स्थिति से संख्या। उदाहरण के लिए, क्रमपरिवर्तन नियम (1,4,3,2) में अंतिम दो का अर्थ है कि अंतिम स्थिति से आप दूसरे को फिर से व्यवस्थित कर सकते हैं, और अंतिम से। दरअसल, अंत में, इस सूची (एन मानों) के इनपुट डेटा के रूप में "हां / नहीं" और फॉर्म (स्थिति 1, स्थिति 2) में अनुरोध का उत्तर देना आवश्यक है - "क्या तत्व 1 से स्थिति 2 तक ले जाना संभव है"।

यह कार्य प्रतियोगिता में सबसे सरल था, 411 लोगों ने इसके साथ मुकाबला किया, पहले टेस्ट में उत्तीर्ण होने का प्रस्ताव दिमित्री झुकोव ने दौर की शुरुआत से 3 मिनट 31 सेकंड पर किया।

जाहिर है, सभी क्रमपरिवर्तन अंततः लूप के एक सेट पर आते हैं। चक्र तीन के उपरोक्त उदाहरण में - 4-> 2-> 4-> 2 ... 1-> 1-> 1 ... 3-> 3-> 3 ... यानी, अगर हमारे पास केवल ऑपरेशन "क्रमपरिवर्तन पी लागू करें", तब दो तत्वों ai और द्वि के लिए उत्तर "हां" होगा यदि और केवल अगर ये तत्व अनुमति चक्र में एक चक्र पर झूठ होंगे।

"क्रमपरिवर्तन" z लागू करते समय क्या होता है, इस बारे में सोचें। अगर शुरू में पहले और दूसरे तत्व अलग-अलग चक्रों में आते हैं, तो "क्रमचय" का उपयोग हमें इन दो चक्रों में से एक से दूसरे में कुछ तत्व को पुनर्व्यवस्थित करने का अवसर देता है।

अब हम एक सामान्य समाधान तैयार कर सकते हैं।

हम पूरे क्रमचय p को चक्रों में विभाजित करते हैं।
प्रत्येक ai और bi के लिए, उत्तर "हां" है यदि ai और bi एक ही चक्र में हैं, या यदि पहला तत्व उनमें से एक के चक्र में है और दूसरा दूसरे के चक्र में है।

चक्रों में विभाजन निम्नानुसार है:

//    col,   −1. vector<int> col(n, −1); //    ,    ,       for (int i = 0; i < n; i++) { if (col[i] != −1) continue; //     int x = i; do { col[x] = i; //    x = a[x]; } while (col[x] == −1); }

पहले दो चक्रों को एक में मिलाएं:

 for (int i = 0; i < n; i++) if (col[i] == 0) col[i] = 1;

नतीजतन, हमें कर्नल की एक सरणी मिली, जिनमें से i-th तत्व एक चक्र को दर्शाता है जिसमें i-th स्थिति शामिल है।

 for (int i = 0; i < m; i++) { int a, b; cin >> a >> b; //  ,          . cout << ((col[a — 1] == col[b — 1])? «Yes» : «No») << «\n»; }

राज्याभिषेक

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

समस्या का एक विस्तृत विवरण रूसी कोड कप की आधिकारिक वेबसाइट पर गोल पृष्ठ पर पाया जा सकता है।

यह कार्य "अंत से दूसरा सबसे कठिन" निकला - 313 लोगों ने इसे हल किया। पहला सही निर्णय दिमित्री झुकोव द्वारा 12:50 पर भेजा गया था।

समस्या में, हमारे पास एक भारित अप्रत्यक्ष पेड़ है। यही है, एक ग्राफ जिसमें छोरों और कई किनारों नहीं होते हैं, जिनके किनारों ("सड़कों") को "वेट" के साथ लिखा जाता है - सड़कों का थ्रूपुट।

इसमें दो चोटियों पर प्रकाश डाला गया है - "राजधानियाँ" - s और t। एक किनारे जोड़ना आवश्यक है जो एस या टी को प्रभावित नहीं करता है, जैसे कि एस से टी तक का प्रवाह अधिकतम है।

आइए हम एक किनारे को वर्टेक्स ए से वर्टेक्स बी तक जोड़ते हैं। आइए हम साबित करते हैं कि s और t के बीच में अधिकतम दो सरल पथ होंगे (यदि इसमें किनारों को न दोहराया जाए तो एक पथ को सरल कहा जाता है)। हम इसके विपरीत साबित होते हैं। मान लीजिए हम तीन तरीके खोजने में कामयाब रहे।

दो मामलों पर विचार करें:

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

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

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

नतीजतन, हमें पता चलता है कि हमारे उत्तर में दो रास्ते होते हैं, जिनमें से एक किनारे को जोड़ने से पहले अस्तित्व में था, और दूसरा - एस से एक किनारे, एक किनारे पर एबी और टी में एक किनारे।

हमें इसका समाधान मिलता है:

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

सामाजिक भय

समस्या की स्थिति यह है कि इसे न्यूनतम कटौती के साथ यहां लाया जाए।

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

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

यात्रियों ने टिकट कैसे खरीदे और सौंपे, इसके अनुसार डिब्बे में यात्रियों के अंतिम वितरण को प्रदर्शित करना आवश्यक है। यह गारंटी दी जाती है कि हर बार जब कोई यात्री टिकट खरीदता है, तो कार में कम से कम एक सीट होती है। ”

ऐसा लगता है कि विचाराधीन ट्रेन वास्तव में बहुत बड़ी है, क्योंकि टिकट की बिक्री और टिकट रिटर्न की संख्या 200,000 तक है, तो कूपों की संख्या 50,000 तक है।

कुल मिलाकर, 167 लोगों ने इस समस्या को हल किया, उनमें से पहला पावेल कुनियाव्स्की (23:19) था।

इस समस्या का एक समाधान इस प्रकार है। हम निम्नलिखित डेटा संरचनाएँ तैयार करेंगे:

 // ,     . Pas[i] = , -1  «  ». vector<int> pas(200000+1, -1); //   –    . Cars[i]     vector< set<int> > cars(50000 + 1);

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

 set<int> zero; set<int> one;

प्रारंभ में, सभी डिब्बे खाली हैं, इसलिए हमने उन्हें भरने के लिए उम्मीदवारों की सूची में डाल दिया - शून्य।

 for (int i = 1; i <= n; i++) zero.insert(i);

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

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

 int car = *zero.upper_bound(0); //    pas[++id] = car; //      cars[car].insert(id); //       zero.erase(car); //        one.insert(car); // …     if (zero.empty()) //   ,      … { zero = one; //        zero.erase(-n); zero.erase(2 * n); one.clear(); //     one.insert(-n); one.insert(2 * n); }

टिकट वितरण ऑपरेशन ("-")। पेस ऐरे का उपयोग करके, हमें पता चलता है कि यात्री किस डिब्बे में बैठा था। हम यात्री को संबंधित डिब्बे से हटा देते हैं।

 int car = pas[x]; cars[car].erase(x); pas[x] = −1;

पता करें कि कितने कार कूप के थे। यहाँ निम्नलिखित विकल्प दिए गए हैं:

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

 set<int>::iterator ll = (one.upper_bound(car)); ll--; //  ,    set<int>::iterator rr = (one.upper_bound(car)); //  ,    if (abs(*ll - car) > abs(*rr - car)) //        ll = rr; int l = *ll; one.erase(l); zero.insert(l); //   one  zero int p = *cars[l].upper_bound(0); cars[l].erase(p); cars[car].insert(p); //      pas[p] = car;

कार्य का उत्तर प्रदर्शित करने के लिए, हम कारों की सरणी का उपयोग करेंगे। I-th डिब्बे में यात्रियों के बारे में जानकारी प्रदर्शित करने के लिए, यह सेट कारों के आकार को प्रदर्शित करने के लिए पर्याप्त है [i],

 cout << cars[i].size() << ((cars[i].size() == 0) ? "\n" : " ");

और फिर कई कारों से संबंधित सभी यात्री [i]।

 set<int>::iterator en = cars[i].end(); en--; for (set<int>::iterator it = cars[i].begin(); it != cars[i].end(); it++) cout << *it << ((it == en) ? "\n" : " ");

सिक्के

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

एक उदाहरण चित्रण के लिए दिया गया है। यदि प्रचलन में 1, 2 या 3 डॉलर के मूल्यवर्ग में सिक्के हैं, और रिसविंड ने 9 के बजाय 10 डॉलर का भुगतान किया है, तो वह 1 के सिक्कों के लिए 2 के सिक्कों को स्वीकार कर सकता है, और भुगतान किया जा सकता है, उदाहरण के लिए, 2 के चार सिक्के और 2 के एक सिक्के। जो उसने अंकित मूल्य "1" के लिए लिया।

वह 2 के संप्रदायों में सिक्कों के लिए 3 के मूल्यवर्ग में सिक्कों को स्वीकार कर सकता था और 1 के संप्रदायों में 3 में से एक में सात सिक्कों का भुगतान कर सकता था, जिसे उसने 2 के संप्रदायों में एक सिक्के के लिए लिया था।

फेस वैल्यू 1 में वास्तव में कितना भुगतान किया गया है	नाममात्र मूल्य 2 में वास्तव में कितना भुगतान किया जाता है	वास्तव में बराबर मूल्य 3 में कितना भुगतान किया जाता है	कुल भुगतान
-	वास्तव में 4 सिक्के (8 डॉलर, 4 × 2) 1 का सिक्का (2 डॉलर, 2 × 1) रिविंड के दृश्य में - 1 डॉलर (1 × 1)	-	वास्तव में 5 सिक्के (10 डॉलर, 4 × 2 + 2 × 1) रिविंड के दृश्य में - 9 डॉलर (4 × 2 + 1 × 1)
वास्तव में 7 सिक्के (7 डॉलर, 7 × 1)	-	वास्तव में 1 का सिक्का (3 डॉलर, 3 × 1) रिविंड के दृश्य में - 2 डॉलर (2 × 1)	वास्तव में 8 सिक्के (10 डॉलर, 4 × 2 + 1 × 1) रिविंड के दृश्य में - 9 डॉलर (4 × 2 + 2 × 1)

मान लीजिए कि Rincewind ने s के लिए सिक्का t लिया। अंतिम उदाहरण में, 2 के लिए सिक्का 3 (टी)। इसका मतलब यह है कि उसने सिक्के की एस (उदाहरण में - $ 7) का उपयोग किए बिना, वी की एक निश्चित राशि एकत्र की (उदाहरण के लिए - $ 7), जिसके बाद उसने एक और के सिक्कों की संख्या t डाल दी, यह सोचते हुए कि ये सिक्के संख्या s हैं (उदाहरण में - एक सिक्का) 3, यह सोचकर कि यह 2 है)।

दूसरे शब्दों में, विकल्पों की पूरी विविधता मामलों के दो समूहों में फिट होती है:

पूर्णांक V and 0 और k> 0 हैं जैसे कि S = V + k · as और T = V + k · पर, जहां T वास्तव में भुगतान की गई राशि है और R रिवाइंड प्रतिनिधित्व में राशि है।
V का योग सिक्के के उपयोग के बिना टाइप किया जा सकता है।

पहली स्थिति को O (1) में सत्यापित किया जा सकता है। ध्यान दें

k = (S - T) / (as - at);
वी = एस - के

यह सत्यापित करना शेष है कि प्राप्त संख्या पूर्णांक, V to 0, और k> 0 हैं।

दूसरी स्थिति की जांच करने के लिए, हम गतिशील प्रोग्रामिंग विधि का उपयोग करते हैं। चलो D [i] [j] - क्या यह संभव है कि पहले i सिक्कों का उपयोग करके j योग प्राप्त किया जाए? आधार: डी [०] [०] = सच। संक्रमण: D [i] [j] = D [i - 1] [j] या D [i] [j - ai]। कार्यान्वयन के लिए, S की एक सरणी पर्याप्त है। इस एल्गोरिथ्म का रनिंग टाइम O (S · n) है। गतिशील प्रोग्रामिंग का उपयोग करते हुए दृष्टिकोण के विस्तृत विवरण के लिए, अंतिम दौर से कार्यों का विश्लेषण , साथ ही उदाहरणों और उदाहरणों के साथ अच्छी सामग्री देखें ।

वर्णित विधि का उपयोग करते हुए, हम 1 से एस तक प्रत्येक राशि V की गणना करते हैं कि क्या रेनविंड सिक्का एस का उपयोग किए बिना इस राशि को एकत्र कर सकता है। उसके बाद, हम उस सिक्के को निकालेंगे जो Rincewind ने s के लिए लिया था। अब दोनों स्थितियों का सत्यापन O (1) के लिए किया जाता है। समाधान का असममित व्यवहार ओ (एस · एन 2) है।

"सिक्के" का काम सबसे पहले पीटर मैट्रिकव ने 17:06 पर हल किया था। कुल मिलाकर, हमें 234 सही फैसले मिले, जो जटिलता के मामले में इस कार्य को अंत से तीसरे स्थान पर रखता है।

लाइन पार्सिंग

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

हम पहले उस महत्वपूर्ण विचार पर विचार करते हैं जो हमें समस्या के समाधान की ओर ले जाता है। आज्ञा देना एक स्ट्रिंग टी - कम से कम लंबाई के आवश्यक प्रतिधारण, और शब्दकोश डब्ल्यू ₁ , डब्ल्यू ₂ , ..., डब्ल्यू के से शब्दों में इसका कुछ विभाजन। इस लाइन की जांच करते समय हम जिस लालची पार्सर को तोड़ने की कोशिश कर रहे हैं, उससे स्ट्रिंग स्ट्रिंग को "काटने" के लिए सबसे पहले हो।

आइए हम निम्नलिखित कथन को सिद्ध करते हैं: यदि स्ट्रिंग लंबाई w ₁ , w ₂ , ..., w _{k-1 की} लंबाई से अधिक नहीं है, तो स्ट्रिंग t की तुलना में एक प्रतिरूप छोटा होता है।

शुरुआत के लिए, स्ट्रिंग की लंबाई इस राशि के बराबर होनी चाहिए। तब यह स्पष्ट है कि लालची पार्सर स्ट्रिंग टी पर सही ढंग से काम करेगा, क्योंकि स्ट्रिंग डब्ल्यू को पहले इसे "काट" दिया जाएगा, और फिर स्ट्रिंग डब्ल्यू _के , क्योंकि यह शब्दकोश में निहित सबसे लंबा स्ट्रिंग उपसर्ग होगा।

इस स्थिति में, स्ट्रिंग की लंबाई w ₁ , w ₂ , ..., w _{k-1 की} लंबाई से कम है। फिर एक नंबर j मौजूद होता है जैसे कि w _{j को} उपसर्ग w _j1 और प्रत्यय w _j2 में बांटा गया है, और w _j1 स्ट्रिंग w (संभवतः शून्य लंबाई) का प्रत्यय है। स्ट्रिंग w _j2 पर विचार करें। यदि उसके लिए शब्दकोष से शब्दों में एक सही विभाजन है, तो यह एक जाल के रूप में छोड़ने के लिए पर्याप्त है जैसे कि डब्ल्यू _जे ₂ , डब्ल्यू _{जे + 1} , डब्ल्यू _{जे + 2} , ..., डब्ल्यू _के , जो एक छोटा काउंटरएक्सप्लिमेंट होगा। यदि, स्ट्रिंग w _{j2 के लिए,} किसी शब्दकोश से शब्द विभाजन सिद्धांत रूप में मौजूद नहीं है, तो एक छोटा सा प्रतिधारण स्ट्रिंग्स डब्ल्यू ₁ , डब्ल्यू ₂ , ..., डब्ल्यू _जे का संयोजन है।

तो, अब हम कल्पना कर सकते हैं कि वांछित पलटाव कैसा दिखता है।

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

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

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

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

संबंधित लंबाई के अध्ययन किए गए उपसर्ग का प्रत्यय शब्दकोश से रेखा के बराबर है
संबंधित लंबाई के अध्ययन उपसर्ग के उपसर्ग को शब्दकोष से शब्दों में विभाजित किया जाता है

, O(sumL × n), sumL — , n — , , . , .

« » ( ) « », , – 115:47.

, , . , / , . , , , . , , , — Impossible.

, , x , x — . : (0, 0) (x, y) y, ( ), ( ) (). .

, , , . , , .

, . , , «» , . , . . , - . . , .

, . , . , . , , , , - . , . , , . x, . , , .

, , . O(n2 log n) , O(n) O(n) O(n) . O(n log n) , O(n) .

, .

और

– 23 , – 100:18. , , – , 2 . , .

50 . 10 Swissotel, . , , , .

अलाइव रऊफ

Mail.Ru Group

रूसी कोड कप 2012: क्वालीफाइंग राउंड (सेमीफाइनल) से कार्यों का विस्तृत विश्लेषण

Eprestanovka

राज्याभिषेक

सामाजिक भय

सिक्के

लाइन पार्सिंग

More articles: