एसीएम ICPC 2013 प्रोग्रामिंग वर्ल्ड चैम्पियनशिप फाइनल

पिछले हफ्ते ACM ICPC 2013 वर्ल्ड टीम प्रोग्रामिंग चैम्पियनशिप में , 11 समस्याएं थीं, जिनमें से एक, आवंटित समय में, किसी भी टीम द्वारा सही ढंग से हल नहीं की जा सकी।

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

इस साल एसीएम ICPC में स्वीडन, नीदरलैंड, अमेरिका, स्लोवाकिया, बेलारूस और रूस के 21 विश्लेषक थे। और उनमें से 10 यांडेक्स के थे। विभिन्न वर्षों में वे सभी ICPC के विजेता थे। विशेष रूप से हैबर के लिए, उन्होंने चैम्पियनशिप के सभी कार्यों को हल किया।

टास्क ए स्व-विधानसभा

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

एक कार्यक्रम लिखें जो यह निर्धारित करेगा कि अणुओं का प्रदान किया गया सेट असीमित आकार की संरचनाओं में इकट्ठा हो सकता है या नहीं। इसके अलावा, 1) समस्या प्लानेर संरचनाओं द्वारा सीमित है और 2) प्रत्येक अणु में एक वर्ग का रूप है, सभी अणुओं का आकार समान है। वर्ग के चार पक्ष सतहों को इंगित करते हैं जिसके द्वारा अणु संगत अणुओं के साथ संयोजन कर सकते हैं।

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

लिंक लेबल दो प्रकार के होते हैं:

• लैटिन कैपिटल लेटर (A..Z) और एक अक्षर + या -। दो सतहों को जोड़ा जा सकता है यदि उनके बांड के निशान एक ही अक्षर द्वारा निरूपित किए जाते हैं, लेकिन विभिन्न संकेत। उदाहरण के लिए, A + A- के साथ संगत है, लेकिन A + और B- के साथ संगत नहीं है।
• दो शून्य 00. एक बंधन चिह्न 00 का मतलब है कि यह सतह एक बंधन नहीं बना सकती है (यहां तक ​​कि उसी सतह के साथ चिह्नित 00)।

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

आकृति अणुओं की तीन प्रजातियों का उदाहरण और उनसे इकट्ठे सीमित आकार की संरचना का उदाहरण देती है (यह किसी भी प्रकार के अणुओं के लिए एकमात्र संभव संरचना नहीं है)।



इनपुट डेटा इनपुट में एक परीक्षण होता है। प्रत्येक परीक्षण में दो लाइनें होती हैं। पहली पंक्ति में संख्या n (1 line n , 000 40,000) होती है - अणुओं के प्रकारों की संख्या। दूसरी पंक्ति में प्रत्येक के 8 वर्णों के एन सब्सट्रिंग्स हैं - प्रत्येक प्रकार के अणु का वर्णन, और सतहों को दक्षिणावर्त वर्णित किया गया है।

आउटपुट डेटा । अनबाउंड शब्द को प्रिंट करें यदि अणु एक अनंत संरचना बना सकते हैं और अन्यथा बंधे हुए शब्द।

समस्या ए का समाधान
विश्लेषण के लेखक मॉस्को यूनिवर्सिटी यूनिवर्सिटी की टीम के हिस्से के रूप में एसीएम ICPC 2011 के कांस्य पदक विजेता वसीली अस्ताखोव हैं। एमवी लोमोनोसोव।

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

समस्या बी। हे, बेहतर बेट्टर

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

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

सादगी के लिए, मान लीजिए कि सभी दांव $ 1 के हैं और अदायगी $ 2 है। अब मान लीजिए कि x 20 है। यदि आप खेल खत्म करने से पहले केवल 10 दांव लगाते हैं, और उनमें से केवल 3 जीतते हैं, तो आपका कुल नुकसान $ 3.2 होगा। यदि 6 दांव जीतते हैं, तो आपकी जीत $ 2 होगी।

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

इनपुट डेटा इनपुट डेटा में एक परीक्षण होता है, जिसमें रिटर्न x (0 100 x <100) का प्रतिशत और प्रतिशत p (0 winning p ≤ 50) में जीतने की संभावना होती है। x और p में अधिकतम दो दशमलव स्थान हैं।

आउटपुट डेटा । 10 ^-3 से अधिक की पूर्ण त्रुटि के साथ अधिकतम अपेक्षित लाभ प्रिंट करें।

समस्या बी का समाधान
विश्लेषण के लेखक मिखाइल लेविन , 2007 एसीएम ICPC कांस्य पदक विजेता, मास्को राज्य विश्वविद्यालय की टीम के हिस्से के रूप में 2008 ACM ICPC रजत पदक विजेता हैं एमवी लोमोनोसोव।

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

संख्या P ( A , B ) के लिए, पुनरावृत्ति संबंध रखती है:

।

जहां प्रत्येक सिक्के पर टॉस जीतने की संभावना है। इसके अलावा, पी (0, ए + बी ) = 1, और पी ( ए + बी , 0) = 0. यदि हम क्रम 2 के इस रैखिक पुनरावृत्ति को हल करते हैं, तो हम प्राप्त करते हैं

।

जहाँ ।

यदि हम प्रत्येक इनपुट ( x , p ) के लिए सभी संभावित जोड़े ( ए , बी ) से गुजर सकते हैं, तो हम ऐसा करेंगे, और फिर सबसे अच्छा चुनें। अनंत संख्या में जोड़े ( ए , बी ) हैं, लेकिन यदि आप कई संख्यात्मक प्रयोग करते हैं, तो आप देख सकते हैं कि ए और बी बढ़ने के साथ , अपेक्षित लाभ पहले बढ़ता है और फिर गिरना शुरू हो जाता है (आप ए और बी के एक समारोह के रूप में अपेक्षित परिणाम के उत्तलता साबित कर सकते हैं), इसलिए। यह हमेशा जोड़े की एक सीमित संख्या की जांच करने के लिए पर्याप्त है। इसके अलावा, कोई यह नोटिस कर सकता है कि ए और बी के लिए सबसे अच्छे मूल्य अधिक हैं, निकटतम पी 0.5 है, और x से 100 है। सबसे खराब स्थिति p = 0.4999, x = 99.99 है। यह पता चला है कि इस मामले में ए को 21000 तक छाँटना पर्याप्त है, और बी - 2500 तक, और इस तरह की थकावट समय सीमा को पार करने के समाधान के लिए पर्याप्त है।

