रूसी कोड कप 2013 - क्वालीफाइंग दौर के कार्यों का विश्लेषण

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

फाइनल तक पहुंचने की लड़ाई आसान नहीं थी, लेकिन निष्पक्ष: दौर के दौरान एक भी कॉपीराइटर की पहचान नहीं की गई।
कट के तहत - विजेताओं पर आंकड़े और क्वालीफाइंग दौर के कार्यों का विस्तृत विश्लेषण:

• टास्क ए: टू टावर्स
• टास्क बी: जमा
• टास्क सी: केपलर
• टास्क डी: टेस्ट
• टास्क ई: लेजर
• टास्क एफ: व्हील

दौर के दौरान, 439 लोगों ने लॉग इन किया, जिनमें से कम से कम एक निर्णय 371 प्रतिभागियों द्वारा भेजा गया था। कुल 3334 समाधान भेजे गए थे।

प्रतिभागी जो पहले इसी कार्यों के समाधान भेजने के लिए थे, और दौर की शुरुआत के बाद का समय (मिनट: सेकंड):

• टास्क ए: रेवमैन (9:12)
• समस्या B: ant.ermilov (16:58)
• टास्क सी: ज़ूकोव_मिट्री (5:52)
• टास्क डी: ई-मैक्स (33:05)
• टास्क ई: विंगर (37:50)
• टास्क एफ: पर्यटक (82:51)

इस दौर में प्रतिभागियों का क्षेत्रीय वितरण निम्नानुसार था:

रूस => 183
यूक्रेन => 53
बेलारूस => 23
संयुक्त राज्य अमेरिका => 18
कजाकिस्तान => ५
जर्मनी => ४
स्विट्जरलैंड => ३
लातविया => २
आर्मेनिया => 2
बुल्गारिया => १
आइसलैंड => 1
हंगरी => 1
उज्बेकिस्तान => १
जॉर्जिया => १
स्पेन => १
लिथुआनिया => १
यूके => 1
आस्ट्रिया => १
साइप्रस => १
पोलैंड => 1

केवल तीसरे घंटे के अंत में विजेताओं की सूची की तस्वीर आकार लेने लगती है। फाइनल में 50 लोग पहुंचे। उनमें से पहले 10:

1. व्लादिस्लाव इसेनबाव
2. गेनेडी कोरोटकेविच
3. दिमित्री धज़ुलगाकोव
4. पीटर मिट्रिक
5. व्लादिस्लाव एपिफ़ानोव
6. आरतोम राखोव
7. माइकल केवर
8. दिमित्री गोज़मैन
9. दिमित्री झुकोव
10. एवगेनी कपुन

और अंत में, चलो कार्यों के विश्लेषण पर सीधे चलते हैं।

टास्क ए दो टावर
विचार: फेडोर Tsarev
एहसास: पावेल क्रोटकोव, एंड्रे स्टानकेविच
विश्लेषण: पावेल क्रोटकोव

टास्क की स्थिति

समय सीमा: 2 सेकंड
मेमोरी सीमा: 256 मेगाबाइट

Mail.World ने हाल ही में एक नए कार्यालय में स्थानांतरित किया है जो 10 ⁹ मंजिलों के साथ दो गगनचुंबी इमारतों की तरह दिखता है। कुछ मंजिलों पर, टावरों को संक्रमण द्वारा जोड़ा जाता है, जिसके माध्यम से आप एक से दूसरे में जा सकते हैं। कुल में n संक्रमण हैं, वे टावरों को फर्श ₁ , ₂ , ..., _n पर जोड़ते हैं

Artyom L _1st फ्लोर पर टॉवर b ₁ में काम करता है। आज उसे अपने सहयोगी दिमित्री के साथ बात करने की ज़रूरत है, जो एल ₂ मंजिल पर बी ₂ टॉवर में काम करता है। अजीब तरह से, यह पता चला कि आर्टेम के कार्य केंद्र से दिमित्री के कार्य केंद्र तक पहुंचने का सबसे तेज़ तरीका चुनना इतना आसान नहीं है।

