रूसी कोड कप 2013: हम फाइनल के कार्यों का विश्लेषण करते हैं

23 सितंबर, 2013 को रूसी कोड कप 2013 प्रोग्रामिंग चैम्पियनशिप का फाइनल हुआ।

पहला स्थान पीटर मित्रीचेव ने लिया (वैसे, आरसीसी 2011 के चैंपियन)। दूसरा पुरस्कार Gennady Korotkevich, तीसरा - दिमित्री Dzhulgakov द्वारा लिया गया था।

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

टास्क A. धैर्य

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

लोग हर दिन इस खेल को खेलते हैं। हर दिन, शिक्षक का प्रारंभिक असंतोष बढ़ता है: पहले दिन यह 1 था, दूसरे दिन - 2, और इसी तरह। I-th के दिन, छात्रों के साथ शिक्षक का प्रारंभिक असंतोष i है। कुल मिलाकर, साल में बिल्कुल n स्कूल के दिन होते हैं, यानी स्कूल के आखिरी दिन, शिक्षक की नाराजगी n होती है और छात्रों का कोई भी प्रैंक उसे तुरंत प्रभावित करता है।

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

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

इनपुट प्रारूप
पहली पंक्ति में एक पूर्णांक T (1 ≤ T) 10 ⁵ ) - परीक्षणों की संख्या है। निम्नलिखित T लाइनों में से प्रत्येक में अगले परीक्षण का वर्णन है: 2 पूर्णांक n और k (1, n, k ¹⁸ 10 ¹⁸ )।

आउटपुट स्वरूप
प्रत्येक परीक्षण के लिए एक ही नंबर प्रिंट करें: एक - जिस दिन वासा अपने माता-पिता के लिए kth समय के लिए गया था, या a1 यदि ऐसी स्थिति नहीं हो सकती है। प्रत्येक संख्या को एक अलग रेखा पर प्रिंट करें।

पार्स:
खेल में दो प्रतिभागियों के लिए वर्णित किया गया था। खेल की स्थिति को एक एकल संख्या x द्वारा वर्णित किया गया था, और खिलाड़ी बदले में दो चालों में से एक बना सकते थे: x को x + 1 या 2x से बदलें। वह खिलाड़ी जिसने पहली बार n खो से अधिक संख्या लिखी थी। संख्या x बढ़ाकर k को खोजना आवश्यक था, जैसे कि शुरुआती संख्या x होने पर पहले खिलाड़ी की जीतने की रणनीति थी।

चूंकि n पर प्रतिबंध काफी बड़ा था, इसलिए संख्याओं की संरचना को समझना आवश्यक था, जो ऐसे खिलाड़ी के लिए स्थिति जीत रहे हैं जो ऐसे राज्य से शुरू होता है। हम बताते हैं कि इस सेट को लगातार संख्याओं के O (लॉग एन) खंडों के एक संघ के रूप में दर्शाया जाता है, जिनमें से प्रत्येक में प्रत्येक नंबर या हर दूसरे नंबर पहले खिलाड़ी के लिए एक जीतने की स्थिति है।

हम पुनरावर्ती रूप से इस सेट का निर्माण करेंगे। प्रक्रिया F (n) को ऐसे सभी सेगमेंट के सेट को वापस करने दें, और इनवॉयरेंट संतुष्ट है: वह खिलाड़ी जिसने n loses से अधिक संख्या के लिए एक चाल बनाई।