समस्या सी। निश्चित रूप से आप बधाई

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

दुर्भाग्य से, इस तथ्य के कारण कि ड्राइवर स्वार्थी हैं, वे कभी भी केंद्र के लिए सबसे कम संभव पथ नहीं लेंगे, भले ही आप उनसे इसके बारे में पूछें। आप केवल उन्हें सलाह दे सकते हैं कि कौन सा रास्ता चुनना है।

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

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



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

इनपुट डेटा इनपुट में एक परीक्षण शामिल है। पहली पंक्ति में तीन नंबर n, m और c हैं , जहाँ n (1 ≤ n ) 25000) चौराहों की संख्या है, m (0 ≤ m ≤ 50,000) शहर में सड़कों की संख्या है और c (0 ≤ c ≤ 1000) ड्राइवरों की संख्या है। अगली मी लाइनों में से प्रत्येक में तीन नंबर होते हैं x _i , y _i और t _i जो सड़क का वर्णन करता है, जहां x _i और y _i (1 y x _i , y _i ) n) विभिन्न चौराहों की संख्या है जो वर्णित सड़क जोड़ता है और t _i ( 1≤ t _i ≤ 10000) - चालक को किसी भी दिशा में सड़क के शुरू से अंत तक पहुंचने में खर्च करने का समय। यह गारंटी है कि आप किसी भी चौराहे से केंद्र तक पहुंच सकते हैं। अंतिम पंक्ति में सी संख्याएं हैं, जिसमें प्रारंभिक चौराहों का वर्णन किया गया है, जिस पर कारें स्थित हैं।

आउटपुट डेटा । उन चालकों की अधिकतम संख्या प्रिंट करें, जो ट्रैफ़िक जाम के बिना शहर के केंद्र पर जा सकते हैं।

समस्या सी का समाधान
विश्लेषण के लेखक मिखाइल लेविन हैं।

हम ओ ( एम लॉग एन ) में एक गुच्छा के साथ डीजकस्ट्रा एल्गोरिथ्म का उपयोग करते हुए अंतिम छोर तक सभी वर्टीकल यू से सबसे छोटी दूरी डी ( यू ) की गणना करते हैं। चूँकि हर कोई केवल सबसे छोटे रास्ते पर ही जाना चाहता है, कार केवल यू से v की दिशा में ऐसे किनारों ( u , v ) के साथ जाएगी जैसे d ( u ) = d ( v ) + l ( u , v ), जहाँ l ( u , v ) किनारे की लंबाई ( u , v ) है। हम केवल ऐसे किनारों से मिलकर एक नए निर्देशित ग्राफ का निर्माण करते हैं।

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

हम अंतिम एक से एक ही दूरी पर कोने के प्रत्येक समूह के लिए अधिकतम प्रवाह पाते हैं और उत्तर जोड़ते हैं - यह समस्या का उत्तर होगा। प्रवाह को बढ़ाने वाले एक मार्ग को खोजने में O ( m ) लगता है, और कुल मिलाकर c से अधिक ऐसे पथों के लिए नहीं मिलेंगे, इसलिए कुल मिलाकर, अधिकतम प्रवाह को खोजने के लिए O ( mc ) से अधिक नहीं में प्रदर्शन किया जाएगा। कुल में, समाधान की जटिलता हे ( एम लॉग एन + एमसी ), जो दिए गए प्रतिबंधों को पास करता है।

कार्य डी। कारक

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



F (k) k के प्रमुख कारकों को क्रमबद्ध करने के लिए विभिन्न तरीकों की संख्या से निरूपित करें। फिर एफ (20) = 3 और एफ (10) = 2।

आपको एक सकारात्मक पूर्णांक n दिया जाता है, और यह गारंटी दी जाती है कि किसी भी n के लिए k मौजूद है जैसे कि f (k) = n । इस तरह के एक न्यूनतम कश्मीर को परिभाषित करें।

इनपुट डेटा इनपुट फ़ाइल में 1000 से अधिक परीक्षण नहीं हैं, जिनमें से प्रत्येक को एक अलग लाइन पर लिखा गया है। प्रत्येक परीक्षण में एक धनात्मक पूर्णांक n <2 ^{63 होता है} ।

आउटपुट डेटा । प्रत्येक परीक्षण के लिए, संख्या n और न्यूनतम k > 1 को प्रिंट करें जैसे कि f ( k ) = n । परीक्षणों में संख्याओं को इस तरह से चुना जाता है कि k <2 ⁶³ ।

समस्या डी का समाधान
विश्लेषण के लेखक फिएटटेक की टीम के हिस्से के रूप में एसीएम ICPC 2012 के स्वर्ण पदक विजेता रेनाट गिमदेव हैं।

यह एक बहुत ही सरल कार्य है जिसमें कई अलग-अलग समाधान थे। मैं तुम्हें सबसे छोटा एक दूंगा।