प्रत्येक टॉवर में एक लिफ्ट है। टॉवर 1 में लिफ्ट यू ₁ सेकंड में एक मंजिल गुजरती है, और टॉवर 2 में लिफ्ट - यू ₂ सेकंड में। एर्टोम टावरों के बीच के रास्ते पर टी सेकंड खर्च करता है।

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

पहले उदाहरण में, एर्टोम को बस पहले टॉवर के लिफ्ट को लेने की आवश्यकता है।

दूसरे उदाहरण में, दूसरे टॉवर में लिफ्ट बहुत तेज चलती है, और आर्टेम के लिए दूसरे टॉवर में संक्रमण के लिए जाना अधिक लाभदायक है, लिफ्ट को 10 वीं मंजिल पर ले जाएं, पहले टॉवर पर लौटें और पहले टॉवर में लिफ्ट द्वारा दूसरी मंजिल पर जाएं।

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

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

पहली पंक्ति में n शामिल है - टावरों के बीच संक्रमण की संख्या (1 ≤ n contains 10 ⁵ )। दूसरी पंक्ति में n भिन्न पूर्णांक ₁ , ₂ , ..., a (1 ≤ a ₁ <a ₂ <... <a _n ≤ 10 ⁹ ) है। अगली पंक्ति में तीन सकारात्मक पूर्णांक हैं: u ₁ , u ₂ और t (उनमें से प्रत्येक 1 से 10 ⁹ की सीमा में है)। अंत में, निम्नलिखित दो पंक्तियों में दो संख्याएँ होती हैं: बी ₁ , एल ₁ और बी ₂ , एल ₂ , क्रमशः (बी ₁ और बी _{2 में} से प्रत्येक 1 या 2, 1 1 एल ₁ , एल ₂ ≤ 10 ⁹ ) है।
इनपुट डेटा में सभी परीक्षण मामलों में संक्रमण की कुल संख्या 10 ⁶ से अधिक नहीं है।

आउटपुट स्वरूप

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

उदाहरण

इनपुट डेटा	उत्पादन
2 1 5 ३ ३ २ १ १ १ १० 2 १ १० ५ ३ २ १ १ १ ११	27 36

टास्क पार्सिंग

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

हम उन मंजिलों से एक ग्राफ बनाएंगे जिनमें हम रुचि रखते हैं। हम निम्नलिखित मंजिलों को दिलचस्प मानेंगे:

• जिस मंजिल पर आर्टेम काम करता है, उस टॉवर में जहां आर्टेम काम करता है
• जिस मंजिल पर दिमित्री काम करती है, उस टॉवर में दिमित्री काम करती है
• फर्श जो Artyom के निकटतम संक्रमण के सिरे हैं (कुल में हमें संक्रमण से 2 कोने मिलते हैं, जो उच्चतर है, और संक्रमण से 2 कोने हैं, जो कम है)
• पिछले पैराग्राफ के समान 4 कोने जोड़ें, लेकिन केवल दिमित्री के लिए

हमारे ग्राफ में दो प्रकार के किनारे हैं:

• उन चोटियों को जोड़ने वाली पसलियां जिनके बीच संक्रमण होता है। ऐसे किनारों का वजन t है
• एक टावर से चोटियों को जोड़ने वाली पसलियां। इस तरह की पसलियों का वजन संबंधित तलों के बीच की दूरी के बराबर होता है, जो औसत टॉवर में एलेवेटर की गति से गुणा होती है

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

टास्क B. जमा
विचार: बोरिस मिनाएव
बोध: विटालि दुमंजुक
विश्लेषण: विटाली डमींजुक

टास्क की स्थिति

समय सीमा: 2 सेकंड
मेमोरी सीमा: 256 मेगाबाइट