हम दो मामलों पर विचार करते हैं। N को विषम होने दो। फिर 2 से n-1 तक कोई भी संख्या एक जीतने की स्थिति है, और कोई भी विषम संख्या एक खोने की स्थिति है। हम दिखाते हैं कि पहला खिलाड़ी हमेशा सुनिश्चित कर सकता है कि वह एक समान स्थिति से आगे बढ़े, और एक विषम स्थिति से उसका विरोधी। दरअसल, यदि पहला खिलाड़ी x को संख्या x + 1 में बदलता है, तो दूसरा खिलाड़ी x + 1 को केवल सम संख्या में बदल सकता है। यह केवल इस बात पर ध्यान देने के लिए है कि संख्या n विषम है, और इसलिए पहले खिलाड़ी के पास हमेशा एक चाल होती है जिससे उसकी हार नहीं होती है। प्रेरण द्वारा जारी रखने पर, हमें पता चलता है कि यदि पहला खिलाड़ी सम संख्या से शुरू होता है, तो उसके पास जीतने की रणनीति है। ऐसे मामले में जब पहला खिलाड़ी विषम संख्या के साथ शुरू होता है, दूसरा खिलाड़ी उसी रणनीति का उपयोग करता है और जीतता है।

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

संख्या l पर विचार करें जो n / 2 से अधिक होगी; इस स्थिति में, स्थिति l खो रही है। संख्या n / 2 की समानता के आधार पर, l या तो n / 2 + 1 या n / 2 + 2 के बराबर है। अब हम सभी संख्याओं को l / 2 से n / 2 तक समावेशी मानते हैं। इन सभी पदों पर विजय प्राप्त होगी, क्योंकि यदि आप इनमें से किसी भी संख्या को दोगुना करते हैं, तो आपको n / 2 और समकाल से अधिक संख्या मिलती है, और ऐसी स्थिति खो रही है। हमें दो सेगमेंट मिले, जिनमें से प्रत्येक पर प्रत्येक स्थान जीत रहा है, और दूसरे पर - प्रत्येक सेकंड।

ध्यान दें कि शेष खंडों को एफ (एल / 2 - 1) कॉल करके प्राप्त किया जा सकता है। मामलों के विश्लेषण से पता चलता है कि l / 2 - 1 हमेशा n / 4 के बराबर होता है, नीचे गोल होता है। सुनिश्चित करें कि आवश्यक संपत्ति संतुष्ट है। मान लें कि x ≤ l / 2 - 1. तब 2x 2 l - 2 2 n / 2, अर्थात, वे सभी पद जो l / 2 - 1 से अधिक हैं, और जिसमें यह संभव है कि वह ऐसी स्थिति से आगे बढ़ें जो l / 2 - 1 से अधिक न हो, जीतने, और इसलिए इस तरह के कदम से नुकसान होगा।

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

समस्या बी। स्नो व्हाइट और एन ड्वार्फ्स

स्नो व्हाइट n gnomes के दोस्त हैं, जिनकी संख्या 1 से n तक है। यह ज्ञात है कि इथ ग्नोम का विकास हाय सेंटीमीटर है, प्रत्येक गनोम का विकास सकारात्मक है और एन से अधिक नहीं है। यदि संख्याओं का योग उनकी कुल वृद्धि से मेल खाता है, तो राजकुमारी सूक्ति के गैर-खाली उपसमूह को सुंदर मानती है। हमें यह पता लगाने की आवश्यकता है कि क्या gnomes का एक अच्छा सेट है, और यदि कोई है, तो इस तरह के सेट का एक उदाहरण आवश्यक है।

इनपुट प्रारूप
पहली पंक्ति में एक पूर्णांक टी - परीक्षणों की संख्या है। अगली 2t पंक्तियों में t अलग-अलग परीक्षण प्रश्न होते हैं। क्वेरी की पहली पंक्ति में n - gnomes (1 ≤ n of 10 ⁶ ) की संख्या है, दूसरे में n सकारात्मक संख्याएं हैं जो n से अधिक नहीं हैं - gnomes की वृद्धि।

सभी अनुरोधों के लिए n का योग 10 ⁶ से अधिक नहीं है।

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

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

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

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

समस्या सी। त्वरित-त्वरित प्रकार

आपको त्वरित सॉर्ट एल्गोरिथ्म के बारे में पता होना चाहिए। तत्वों को दोहराए बिना किसी सरणी को छाँटते हुए, इसकी कुछ भिन्नता पर विचार करें।

function qqsort(A: array of int): array of int if isSorted(A): return A middle = pick(A) aLess = elements of A less then middle aGreater = elements of A greater then middle return qqsort(aLess) + [middle] + qqsort(aGreater) 

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