ध्यान दें कि यदि हम सरल कारकों में विघटित होते हैं n = p ₁ ^{k ₁} p ₂ ^{k ₂} ... p _t ^{k _t} , तो primes के उत्पाद के रूप में आदेशित अभ्यावेदन की संख्या बराबर होगी । यह सरल कॉम्बिनेटरियल रीजनिंग से आता है: आप N के विभिन्न प्रमुख कारकों को आदेश दे सकते हैं! तरीके। यदि इन कारकों के बीच समान कारक हैं, तो सभी ऑर्डर जो केवल समान कारकों के क्रम में भिन्न होते हैं, वास्तव में मेल खाते हैं। समान कारकों के k _{i के} प्रत्येक समूह को k _i पुनर्व्यवस्थित किया जा सकता है! तरीके। इसलिए, प्रत्येक अनूठे क्रमचय की गणना k ₁ ! K ₂ ! ... k _t ! समय और इस संख्या को विभाजित किया जाना चाहिए। यह सूत्र हमें प्रमुख कारकों में संख्या k के अपघटन को जानते हुए, f ( k ) की शीघ्र गणना करने में सक्षम बनाता है।

इसके अलावा, यह ध्यान दिया जाना चाहिए कि आदेशों की संख्या इस बात पर निर्भर नहीं करती है कि _मैं किस p के बराबर _हूं और आपस में k कैसे आदेशित हैं। इसलिए, यदि हम न्यूनतम संख्या की तलाश कर रहे हैं, तो हमें इसे फॉर्म n = 2 ^{k ₁} 3 ^{k ₂} 5 ^{k ₃} ..., इसके अलावा, k ₁ 2k ₂ ≥k ₃ the ... की संख्याओं के बीच देखना होगा, यह पता चलता है कि संख्याओं की संख्या 2 ⁶³ से कम है। बहुत सारे नहीं हैं (जिस स्थिति में वे केवल उन समाधानों को देखने के लिए कहते हैं जो 2 ⁶³ से कम हैं), उनमें से लगभग 40,000 हैं और वे आसानी से पुनरावृत्ति द्वारा उत्पन्न होते हैं। उनमें से प्रत्येक के लिए, एक ऊपर वर्णित सूत्र के अनुसार एफ (के) पा सकता है और सहयोगी सरणी में स्टोर कर सकता है प्रत्येक प्राप्त एफ (के ) के लिए संख्या के न्यूनतम मान। उसके बाद, स्थिति से प्रत्येक अनुरोध इस सहयोगी सरणी को कॉल के दौरान संसाधित किया जाता है।

समस्या ई। हार्वर्ड

शब्द "हार्वर्ड आर्किटेक्चर" एक कंप्यूटर पर निर्देश और डेटा के लिए भौतिक रूप से साझा मेमोरी के साथ लागू होता है। यह शब्द हार्वर्ड मार्क I कंप्यूटर से आता है, जिसे 1944 में बनाया गया था। यह निर्देशों के लिए पेपर टेप और डेटा के लिए एक रिले का उपयोग करता था।

कुछ आधुनिक माइक्रोकंट्रोलर हार्वर्ड आर्किटेक्चर का उपयोग करते हैं, लेकिन पेपर टेप और रिले नहीं! डेटा बैंकों में है, जिनमें से प्रत्येक में समान संख्या में सेल हैं। प्रत्येक डेटा एक्सेस इंस्ट्रक्शन में बैंक के भीतर एक बाइट ऑफसेट f और बिट a है , जिसका उपयोग बैंक नंबर निर्धारित करने के लिए किया जाता है। यदि a 0 है, तो बैंक में नंबर 0 के साथ कॉल आता है। यदि 1 है, तो बैंक नंबर एक विशेष बैंक चयन रजिस्टर (RBB) में संग्रहीत किया जाता है।

उदाहरण के लिए, मान लीजिए कि हमारे पास 8 बैंक हैं जिनमें से प्रत्येक में 8 सेल हैं। सेल नंबर 5 तक पहुंचने के दो तरीके हैं: एक निर्देश = 0 और f = 5, या दो निर्देशों के साथ, आरवीबी मान को 0 पर सेट करना और फिर निर्देश के साथ = 1 और एफ = 5 का उपयोग करना। जाहिर है, पहला तरीका तेज़ है, क्योंकि आपको आरबीएम के मूल्य को निर्दिष्ट करने की आवश्यकता नहीं है। अब मान लीजिए कि आप सेल 20 को उसी मेमोरी में एक्सेस करना चाहते हैं। अब हम केवल एक ही तरीका लागू करते हैं: आरवीबी 2 (यदि वांछित मूल्य पहले से संग्रहीत नहीं है) का मान सेट करके निर्देश को निष्पादित करने के लिए, और फिर एक = 1 और f = 4. के साथ निर्देश संचालन का एक अनुक्रम है। प्रत्येक ऑपरेशन है:

• चर तक पहुंच को वीआई के रूप में लिखा जाता है, जहां मैं एक सकारात्मक पूर्णांक हूं;
• पुनरावृत्ति, Rn E रूप में लिखी जाती है , जहाँ n एक धनात्मक पूर्णांक है, और — , n .
  
  कार्य कार्यक्रम का न्यूनतम निष्पादन समय निर्धारित करना है। अर्थात्, बैंकों की संख्या और आकार को जानने के साथ-साथ एक कार्यक्रम होने पर, कार्यक्रम को निष्पादित करने के लिए आवश्यक निर्देश 1 (कोशिकाओं तक पहुंच और, संभवतः, आरवीबी मूल्य निर्धारित करना) की न्यूनतम संख्या निर्धारित करना आवश्यक है। ऐसा करने के लिए, आपको चर को मेमोरी कोशिकाओं के साथ और सभी मैपिंग के बीच जोड़ने की जरूरत है, वह निर्धारित करें जो निर्देशों की संख्या को कम करता है। यह संख्या स्वयं देना आवश्यक है। कृपया ध्यान दें कि पहले असाइनमेंट से पहले आरवीबी के मूल्य को परिभाषित नहीं किया गया है।
  
  इनपुट डेटा दो पंक्तियों से मिलकर एक परीक्षण होता है। पहले बी और एस में - चर की संख्या और मात्रा जो बैंक में संग्रहीत की जा सकती है। दूसरी पंक्ति में एक गैर-खाली कार्यक्रम है जिसमें 1000 से अधिक तत्व नहीं हैं (प्रत्येक Rn , V i और E को एक तत्व के रूप में गिना जाता है)।
  
  यह माना जा सकता है कि:
  
  • आरएन की पुनरावृत्ति में, एन ¹ rep एन ⁶ 10 ^{6 को} संतुष्ट करता है;
  • पुनरावृत्ति शरीर Rn E ;