कई वर्षों के काम के अनुभव के लिए, वासिली इवानोविच ने कश्मीर रूबल कमाया। अब वासिली इवानोविच सेवानिवृत्त हो गए हैं और इस धन को अगले कुछ वर्षों के लिए जमा करना चाहते हैं। उसके गृहनगर में n बैंक हैं। यदि वसली इवानोविच के बैंक खाते के नंबर i में jth वर्ष के दौरान पैसा है, तो वर्ष के अंत में इस खाते में उनकी राशि p _{i, j} प्रतिशत से बढ़ जाएगी।

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

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

इस वर्ष के अंत में वासिली इवानोविच के सभी खातों पर रूबल की अधिकतम संख्या का पता लगाएं।

उदाहरण में, वासिली इवानोविच पहले दूसरे बैंक को पैसा देता है। पहले वर्ष के बाद उसके पास 115 रूबल हैं, वह पुनर्वितरण के लिए दोनों बैंकों को चुनता है। 2 रूबल के कमीशन का भुगतान करने के बाद, वह पहले बैंक में सभी पैसे डालता है। वर्ष के अंत में, उनके बैंक खाते में 113 × 1.15 = 129.95 रूबल थे।

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

पहली पंक्ति में एक धनात्मक पूर्णांक t - परीक्षण की संख्या है। (1 ≤ t ≤ 50)

प्रत्येक परीक्षण का वर्णन क्रमशः तीन पूर्णांकों n, m और k - एक पंक्ति के साथ शुरू होता है, जो बैंकों, वर्षों और अर्जित किए गए रूबल की संख्या। (1 ≤ n, 10000, 1 ≤ m 1 20, 1 ≤ k ⁹ 10 ⁹ ) अगली पंक्ति में n पूर्णांक होते हैं, जहाँ i-th संख्या एक _{i है} - i-th बैंक का कमीशन (1 _{i i i} ≤ 10 ⁹⁾ )। अगली एन लाइनों में से प्रत्येक में एम पूर्णांक हैं। I-th लाइन में, j-th नंबर p _{i, j} है, जो Vasli Ivanovich द्वारा प्राप्त किए गए अतिरिक्त पैसे का प्रतिशत j-th वर्ष में i-th बैंक (0 _i p _{i, j} account 100) के खाते में होता है।

सभी परीक्षणों में बैंकों की कुल संख्या 50,000 से अधिक नहीं है।

आउटपुट स्वरूप

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

उदाहरण

इनपुट डेटा	उत्पादन
1 २ २ १०० १ १ १० १५ १५ १०	129.95

टास्क पार्सिंग

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

इस तथ्य को ध्यान में रखते हुए, यह साबित हुआ कि समस्या को गतिशील प्रोग्रामिंग की विधि द्वारा हल किया गया है। Dp _{i, j} मैं वर्षों बाद वासिली इवानोविच के खातों में अधिकतम संख्या में रूबल के बराबर हो, अगर i-year के दौरान उसका सारा पैसा j-th बैंक में था। हम सभी बैंकों के माध्यम से सॉर्ट करते हैं, जहां पिछले वर्ष में पैसा जमा किया जा सकता था, फिर dp _{i, j} = (max (dp _{i-1, k-a k} ) - a _j ) • p _{j, i} से 1 k से n तक सभी।

हम अलग से मामले पर विचार करते हैं जब j = k, तब dp _{i, j} = max (dp _{i, j} , dp _{i, j-1} • p _{j, i} )। इसका उत्तर सभी d के लिए अधिकतम dp _{m, k} के बराबर है। परिणामस्वरूप, पहली नज़र में, समाधान O (n2m) के लिए काम करता है। हालांकि, ध्यान दें कि dp _{i-1, k} - a _, j पर निर्भर नहीं करता है। इसलिए, यदि सभी के लिए हम अधिकतम (dp _{i-1, k} - a _k ) का समर्थन करते हैं, तो हम O ( _n ) में एक समाधान प्राप्त करते हैं।