यदि कोई सरणी पहले से पास है तो तर्क द्वारा सॉर्ट किया गया है तोSSours (a) फ़ंक्शन चेक करता है। पिक फ़ंक्शन सरणी से कुछ तत्व देता है, जिसे तर्क के रूप में इसे पास किया जाता है। यह सरणी के किसी भी तत्व को वापस कर सकता है।

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

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

उदाहरण के लिए, यदि आप सरणी A = [1, 2, 6, 7, 5, 3, 4, 8, 9] को क्रमबद्ध करना चाहते हैं, तो यदि नंबर 5 को वापस लेने के लिए पहली कॉल, सरणी aLess होगी [1, 2, 3] 4], और एग्रीटेटर सरणी है [6, 7, 8, 9]। तदनुसार, क्यूकॉर्ट पुनरावर्ती कॉल तुरंत बाहर निकल जाएगी, क्योंकि आईस्रोइट पर कॉल उन में वापस आ जाएगी और सरणी को सॉर्ट किया जाएगा। यह इष्टतम है, इस मामले में पिक फ़ंक्शन को केवल 1 बार बुलाया गया था।

इनपुट प्रारूप
पहली पंक्ति में परीक्षणों की संख्या t है। अगला, 2t लाइनों में, परीक्षण स्वयं निर्धारित किए जाते हैं। परीक्षण विवरण की पहली पंक्ति में एक सकारात्मक संख्या n है - सरणी का आकार। दूसरी पंक्ति में सरणी एआई (1 ≤ एआई if एन, अगर मैं contains जे, तो एआई। एजे) शामिल है। सभी परीक्षणों में सरणियों का कुल आकार 106 से अधिक नहीं है।

आउटपुट स्वरूप
प्रत्येक परीक्षण मामले के लिए एक एकल संख्या प्रिंट करें - पिक फ़ंक्शन को न्यूनतम संख्या जो कि qqortort फ़ंक्शन का उपयोग करते समय छँटाई की जा सकती है।

पार्स:
समस्या में, त्वरित सॉर्ट एल्गोरिथ्म के कुछ संशोधन दिए गए थे और इसे क्रमबद्ध करने के लिए आवश्यक पिक फ़ंक्शन के लिए सबसे छोटी संख्या को कॉल करने के लिए दिए गए क्रमचय की आवश्यकता थी।

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

यदि x numbers a और a लगातार प्राकृतिक संख्याओं का समूह है, तो बाएँ (a, x) और दाएँ (a, x) भी लगातार संख्याओं के समुच्चय हैं। यह सत्य है, क्योंकि यदि L से R तक पूर्णांकों का समुच्चय है, तो बाएँ से (a, x) L से x-1 तक पूर्णांकों का समुच्चय है, और दायें (a, x) x + 1 से पूर्णांकों का समुच्चय है आर

आइए दिए गए एरे को देखें। W [i] तत्व i की स्थिति को a: w [a [i]] = i में बताता हूं। हम सरणी को 1 से बढ़ रही संख्याओं की श्रृंखला में विभाजित करते हैं ताकि सरणी में एक ही श्रृंखला के अंदर के तत्व एक पंक्ति में जाएं: 1 को पहली श्रृंखला में जोड़ें, फिर अगर w [1] <w [2], तो इसमें 2 जोड़ दें, आदि।

उदाहरण के लिए, चेन ([1, 2, 6, 7, 5, 3, 4, 8, 9]) = [[1, 2, 3, 4], [5], [6, 7, 8, 9]] । आइए देखें कि एक्स द्वारा विभाजित करने के बाद इन जंजीरों का क्या होता है। हम बाईं ओर (ए, एक्स) और दाईं ओर (ए, एक्स) में जंजीर तोड़ते हैं। चलो पढ़ाई छोड़ दी। ठीक वैसे ही व्यवहार किया जाता है। चेन [c..d] a चेन (ए) और x की सापेक्ष स्थिति पर विचार करें।