Vi , i 1 ≤ i ≤ min ( bs; 13 );
10 12 .
Rn E ;
Vi , i 1 ≤ i ≤ min ( bs; 13 );
10 12 .

    आउटपुट डेटा । एकल संख्या प्रिंट करें - कार्यक्रम को निष्पादित करने के लिए आवश्यक न्यूनतम निर्देशों की संख्या।
    
    समस्या ई का समाधान
    विश्लेषण के लेखक स्टैनिस्लाव पाक हैं , जो सेराटोव स्टेट यूनिवर्सिटी की टीम के हिस्से के रूप में एसीएम ICPC 2009 के स्वर्ण पदक विजेता हैं।
    
    

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

    1. हम यह मान सकते हैं कि शून्य बैंक भरा हुआ है अगर किसी अन्य बैंक में भरा हुआ सेल है, क्योंकि शून्य बैंक तक पहुंच मुफ्त है।
    2. शून्य से अधिक संख्या वाले बैंक समान हैं, इसलिए, यह माना जा सकता है कि इन बैंकों की कोशिकाओं में प्रदर्शित चर की न्यूनतम संख्या का आदेश दिया जाता है, उदाहरण के लिए, आरोही क्रम में।
    3. हम मान सकते हैं कि किन्हीं दो बैंकों में भरी हुई कोशिकाओं की कुल संख्या s से अधिक है।

    
    
    कटे-कटे 1 - 3 और दिलचस्प मैपिंग के इनपुट डेटा की सीमाओं को ध्यान में रखते हुए, लगभग 3 · 10 ⁶ ।
    
    चूंकि शून्य बैंक एक्सेस करना मुफ्त है, आप प्रोग्राम से इस बैंक के लिए मैप किए गए वेरिएबल को हटा सकते हैं। शेष चर i और j की प्रत्येक जोड़ी के लिए , आप C _{ij की} गणना कर सकते हैं - चर i तक पहुँचने के बाद चर i तक पहुँचने के संचालन की लागत, जिसके बाद यह कार्यक्रम का अनुकरण करने के लिए बना रहता है।

    
    
    

    समस्या एफ कम बिजली

    
    आप कंप्यूटर के लिए उन्नत चिप्स डिजाइन करते हैं। चिप्स का उत्पादन सरल है और रेल पर रखा जाता है, हालांकि, बिजली की आपूर्ति एक समस्या का कारण बनती है, क्योंकि उपलब्ध बैटरी में अलग-अलग आउटपुट शक्तियां होती हैं।
    
    कल्पना करें कि हमारे पास प्रत्येक पर दो चिप्स के साथ n मशीनें हैं, और प्रत्येक चिप k बैटरी द्वारा संचालित है। आश्चर्यजनक रूप से, इससे कोई फर्क नहीं पड़ता कि चिप्स कितनी ऊर्जा की खपत करते हैं, हालांकि, यह महत्वपूर्ण है कि चिप्स की आउटपुट शक्तियां यथासंभव कम हो, क्योंकि इस मामले में मशीन सबसे अच्छा काम करती है। चिप की आउटपुट पावर चिप में सभी k बैटरी के बीच न्यूनतम आउटपुट पावर है। आपके पास 2nk बैटरी है जो आपको मशीनों के चिप्स पर वितरित करने की आवश्यकता है। यह पता लगा सकता है कि बैटरी को वितरित करने का कोई तरीका नहीं है ताकि चिप्स की आउटपुट शक्ति सभी मशीनों के लिए समान हो। हालांकि, आपको बिजली के अंतर को कम करने की आवश्यकता है। अधिक विवरण में, आप अपने ग्राहकों को गारंटी देना चाहते हैं कि सभी मशीनों में चिप्स की आउटपुट पावर में अंतर d से अधिक नहीं है, जबकि d को कम करने की कोशिश कर रहा है। ऐसा करने के लिए, आपको चिप्स द्वारा बैटरी के इष्टतम वितरण को खोजने की आवश्यकता है।
    
    इनपुट डेटा दो रेखाओं वाले एक परीक्षण से मिलकर। पहली पंक्ति में दो संख्याएँ n और k ( 2nk ⁶ 10 ⁶ ) हैं, दूसरी पंक्ति में 2nk पूर्णांक p _i (1 (p _i 910 ⁹ ) हैं।
    
    आउटपुट डेटा । न्यूनतम डी को ऐसे प्रिंट करें कि चिप्स के बीच बैटरी का वितरण हो ताकि प्रत्येक मशीन में चिप्स की आउटपुट शक्तियों में अंतर d से अधिक न हो।
    
    समस्या एफ का समाधान
    विश्लेषण के लेखक स्टेनिस्लाव पाक है।
    
    

    यह कार्य सबसे आसान में से एक है। 2 एनके से आपको बैटरी के प्रत्येक जोड़े (चलो उन्हें प्रतिनिधि कहते हैं) का चयन करने की आवश्यकता है, जिनमें से प्रत्येक
    इसकी चिप पर एक न्यूनतम शक्ति है, ताकि जोड़े में बैटरी की उत्पादन शक्ति में अधिकतम अंतर न्यूनतम हो। मान लीजिए कि डी तय हो गया है, तो हम पता लगा सकते हैं कि क्या ऐसे प्रतिनिधि हैं जो अधिकतम डी से अधिक नहीं है। हम शक्तियों को पी _{1 2} पी ₂ ... _k पी _{2 एनके सॉर्ट करते हैं} और हम लालच से जोड़े इकट्ठा करेंगे: बैटरी पी ₁ और पी ₂ पहली जोड़ी में गिर जाएगी। यदि पी ₂ - पी ₁ > डी , तो प्रतिनिधियों का चयन नहीं किया जा सकता है। दूसरी जोड़ी में हम बैटरी ले सकते हैं ( p _i2 , p _{i2 + 1} ) यदि d से अधिक का अंतर हो और न्यूनतम सूचकांक i 2 i 2 k + 1 हो, तो संभव है। इसी तरह, तीसरी जोड़ी में - ( p _i3 , p _{i3 + 1} ), i3 pair 4k + 1।
    
    यदि इस एल्गोरिथ्म का उपयोग करते हुए n जोड़े को जमा करना संभव नहीं है, तो ऐसा नहीं किया जा सकता है। इसका जवाब हम बाइनरी सर्च से खोजते हैं।

    
    
    

    टास्क जी मानचित्र टाइलें।

    
    यह एक ऐसा कार्य है जिसे आवंटित समय में कोई भी टीम सही ढंग से हल नहीं कर सकती है।
    
    कार्ड प्रिंट करना एक मुश्किल काम है। पहले आपको एक विमान पर गोलाकार पृथ्वी के नक्शे को फिट करने के लिए एक उपयुक्त परिवर्तन खोजने की आवश्यकता है, फिर यह पता चलता है कि उच्च-गुणवत्ता वाले मानचित्रों को मुद्रित करने के लिए आपको कागज की कई शीटों का उपयोग करने की आवश्यकता होती है, क्योंकि वे एक पर फिट नहीं होते हैं। इस कठिनाई को दूर करने के लिए, कार्ड प्रकाशकों ने कार्ड को कई आयताकार भागों में विभाजित किया और प्रत्येक भाग को अलग से प्रिंट किया। यह इस प्रक्रिया में है कि आप इस कार्य में भाग लेंगे।
    
    इंटरनेशनल एसोसिएशन ऑफ कार्ड पब्लिशर्स कार्ड प्रिंट करने के लिए उपयोग की जाने वाली व्यक्तिगत शीट की संख्या को कम करके कार्ड प्रिंटिंग लागत को कम करने की कोशिश कर रहा है। यहां तक ​​कि एक मानक शीट आकार और नक्शे के पैमाने के साथ, आप उनके लेआउट को समायोजित करके शीट की खपत को अनुकूलित कर सकते हैं।
    
    आकृति के बाईं ओर क्षेत्र को कवर करने वाली 14 चादरें दिखाई देती हैं। दायां भाग दिखाता है कि कैसे एक ही क्षेत्र को केवल 10 चादरों से कवर किया जा सकता है, क्षेत्र के उन्मुखीकरण को बदलने के बिना, चादरों का आकार और पैमाने।
    
    
    टेक्सास शीट बिछाने के लिए दो अलग-अलग तरीके
    
    आपका कार्य इंटरनेशनल एसोसिएशन ऑफ कार्ड पब्लिशर्स को दी गई क्षेत्र को कवर करने के लिए आवश्यक न्यूनतम संख्या में शीट खोजने में मदद करना है। सादगी के लिए, क्षेत्र स्वयं-चौराहों के बिना एक बंद बहुभुज है।
    
    ध्यान दें कि सभी शीट क्षैतिज और ऊर्ध्वाधर के समानांतर पक्षों के साथ एक सतत ग्रिड के हिस्से होने चाहिए। शीट को केवल उनके पक्षों द्वारा पूरी तरह से छुआ जा सकता है और घुमाया नहीं जा सकता है। इसके अलावा, हालांकि सभी दिए गए निर्देशांक पूर्णांक हैं, शीट गैर-पूर्णांक निर्देशांक में स्थित हो सकते हैं।
    
    बहुभुज चादरों के किनारों को छू सकता है (उदाहरण के लिए 2)। हालांकि, तर्कसंगत संख्याओं के मशीन प्रतिनिधित्व के साथ समस्याओं से बचने के लिए, यह माना जा सकता है कि बहुभुज के शीर्ष 10 ^-6 की दूरी पर शीट के बाहर होने पर उत्तर नहीं बदलेगा।
    
    इनपुट डेटा प्रविष्टि में एक परीक्षण होता है। परीक्षण की पहली पंक्ति में तीन नंबर n , x _s और y _{s हैं} । बहुभुज n (3 ≤ n , 50), x _s और y _s (1 s x _s , y _s ) 100) के कोने की संख्या - उन चादरों के आकार जिन्हें आप मानचित्र को कवर करना चाहते हैं। अगली एन लाइनों में से प्रत्येक में दो पूर्णांक x और y (0 ≤ x s 10 x _s , 0 y y that 10 y _s ) होते हैं जो बहुभुज के शीर्ष का वर्णन करते हैं (त्रैमासिक दिशा में, या तो दक्षिणावर्त या वामावर्त)।
    
    आउटपुट डेटा । बहुभुज को कवर करने के लिए आवश्यक शीट की न्यूनतम संख्या प्रिंट करें।
    
    समाधान जी
    विश्लेषण के लेखक फैज़टेक की टीम के हिस्से के रूप में एसीएम ICPC 2012 के स्वर्ण पदक विजेता याकोव डुलागच हैं।
    
    

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

    विकल्प पीढ़ी

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

    • बहुभुज के कोने में से एक ग्रिड लाइन पर पड़ता है;
    • बहुभुज के किनारों में से एक मेष नोड में चलता है।

    
    
    जब इन शर्तों में से एक को पूरा किया जाता है, तो बहुभुज में अभी भी कुछ हद तक स्वतंत्रता है:
    
    

    • यदि शीर्ष ग्रिड लाइन से टकराता है, तो आप इस लाइन के साथ बहुभुज को स्थानांतरित कर सकते हैं;
    • यदि एक धार एक जाल नोड से टकराती है, तो आप किनारे के साथ बहुभुज को स्थानांतरित कर सकते हैं।

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

    1. किसी एक कोने में लंबवत ग्रिड रेखा होती है, और एक कोने में क्षैतिज ग्रिड रेखा पर पड़ता है। इसमें वह मामला शामिल है जब एक शीर्ष एक ग्रिड नोड से टकराता है। यही है, जोर विशिष्ट रूप से एक जोड़ी कोने द्वारा परिभाषित किया गया है, कुल विकल्प - एन ² ।
    2. एक कोने में से एक क्षैतिज या ऊर्ध्वाधर ग्रिड लाइन पर पड़ता है। सामान्यता के नुकसान के बिना, हम मानते हैं कि यह ग्रिड लाइन ऊर्ध्वाधर है और समीकरण x = 0 द्वारा दी गई है।
       अब किनारों में से एक को, जो ऊर्ध्वाधर नहीं है, गाँठ मारो। एक शिफ्ट का चयन करने के लिए, यह नोड के एब्सिस्सा को चुनने के लिए पर्याप्त है, और यह एम + 1 से अधिक तरीकों से नहीं किया जा सकता है। मी के लिए, संख्या 10 इंगित की गई है। कुल विकल्प - एन ² ( एम + 1)।
    3. एक जाल नोड के खिलाफ दो गैर-समानांतर पसलियों को अलग करना। यहां, बहुभुज पारी को निर्धारित करने के लिए, किनारों के अलावा, उन ग्रिड नोड्स के बीच "अंतर" को ठीक करना आवश्यक है जिसमें ये किनारे आराम करते हैं। कुल - n ² ( m + 1) ² विकल्प।

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

    कब्जे वाली कोशिकाओं की गिनती

    
    इस कार्य में दूसरी कठिनाई थी एक दिए गए बदलाव से कब्जे वाली कोशिकाओं की संख्या की कुशलता से गणना करना। गिनती का भोली तरीका - ( एम + 1) ² कोशिकाओं के लिए एक बहुभुज के साथ चौराहे की जांच - ओ ( एम ² एन ) के लिए काम करता है और समय सीमा में फिट नहीं होता है। यह पता चला है कि प्रत्येक m + 1 कॉलम में व्याप्त कोशिकाओं की संख्या अधिक कुशल होगी। ऐसा करने के लिए, स्तंभ के माध्यम से गुजरने वाले बहुभुज की सीमा के निरंतर टुकड़ों पर विचार करें: या तो सीमा का एक टुकड़ा "क्रॉस" करता है (टुकड़े का एक छोर स्तंभ की दाईं सीमा पर है)
    और दूसरा छोर बाईं ओर है), या टुकड़े के दोनों छोर कॉलम की एक ही सीमा पर हैं। यह साबित किया जा सकता है कि पहले प्रकार के टुकड़ों को जोड़े में विभाजित किया गया है, और इन टुकड़ों के बीच सभी कोशिकाओं पर कब्जा कर लिया जाएगा। उसके बाद, प्राप्त कोशिकाओं के लिए आपको उन कोशिकाओं को जोड़ने की आवश्यकता होती है जिनके माध्यम से दूसरे प्रकार के टुकड़े गुजरते हैं। इस विधि को O ( m ( m + n )) = O ( mn ) में लागू किया जा सकता है।
    
    इस समस्या के लिए एल्गोरिथ्म की कुल जटिलता O ( n ³ m ³ ) है।

    
    
    

    समस्या एच। Matryoshka

    
    Matryoshka पारंपरिक रूसी लकड़ी की घटती हुई आकार का एक सेट है, जिसे एक दूसरे के अंदर रखा जाता है। आप अंदर से एक छोटा matryoshka प्राप्त करने के लिए matryoshka खोल सकते हैं, जो बदले में, matryoshka अंदर और इतने पर भी है।
    
    घोंसले के शिकार गुड़िया की एक प्रदर्शनी हाल ही में राष्ट्रीय घोंसले के संग्रहालय में आयोजित की गई थी, जिसमें गुड़िया के सेट में समान शैली लेकिन अलग-अलग संख्या में घोंसले के शिकार गुड़िया प्रस्तुत किए गए थे। दुर्भाग्य से, एक चंचल (और बिना बचे हुए) बच्चे ने सभी गुड़ियाओं को अलग कर दिया और सभी गुड़ियाओं को एक पंक्ति में डाल दिया।
    
    पंक्ति में नेस्टेड गुड़िया थीं, जिनमें से प्रत्येक का पूर्णांक आकार है। आपको सभी गुड़िया को सेट में फिर से इकट्ठा करने की आवश्यकता है, हालांकि आप या तो सेट की प्रारंभिक संख्या, या प्रत्येक सेट में गुड़िया की संख्या को नहीं जानते हैं। आप केवल यह जानते हैं कि प्रत्येक सेट में 1 से कुछ मीटर तक सभी क्रमिक आकारों की गुड़िया शामिल हैं, और एम अलग-अलग सेटों के लिए भिन्न हो सकते हैं।
    
    सेट करते समय, आपको निम्नलिखित नियमों द्वारा निर्देशित होना चाहिए:
    
    • आप गुड़िया को केवल बड़ी गुड़िया के अंदर रख सकते हैं;
    • यदि आप एक पंक्ति में एक दूसरे के बगल में खड़े हैं तो ही आप दो गुड़ियों को जोड़ सकते हैं;
    • नेस्टिंग डॉल को नेस्टिंग डॉल के सेट के अंदर रखने के बाद, इसे नेस्टिंग डॉल के दूसरे समूह में नहीं ले जाया जा सकता है या नेस्टिंग डॉल के समूह से अलग नहीं किया जा सकता है। घोंसले के शिकार गुड़िया के दो समूहों के संयोजन के दौरान इसे अस्थायी रूप से विभाजित करने की अनुमति है।
    
    आपका समय बहुत मूल्यवान है, इसलिए आप जितनी जल्दी हो सके सभी घोंसले बनाने वाली गुड़िया को समूहों में इकट्ठा करना चाहते हैं। प्रक्रिया का एकमात्र हिस्सा जो समय लेता है वह गुड़िया को खोलना और बंद करना है, इसलिए आप इस तरह के कार्यों की संख्या को कम करना चाहते हैं। उदाहरण के लिए, समूहों के संयोजन के लिए क्रियाओं की न्यूनतम संख्या [१,२,६] और [४] दो हैं, पहले आपको ६ और ४ के आकार की गुड़िया खोलने की जरूरत है। [१,२,५] और [३,४] समूहों को मिलाकर तीन खोजों की आवश्यकता है।
    
    एक प्रोग्राम लिखें जो घोंसले के शिकार गुड़िया के सभी सेटों को इकट्ठा करने के लिए आवश्यक खोजों की न्यूनतम संख्या की गणना करता है।
    
    इनपुट डेटा आपको एक परीक्षण दिया जाता है, जिसमें दो लाइनें होती हैं। पहली पंक्ति में एक नंबर n (1 line n ) 500) है - मूल पंक्ति में अलग-अलग गुड़िया की संख्या। दूसरी पंक्ति में एक पंक्ति में प्रत्येक गुड़िया के आकार का वर्णन करने वाली एन संख्याएं हैं। प्रत्येक गुड़िया का आकार कम से कम 1 है और 500 से अधिक नहीं है।
    
    आउटपुट डेटा । सभी सेट को इकट्ठा करने के लिए आवश्यक घोंसले के शिकार गुड़िया के उद्घाटन की न्यूनतम संख्या प्रिंट करें। यदि असेंबली संभव नहीं है (बच्चा अपने लिए कई गुड़िया उठा सकता है), असंभव शब्द को प्रिंट करें।
    
    समस्या एच का समाधान
    विश्लेषण के लेखक एलेक्सी रोपन हैं , जो बेलारूसी स्टेट यूनिवर्सिटी ऑफ इंफॉर्मेटिक्स एंड रेडियो इलेक्ट्रॉनिक्स की टीम के हिस्से के रूप में एसीएम ICPC 2012 के कांस्य पदक विजेता हैं।
    
    

    मान लीजिए कि एफ _i का मूल्य नेस्टेड गुड़िया के उद्घाटन की न्यूनतम संख्या है जो समूहों में पहले i घोंसले के शिकार गुड़िया को तोड़ने के लिए आवश्यक है। फिर F ₀ = 0 और F _i = min 0 _{0j <i} F _j + G _{j + 1, i} , जहाँ G _{l , r} का मान न्यूनतम खोज है जिन्हें गुड़िया से l को r समावेशी बनाने के लिए गुड़िया बनाने की आवश्यकता है एक (प्रत्येक इकाई में घोंसले के शिकार गुड़िया की संख्या), और j + 1 से i समावेशी के अंतराल पर, घोंसले के शिकार गुड़िया के सभी आकार अलग-अलग होते हैं और i - j से अधिक नहीं होते हैं । तब समस्या का उत्तर F _{n होगा} , और समाधान की जटिलता को ध्यान में रखे बिना G के मूल्यों की गणना O ( n ² ) होगी। जी _{i , i के लिए,} मान हमेशा 0 होता है, और G _{i , j} और i <j के लिए, अंतिम चरण में, रूसी गुड़िया के दो समूह संयुक्त होते हैं। आज्ञा देना k की संख्या रूसी गुड़िया है जिस पर बाएं समूह समाप्त होता है। फिर G _{i , j} = min _{i≤k <j} G _{i , k} + G _{k + 1, j} + C _{i , k , j} , जहां value C _{i , k , j} न्यूनतम संख्या में गुड़िया के खुलने की आवश्यकता है नेस्टेड गुड़िया के समूहों को i- th से k- th और c k + 1-th से j- th में संयोजित करना । मान M _{i , j ,} i से j तक अंतराल में नेस्टेड गुड़िया का न्यूनतम आकार है और K _{i , j ,} के अंतराल में नेस्टेड गुड़िया की संख्या i से j हो जाती है, जिनका आकार s से कम है। तब C _{i , k , j की} गणना j - i + 1 - t के रूप में की जा सकती है , जहाँ t गुड़िया की संख्या है, जिसे संयुक्त करने पर, खोला नहीं जाएगा, अर्थात t = K _{k + 1, j, M i, j} + K _{i , j , M k + 1, j} (कोई यह नोटिस कर सकता है कि कोई एक शब्द हमेशा शून्य होगा)। कंप्यूटिंग कश्मीर और जी की जटिलता है ।

    
    
    

    समस्या I. समुद्री डाकू छाती

    
    समुद्री डाकू जैक खुले समुद्र में लड़ाई और लूटपाट, चोरी और सभी के उत्पीड़न और सब कुछ के थक गया है। उसने संन्यास लेने का फैसला किया, और यहां तक ​​कि समुद्र में सही निर्जन द्वीप पाया, जिस पर वह अपना शेष जीवन गरिमा के साथ बिताएगा, जब तक कि वह पैसे से बाहर नहीं निकलता। अब उसके पास बहुत सारे सोने के सिक्के हैं जो वह एक छाती में डालना चाहता है (वह अंत में एक समुद्री डाकू है!)। जैक एक छाती का निर्माण कर सकता है जो एक आयताकार समान आकार का होता है जो पूर्णांक पक्षों के साथ होता है और छाती के नीचे के निर्दिष्ट आकार से अधिक नहीं होता है। यह केवल खजाना सीने को छिपाने के लिए खोजने के लिए बनी हुई है।
    
    जैक ने एक छायादार तालाब में छाती को बाढ़ने का फैसला किया। तालाब की सतह पूर्वनिर्धारित पक्षों के साथ एक आयत है, तालाब ऊर्ध्वाधर पत्थर के किनारों से सभी तरफ से घिरा हुआ है। जैक ने तालाब के तल की जांच की और तालाब की गहराई के बारे में प्रत्येक स्थान पर तालाब के प्रत्येक 1x1 वर्ग (कार्टेशियन समन्वय प्रणाली में) के बारे में जाना। जब जैक छाती को डुबोता है, तो बाद वाला अधिकतम संभव गहराई तक डूब जाएगा जब तक कि वह कम से कम एक वर्ग के साथ नीचे नहीं छूता। छाती में जकड़न के कारण, तालाब में पानी का स्तर बढ़ जाएगा। तालाब के किनारे काफी ऊंचे हैं, ताकि पानी कभी भी अपनी सीमा से बाहर न फैले। बेशक, चूंकि छाती को छिपाने की जरूरत है, यह तालाब में पानी के स्तर से पूरी तरह नीचे होना चाहिए। आपका कार्य छाती की अधिकतम मात्रा का पता लगाना है जो तालाब में छिपा हो सकता है।
    
    बाईं ओर का आंकड़ा बिना छाती वाला एक तालाब दिखाता है, केंद्र में - एक तालाब जिसमें वॉल्यूम 3 की छाती होती है, दाईं ओर - तालाब में वॉल्यूम 4 (अधिकतम संभव) की एक छाती। कृपया ध्यान दें कि यदि केंद्रीय आकृति से छाती अधिक ऊंचाई की एक इकाई पर बनाई गई थी, तो इसका शीर्ष तालाब की सतह पर बिल्कुल दिखाई देगा।
    
    
    
    इनपुट डेटा इनपुट में एक परीक्षण शामिल है। परीक्षण चार पूर्णांक a , b , m , n (1 , a, b, m, n । 500) वाली रेखा से शुरू होता है। तालाब की सतह का आकार m x n है , छाती के नीचे का अधिकतम आकार x b है । इसके अलावा, ए और बी पर्याप्त हैं; छाती कभी भी पूरे तालाब को पूरी तरह से कवर नहीं करेगी। शेष मी एंट्री लाइनों में से प्रत्येक में n नंबर d _{ij होता है} जो निर्देशांक (i, j) के साथ तालाब की गहराई का वर्णन करता है, जहाँ किसी भी 1j i ⁹ m , 1≤ j । N के लिए ⁰ ) d _ij ⁹ 10 ⁹ ।
    
    आउटपुट डेटा । पूर्णांक पक्षों के साथ छाती की अधिकतम मात्रा को प्रिंट करें जो पानी की सतह के नीचे एक तालाब में छिपा हो सकता है, जिसमें से एक नीचे के माप से अधिक होता है और दूसरा ख से अधिक नहीं। यदि पानी के नीचे कोई छाती नहीं छिपाई जा सकती है, तो 0 प्रिंट करें।
    
    समाधान I
    विश्लेषण के लेखक वसीली अस्ताखोव हैं।
    
    

    , h · w , d , , S — . , h · w, , d . . ( ( a,b )) , .
    
    . , x ₀ x ₁ ( x ₀ < x ₁ , x ₁ - x ₀ ≤ b ) . , , x ₀ x ₁ . ( n ³ ). , w = x ₁ - x ₀ ≤ a , yb , y a . : ( h ), . . y . , , .
    
    ( ), . , ≥ . , . , O( n ² · m · log m ), log .

    
    
    

    J. Pollution Solution

    
    , , ( , ) , . — , , .
    
    
    
    , , . ( ) x , (0, 0).
    , . , , - .
    
    . . , n r , 3 ≤ n ≤ 100 — , 1 ≤ r ≤ 1000 — . n , x _i y _i — , −1500 ≤ x _i ≤ 1500 0 ≤ y _i ≤ 1500. . .
    
    . , r . 10 ⁻³ .
    
    J
    — , ACM ICPC 2012 .
    
    

    : , .
    
    ( , ). O — , n P ₁ , P ₂ , …, P _n , n - ( x _i , y _i ). , P _{n +1} = P ₁ .
    
    ।
    
    S ( O P _i P _{i +1} ) — O , P _i P _{i +1} :
    
    ।
    
    , :
    
    
    
    n , «» , , , ( ).
    
    
    
    . , , , . : O P _i P _{i +1} , , .
    
    
    
    ? P _i P _{i +1} . .
    
    

    • t P _i + (1 − t ) P _{i +1} t [0, 1] ( ). t , .
    • .

    
    
    , ( P ₁ P ₂ P ₃ P ₄ ), ( P ₅ P ₁ ) ( P ₂ P ₃ P ₄ P ₅ ).
    
    O P _i P _{i +1} (, O P ₅ P ₁ ). ( ), , . .
    
    , ।

    
    
    

    K. Up a Tree

    
    — . . . , post, pre in pre- output, , output . , .
    
    .
    

     void prePrint(TNode t) { output(t.value); if (t.left != null) prePrint(t.left); if (t.right != null) prePrint(t.right); } void inPrint(TNode t) { if (t.left != null) prePrint(t.left); output(t.value); if (t.right != null) prePrint(t.right); } void postPrint(TNode t) { if (t.left != null) prePrint(t.left); if (t.right != null) prePrint(t.right); output(t.value); } 

    
    
    — ! , , , . , , .
    
    . , , . , , , . :
    
    
    • , , inPrint ;
    • 6 inPrint, prePrint postPrint, , .
    
    , . . , .
    
    . , — prePrint, inPrint postPrint. n (4 ≤ n ≤ 26), .
    
    . 6 {Pre, In, Post} — prePrint , inPrint , , postPrint. , prePrint, inPrint, postPrint , , prePrint , , , inPrint .
    
    K
    — , ACM ICPC 2007 . एमवी .
    
    

    . 90. . . S ( f ₁ , f ₂ , f ₃ , s ₁ , s ₂ , s ₃ , l ) — , , f _i , i - , s _i l , — , — .
    
    , O( n ² ).
    
    3 ³ n ⁴ , , 3 ³ n ² , n ≤ 26 .
    
    

    
    
    , ACM ICPC 2013, . , , Per Austrin ( ). , ICPC. .