समस्या सी। केप्लर
विचार: विटाली अक्षोनोव
कार्यान्वयन: एंड्री कोमारोव
विश्लेषण: एंड्री कोमारोव

टास्क की स्थिति

समय सीमा: 2 सेकंड
मेमोरी सीमा: 256 मेगाबाइट

दूसरे जाइरोस्कोप की विफलता के बाद, केपलर खगोलीय दूरबीन आगे के संचालन के लिए अनुपयुक्त हो गई। नासा ने इस नुकसान को ठीक करने और एक अन्य दूरबीन को अंतरिक्ष में लॉन्च करने का फैसला किया। बिजली के साथ दूरबीन प्रदान करने के लिए, सौर पैनलों का उपयोग करने का निर्णय लिया गया था। सौर पैनल के लिए रिक्त आकार में एक आयताकार पैनल n × m है, जिसमें 1 × 1 कोशिकाएं होती हैं।

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

ऐसा करने के लिए, वे निम्नानुसार बैटरी के लिए एक रिक्त के साथ आते हैं: यदि वर्तमान रिक्त के किनारों में से एक की लंबाई समान है, तो आप रिक्त को इसके साथ आधा में मोड़ सकते हैं; पैनल का आकार आधा है (पैनल की मोटाई की उपेक्षा की जा सकती है)। यदि पक्षों में से एक की लंबाई विषम है (पैनल का आकार (2n + 1) × m) है, तो वे समय-समय पर अल्ट्रा-सटीक लेजर के साथ इसमें से 1 × m आकार का एक टुकड़ा काट सकते हैं और फिर उन्हें 2n लंबे एक तरफ आधे हिस्से में मोड़ सकते हैं। पैनल के कट ऑफ पीस को फेंक दिया जाता है। नतीजतन, वैज्ञानिकों को 1 × 1 पैनल मिलता है जो कक्षा में उड़ जाएगा और वहां विस्तार करेगा।

सभी फोल्डिंग की तुलना में लेजर बहुत लंबे समय तक काम करता है। उन्हें इस तरह से 1 × 1 वर्ग में मूल वर्कपीस को मोड़ने के लिए कम से कम लेजर समय निर्धारित करने में मदद करें।

कृपया ध्यान दें कि पैनल की तैनाती के परिणामस्वरूप होने वाली बैटरी का आकार कोई फर्क नहीं पड़ता है, लेजर ऑपरेटिंग समय को कम करना आवश्यक है।

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

पहली पंक्ति में एक पूर्णांक t (1 ≤ t) 1000) - परीक्षण प्रश्नों की संख्या है। अगली टी लाइनों में स्वयं प्रश्न होते हैं। प्रत्येक अनुरोध में दो पूर्णांक n और m (1 m n, m) 10 ⁹ ) होते हैं - सौर बैटरी के लिए रिक्त का प्रारंभिक आकार।

आउटपुट स्वरूप

प्रत्येक अनुरोध के लिए एक नंबर प्रिंट करें - सबसे कम लेजर समय जो वैज्ञानिक प्राप्त कर सकते हैं।

उदाहरण

इनपुट डेटा	उत्पादन
3 १ १ ४ ४ ३ २	0 0 1

टास्क पार्सिंग

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

• लंबाई n के किनारे जोड़ें। इस मामले में, नई लंबाई /n / 2 the है
• लंबाई एम के किनारे मोड़ो। इस स्थिति में, लंबाई नहीं बदलती है और n के बराबर बनी रहती है

इसलिए, एक पक्ष में केवल लंबाई n, an / 2⌊⌊, /n / 2 side / 2⌋, ..., 1. केवल N = 2log ₂ n⌋ + 1 हो सकते हैं। दूसरे पक्ष के लिए समान विचारों को उठाते हुए, हम पाते हैं कि इसकी लंबाई M = ⌊log ₂ m⌋ + 1 मान ले सकती है।