• x> d। इस मामले में, [c..d] case चेन (बाएं (ए, एक्स))
• c <x। इस मामले में, [c..d] c चेन (बाएं (ए, एक्स))। और [c..d] से एक भी तत्व जंजीरों से किसी भी श्रृंखला में नहीं दिखाया गया है (बाएं (ए, एक्स))
• x = d, x। c। यहां [c..d-1]-चेन (बाएं (ए, एक्स))
• x = c, x ≠ d। दूसरे मामले के समान, [c..d] second चेन (बाएं (a, x))
• अंत में, अंतिम मामला: x = c = d। इस मामले में, श्रृंखला से कुछ भी नहीं [c..d] (जो, वास्तव में, [c]) या तो जंजीरों (बाएं (ए, एक्स)) या चेन (दाएं (ए, एक्स)) में गिर जाता है

इन मामलों को देखते हुए, कोई निम्नलिखित को नोटिस कर सकता है: यदि दो तत्व एक ही श्रृंखला में एक बार थे, तो वे एक ही क्रमबद्ध सरणी के विभिन्न श्रृंखलाओं में कभी समाप्त नहीं होंगे। हालांकि, वे विभिन्न श्रृंखलाओं में दिखाई दे सकते हैं, लेकिन विभिन्न सरणियों को छांटने के ढांचे के भीतर। उदाहरण के लिए, एक = [५, २, ३, ४, १], जंजीर (ए) = [[१], [२, ३, ४], [५]], x = ३, बाएं (ए, ३) = [२, १], जंजीरों (बाएं (ए, ३)) = [[१], [२]], दाएं (ए, ३) = [५, ४], जंजीरों (दाएं (ए, ३)) = [ [४], [५]]। यह देखा जा सकता है कि संख्या 2 और 4, जो पहले एक ही श्रृंखला [2, 3, 4] में थे, अलग-अलग तरीकों से निकले, लेकिन क्रमबद्ध सरणियाँ अलग हैं ([2, 1] और [5, 4])।

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

अनौपचारिक रूप से बताएं कि आप क्या हासिल करना चाहते हैं। हमारे पास एक सरणी है। इस पर चेन (ए) का निर्माण करते हैं। परिणामी सेट में, विभाजक के रूप में केवल श्रृंखला के सिरों को चुनना फायदेमंद है। क्रमबद्ध सरणी प्राप्त करने के लिए, जंजीरों के बीच के सभी अंतराल को समाप्त करना आवश्यक है। अगर शुरू में जंजीर [c..d] और [d + 1..e] थे, और तत्व d को विभाजक के रूप में चुना गया था, तो अंतर (d..d + 1) हमें उत्साहित करना बंद कर देता है, क्योंकि सभी तत्व इसके बाईं ओर हिट हो गए हैं एक सरणी में, और दाईं ओर सब कुछ दूसरे में है। इस प्रकार, एक अंतर को समाप्त कर दिया गया, और उन सभी को #chains (a) - 1 को समाप्त करना चाहिए, जहां # आकार को दर्शाता है।

बता दें कि लंबाई 1: [c..d-1], [d], [d + 1..e] की पहली और अंतिम श्रृंखला नहीं है। डी को अलग करने वाले तत्व के रूप में लें। फिर, चूंकि यह श्रृंखला [d] के लिए सबसे बाईं ओर है, इसलिए अंतर (d-1..d) समाप्त हो जाएगा। चूंकि यह समान श्रृंखला के लिए सबसे सही भी है, इसलिए अंतर (d..d + 1) को भी समाप्त कर दिया जाएगा। इस प्रकार, एक अलग के रूप में एक गैर-चरम श्रृंखला के एकल तत्व की पसंद एक बार में दो अंतराल को समाप्त करती है।