समस्या को हल करने के लिए, हम गतिशील प्रोग्रामिंग के विचार का उपयोग करते हैं। एक _i , i∈ [1..N] की लंबाई, जो कि पहले पक्ष की हो सकती है, को अवरोही क्रम में क्रमबद्ध किया गया। इसी तरह बी _{आई के लिए} ।

हम निम्नलिखित मूल्य की गणना करते हैं: dp [i, j] = "सबसे छोटा समय जिसमें n × m पैनल से _i × b _j पैनल मिलना संभव है"। फिर, चूंकि और बी को घटते क्रम में आदेश दिया जाता है, एक _एन = 1, बी _एम = 1, जिसका अर्थ है कि समस्या का उत्तर डीपी [एन, एम] है। dp [i, j] की गणना नियमों के अनुसार की जा सकती है:

1. dp [i, j] = j
2. dp [i, j] = min (dp [i, j], dp [i-१, j] + ((ai-1 mod 2) • bj) अगर i> १
3. dp [i, j] = min (dp [i, j], dp [i, j-1] + ((bj-1 mod 2) • ai) अगर j> 1
4. dp [१, १] = ०

टेस्ट डी। टेस्ट
विचार: आर्टेम वासिलिव
कार्यान्वयन: आर्टेम वासिलिव
विश्लेषण: आर्टीम वासिलिव

टास्क की स्थिति

समय सीमा: 2 सेकंड
मेमोरी सीमा: 256 मेगाबाइट

एर्टोम इलेक्ट्रॉनिक प्रणाली में एक प्रशिक्षण परीक्षा पास करता है। परीक्षण प्रश्न में n कथन होते हैं, जिनमें से कुछ सत्य हैं और उन्हें जांचना आवश्यक है। कुछ चेकबॉक्स की जांच करके, आप शुद्धता के लिए उत्तर की जांच कर सकते हैं। यदि सभी सच्चे बयानों की जाँच की जाती है, और सभी झूठे कथन नहीं हैं, तो प्रश्न का उत्तर सही माना जाता है।

Artyom सोचने में बहुत आलसी है, इसलिए उसने झंडे लगाने के सभी विकल्पों को बस हल करने का फैसला किया। ऐसा करने के लिए, वह अपनी व्यवस्था के सभी 2 ^एन वेरिएंट की सूची तैयार करता है। सूची में, झंडे लगाने का प्रत्येक विकल्प ठीक एक बार मौजूद होना चाहिए।

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

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

पहली पंक्ति में एक पूर्णांक n (1 ≤ n। 16) होता है।

आउटपुट स्वरूप

2 ^एन लाइनों को प्रिंट करें। I-th लाइन प्रिंट n वर्णों में 0 या 1 - i-th उत्तर विकल्प के लिए प्रत्येक झंडे की स्थिति, चेक बॉक्स के लिए 1 और अपरिभाषित के लिए 0। विकल्पों में इकाइयों की संख्या में वृद्धि नहीं होनी चाहिए। पदों की संख्या जिसमें दो आसन्न रेखाएं प्रतिष्ठित हैं, दो से अधिक नहीं होनी चाहिए।

उदाहरण

इनपुट डेटा	उत्पादन
2	11 10 01 00

टास्क पार्सिंग

इस समस्या में, लंबाई के 0 और 1 से सभी पंक्तियों को सूचीबद्ध करना आवश्यक था ताकि दो गुण संतुष्ट हों: सबसे पहले, इकाइयों की संख्या घटती नहीं है, और दूसरी बात, दो आसन्न पंक्तियाँ दो से अधिक पदों में भिन्न होती हैं।

हम एक हल (n, k) प्रक्रिया लिखते हैं जो लंबाई n के सभी बिट स्ट्रिंग्स की एक सूची देता है जो हमारी संपत्ति को संतुष्ट करता है। प्रत्येक पंक्ति में बिल्कुल k इकाइयाँ होती हैं। हम हल के लिए एक पुनरावर्ती एल्गोरिदम का वर्णन करते हैं (n, k):

1. यदि k 0 या n है, तो एक पंक्ति 0 ⁿ या 1 ⁿ से एक सूची लौटाएं
2. अन्यथा, हम पुनरावर्ती हल (n - 1, k) कहते हैं और हल करते हैं (n - 1, k - 1)
3. पहली सूची से अंत तक हम सभी बिट स्ट्रिंग्स को 0 पर असाइन करते हैं, दूसरी सूची से सभी तत्वों को हम अंत 1 पर असाइन करते हैं
4. पहली सूची का विस्तार और दूसरे का विस्तार

अब इसका समाधान सूची के हल (n, k) से सभी k के लिए n से 0 तक के सभी बिट स्ट्रिंग्स को निकालना है। आइए हम इस समाधान की शुद्धता को साबित करें। सूची के गुणों पर विचार करें कि समाधान प्रक्रिया वापस आती है।

1. सूची हल करने का पहला तत्व (n, k) 1 ^k 0 ^{n - k है}
2. यदि k> 0, तो सूची हल करने का अंतिम तत्व (n, k) 1 ^{k - 1} 0 ^{n - k} 1 है
3. यदि k = 0 है, तो सूची हल करने का अंतिम तत्व (n, k) 0 ^{n है}

प्रेरण द्वारा इन सभी गुणों को साबित करना आसान है। नतीजतन, हमें पता चलता है कि समाधान (एन, के) प्रक्रिया वास्तव में सही ढंग से काम करती है। यह सत्यापित करना शेष है कि हल का अंतिम तत्व (n, k + 1) और हल का पहला तत्व (n, k) दो से अधिक स्थिति में भिन्न नहीं है। हल का अंतिम तत्व (n, k + 1): 1 ^k 0 ^{n - k - 1} 1, हल का पहला तत्व (n, k): 1 ^k 0 ^{n - k} । यह देखना आसान है कि संपत्ति भी इन दो लाइनों के लिए रखती है। इस प्रकार, हमने एक एल्गोरिथ्म प्राप्त किया है जो लंबाई n के सभी बिट तारों को शामिल करता है और आवश्यक गुणों को संतुष्ट करता है।

टास्क ई लेज़रों
विचार: अन्ना मालोवा
कार्यान्वयन: आर्टेम वासिलिव
विश्लेषण: आर्टीम वासिलिव

टास्क की स्थिति

समय सीमा: 2 सेकंड
मेमोरी सीमा: 256 मेगाबाइट

लेजर प्रयोगशाला के वैज्ञानिक एक नए तरह के लेजर का परीक्षण कर रहे हैं। ऐसा करने के लिए, वे एक विशेष प्रयोगशाला तालिका का उपयोग करते हैं, जिस पर एन अटैचमेंट पॉइंट होते हैं।

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

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

वैज्ञानिक यह जानना चाहते हैं कि नियोजित प्रयोग को किस न्यूनतम वोल्टेज पर महसूस किया जा सकता है।

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

पहली पंक्ति में एक पूर्णांक n (2 ≤ n) 150) है - प्रयोगशाला बेंच पर लगाव बिंदुओं की संख्या। अगली n लाइनों में दो पूर्णांक xi, yi - i-th बिंदु के निर्देशांक हैं। ((20000 _i x _i , y _i for 20000 सभी के लिए 1 से n तक, सभी बिंदु अलग हैं)। पहला बिंदु लेजर से मेल खाता है, बाकी सभी रेफ्रेक्टर्स के लिए।

आउटपुट स्वरूप

एक वास्तविक संख्या प्रिंट करें - न्यूनतम वोल्टेज जिसे आपको अपवर्तक को लागू करने की आवश्यकता है। उत्तर की पूर्ण या सापेक्ष त्रुटि 10 ^-8 से अधिक नहीं होनी चाहिए।

उदाहरण

इनपुट डेटा	उत्पादन
4 ० ० ० १ १ १ १ ०	90.0

टास्क पार्सिंग

समाधान का मुख्य विचार उत्तर में एक द्विआधारी खोज है। हम अधिकतम विक्षेपण कोण α को ठीक करते हैं और इस तरह के उत्तर के साथ समाधान के अस्तित्व की जांच करते हैं। ऐसा करने के लिए, हम ग्राफ़ में एक रास्ता खोजने के लिए समस्या को कम करते हैं।

स्थिति में परिभाषित बिंदुओं को P ₁ , P ₂ , ..., P _{n के} रूप में निरूपित करें। हम n (n - 1) कोने का एक ग्राफ बनाते हैं, जहां प्रत्येक शीर्ष पर विभिन्न बिंदुओं का एक जोड़ा जोड़ा होता है। जोड़े से किनारों (i, j) को जोड़े (j, k) से खींचे यदि वैक्टर P _i P _j और P _j P _{k के} बीच का कोण α से अधिक न हो। निर्मित ग्राफ़ में n ³ से अधिक किनारे नहीं हैं। अब, यदि इस तरह के ग्राफ में फॉर्म (1, i) के शीर्ष से फार्म (j, 1) के शीर्ष तक एक पथ मौजूद है, तो ऐसे α के साथ प्रयोग किया जा सकता है। आप ग्राफ़ में पथ खोजने के लिए किसी भी एल्गोरिथ्म का उपयोग करके पथ के अस्तित्व को सत्यापित कर सकते हैं।

इस प्रकार, द्विआधारी खोज का एक पुनरावृत्ति O (n ³ ) के लिए काम करता है, जिसका अर्थ है कि पूरे एल्गोरिथ्म को O (n ³ log (1 / ε)) में लागू किया जा सकता है या, यदि आप देखते हैं कि खोज स्थान वास्तव में असतत है (हम केवल रुचि रखते हैं) n ³ कोणों से अधिक नहीं), फिर इस एल्गोरिथ्म को O (n ³ log (n ³ )) में लागू किया जा सकता है।

समस्या एफ व्हील
विचार: बोरिस मिनाएव
कार्यान्वयन: बोरिस मिनाएव
विश्लेषण: बोरिस मिनाएव।

टास्क की स्थिति

समय सीमा: 2 सेकंड
मेमोरी सीमा: 256 मेगाबाइट

इस समस्या के कारण देश में सड़कों की एक दिलचस्प प्रणाली है। इस देश में कुल मिलाकर n + 1 शहर राजधानी और n सामान्य शहर हैं। सभी सामान्य शहर एक सर्कल पर स्थित हैं जिसका केंद्र राजधानी में है। सभी पड़ोसी सामान्य शहरों के बीच की दूरी समान है। प्रत्येक शहर अपने दो पड़ोसियों, साथ ही साथ राजधानी के साथ सड़कों से जुड़ा हुआ है। , n-, .

, . ! . . ( ) . , . . , , , .

, . , . !

, . ( ) . 1/8 . 4. 3/8 — . 2. , 1/2 , — . 3. 4×1/8+2×3/8+3×1/2=2.75.

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

t — . t n (3 ≤ n ≤ 500) — . , 1000.

आउटपुट स्वरूप

— , . , 10 ^-9 .

इनपुट डेटा	उत्पादन
2 3 4	2.75 3.4375

टास्क पार्सिंग

. , . . 0, , 1 . n. . — ( + 1) ( , ). , : – .

, . :

, , . O(n ⁵ ).

, . , , . . . , . . . , ( , + 1) . , n — 1, , ( , + 1). , , , . , O(n ⁴ ).

, . , . , , (n + 2) / 2. , n = 150 10 ^-12 . , n .

, . O(n ⁴ ) 150 n. n (n + 2) / 2.

Russian Code Cup। अगला चरण अंतिम है; हम निश्चित रूप से इसके बारे में हैबे पर बताएंगे।