चलो किसी प्रकार का इष्टतम उत्तर है, और अलग करने वाले तत्व डी ₁ , डी ₂ , ..., डी _{के इसमें} दिखाई देते हैं। उनमें से प्रत्येक ने कुछ अंतराल को समाप्त कर दिया। हम निम्नलिखित करते हैं: पहले अलग करने वाले तत्व के रूप में min {d ₁ , ..., d _k } चुनें। एरे को छोड़े गए बाएं में तोड़ दिया जाएगा और अभी तक सही टुकड़ों को नहीं छांटा जाएगा। D _{i के} बीच दूसरा न्यूनतम चुनें और इसे दाएं टुकड़े के लिए एक अलग तत्व बनाएं। हम दोहराएंगे जब तक d _मैं बाहर चला जाता _हूं । यह सुनिश्चित करना आसान है कि अलग करने वाले तत्वों को चुनने की इस रणनीति के साथ, प्रत्येक पहले की पसंद में समान अंतराल को समाप्त कर देगा। इस प्रकार, गतिशील प्रोग्रामिंग की मदद से समस्या को हल करना संभव है, पहले कुछ जंजीरों को एक में संयोजित करने के लिए न्यूनतम आवश्यक संख्याओं की गणना करना। उत्तर सभी श्रृंखलाओं को एक में मिलाने के लिए आवश्यक न्यूनतम चरणों की संख्या होगी।

टास्क डी। रोबोट

बोरिया एक रोबोट प्रोग्रामिंग प्रतियोगिता में भाग ले रहा है। प्रारंभिक समय में, रोबोट आकार के एन × मीटर कोशिकाओं के एक आयताकार क्षेत्र के ऊपरी बाएं सेल में स्थित है। रोबोट का लक्ष्य कम से कम सही सेल में जल्दी से जल्दी पहुंचना है। एक चाल में, रोबोट सबसे पहले उसके बगल में स्थित वर्तमान क्षेत्र सेल से चलता है और उसके बगल में।

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

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

इनपुट प्रारूप
पहली पंक्ति में एक पूर्णांक t - फ़ील्ड की संख्या होती है। प्रत्येक क्षेत्र का वर्णन इस प्रकार है। पहली पंक्ति में दो पूर्णांक n और m होते हैं - कोशिकाओं में क्षेत्र की ऊँचाई और चौड़ाई (1, n, m inte ^{3 3} )। अगली n लाइनों में प्रत्येक अक्षर m है। यदि प्रतीक B है, तो संबंधित सेल काला है, और यदि W है, तो सफेद है।
सभी क्षेत्रों में कोशिकाओं की कुल संख्या 10 ⁶ से अधिक नहीं है।

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

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

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

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

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

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

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

कार्य ई। टीकाकरण

बेटलैंड में स्वास्थ्य मंत्रालय ने देश के निवासियों के बीच कैपिबारा फ्लू की घटनाओं का बड़े पैमाने पर अध्ययन किया है। वैज्ञानिकों ने पाया है कि इन्फ्लूएंजा के खिलाफ मानव प्रतिरक्षा एक गैर-नकारात्मक पूर्णांक की विशेषता है। हर साल 4 जनवरी को, सूर्य पर फैलने के परिणामस्वरूप, प्रत्येक व्यक्ति की प्रतिरक्षा कम हो जाती है। हालाँकि, वह नकारात्मक नहीं बन सकता। यदि मूल प्रतिरक्षा कश्मीर से कम थी, तो प्रतिरक्षा 0 के बराबर हो जाती है।

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

रोग का बेहतर अध्ययन करने के लिए, वैज्ञानिकों ने अधिक आंकड़े एकत्र करने का निर्णय लिया। उन्हें अपने जीवन के कुछ वर्षों में कुछ लोगों की प्रतिरक्षा की गणना करने में मदद करें।

प्रत्येक व्यक्ति उस वर्ष के बारे में जानता है जिसमें वह पैदा हुआ था, जिस वर्ष उसकी प्रतिरक्षा को जानना आवश्यक है, साथ ही जन्म के समय उसकी प्रतिरक्षा भी। हम मानते हैं कि बैटलैंड के सभी निवासी इसी वर्ष 1 जनवरी को पैदा हुए थे, और 3 जनवरी को प्रतिरक्षा आवश्यक है।

इनपुट प्रारूप
पहली पंक्ति में एक पूर्णांक टी - परीक्षणों की संख्या है।

प्रत्येक परीक्षण निम्नानुसार परिभाषित किया गया है। पहली पंक्ति में तीन पूर्णांक n, m और k हैं - टीकाकरण की संख्या, अनुरोधों की संख्या और प्रत्येक वर्ष के 4 जनवरी को प्रतिरक्षा क्षमता घट जाती है जिसके परिणामस्वरूप सौर भड़कना (1, n, m ≤ 10 ⁵ , 1 ≤ k ≤ 10 ⁹ ) । निम्नलिखित टीकाकरण का वर्णन है: अगली n लाइनों में दो संख्याएँ हैं - जिस वर्ष टीकाकरण दिया गया था, और जिस राशि से प्रत्येक व्यक्ति की प्रतिरक्षा में वृद्धि हुई थी। यह गारंटी है कि साल सख्ती से बढ़ते क्रम में दिए गए हैं।

अगली मी लाइनों में प्रश्न हैं: व्यक्ति के जन्म वर्ष का प्रतिनिधित्व करने वाले तीन पूर्णांक, वह वर्ष जिसमें उसकी प्रतिरक्षा जानना आवश्यक है, और प्रारंभिक मानव प्रतिरक्षा भी।

परीक्षणों में सभी संख्याएं नकारात्मक हैं और 10 ⁹ से अधिक नहीं हैं। यह गारंटी दी जाती है कि जिस वर्ष किसी व्यक्ति की प्रतिरक्षा जानना आवश्यक है वह उसके जन्म के वर्ष से कम नहीं है। सभी परीक्षणों में टीकाकरण की कुल संख्या 200,000 से अधिक नहीं है। इसी तरह, कुल लोगों की संख्या 200,000 से अधिक नहीं है।

आउटपुट स्वरूप
प्रत्येक अनुरोध के लिए, एक अलग लाइन में, उसी वर्ष में मानव प्रतिरक्षा प्रदर्शित करें।

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

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

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

टास्क एफ उड़ान अनुसूची

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

Baytland में n शहर हैं, और एयरलाइन मी अनुसूचित उड़ानें प्रदान करती है जो आपको कुछ ट्रांसफर के साथ - संभवतः किसी भी Baytland शहर से किसी अन्य में जाने की अनुमति देती है। फ्लाइट नंबर i, शहरों को नंबर ai और bi से जोड़ता है और दिन में एक बार बॉल्टलैंड में p घंटे से मिलकर चलता है। I-th उड़ान का उड़ान समय ली घंटे है, और यह उस समय उड़ान भरता है जब अगले दिन की शुरुआत से si घंटे बीत चुके होते हैं। , ai bi bi ai . , , , , , .

. , ; , . , .

, , x, y. .

इनपुट प्रारूप
t. .

n, m p (1 ≤ n ≤ 10 ⁴ , 1 ≤ m, 1 ≤ p ≤ 10 ⁹ ) — , .

m . a, b, l s (1 ≤ a, b ≤ n, a ≠ b, 1 ≤ l ≤ 10 ⁹ , 0 ≤ s < p) — , , . , .

c (1 ≤ c ≤ 10 ⁵ ) — , . c x y (1 ≤ x, y ≤ n) — , , . (x + ans — 1) mod n + 1 ( y + ans — 1) mod n + 1, ans — , , 0 .

, 10 ⁴ , — 10 ⁵ .

आउटपुट स्वरूप
— , .

:
. , , , , .

, , , . , , .

. , , . :

• , 0 ( )
• , 0

, 2 ^k 2 ^{k + 1} O(1) , 2 ^{k + 1} 2 ^k , , , , .

, , , , O(logn) , . , , .

, , . -, , - , , . : , , , . , , .

, , , , : , , , , , . , , :

• , 0 ( ) , ,
• , 0 , ,
• , 0 , ,
• , 0 , ,

, , , .
, . , (, ) , , , , .
, — , , .

RCC 2013 . F , , , — 50 .

, ( , ) .