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

पिछले रविवार को, रूसी कोड कप का तीसरा, अंतिम क्वालीफाइंग दौर हुआ। हर कोई जो हिस्सा लेना चाहता था, वह क्वालिफाइंग दौर में जगह बनाने के लिए आ सकता है।

याद रखें कि रूसी कोड कप चैंपियनशिप में कई ऑनलाइन पर्यटन शामिल हैं, जिसके परिणामों के अनुसार अंतिम प्रतियोगिता के लिए अंतिम, ऑफ़लाइन के लिए चयन किया जाता है।

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

क्वालिफाइंग राउंड विजेता क्वालिफाइंग राउंड में भाग लेते हैं। कुल मिलाकर, यह 600 लोगों (या 603 अगर 201 लोग योग्यता के दौर में चले गए) का पता लगाता है। क्वालिफाइंग राउंड के बाद, 50 फाइनलिस्ट निर्धारित किए जाते हैं। इस मामले में, ऐसी स्थिति भी हो सकती है जहां अंतिम स्थान दो प्रतिभागियों द्वारा साझा किया जाता है। इस मामले में, 51 लोग फाइनल में जाएंगे।

क्वालीफाइंग राउंड से पहले लगभग दो सप्ताह शेष हैं। अगले दौर की प्रत्याशा में, हम अंतिम क्वालीफाइंग दौर के परिणामों को संक्षेप में प्रस्तुत करेंगे और कार्यों का विश्लेषण करेंगे।

कार्यों के विषय:

• कार्य ए। परीक्षा।
• टास्क बी संचार।
• समस्या सी। सेंचुरी का मैच।
• समस्या डी। ऐरे विभाजन।
• टास्क ई। वन घटना।

दौर के दौरान, 681 लोगों ने लॉग इन किया। इनमें से कम से कम एक निर्णय 529 लोगों द्वारा भेजा गया था।

कुल 2660 समाधान भेजे गए थे।

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

• टास्क ए : इरिंका (3:59)
• समस्या B : चाप (5:18)
• टास्क सी : mr146 (19:53)
• टास्क डी : मेगाटाइक (37:26)
• टास्क E : peter50216 (78:11)

फेरे के दौरान दो नकलची देखे गए। राउंड के अंत में उनके परिणाम तुरंत रद्द कर दिए गए। नकल करने वालों की पहचान ITMO विशेषज्ञों द्वारा विकसित एक विशेष एल्गोरिथ्म द्वारा की जाती है और इसे कार्य सत्यापन प्रणाली में एकीकृत किया जाता है।

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

रूस => 337
यूक्रेन => 81
बेलारूस => 42
कजाकिस्तान => १>
आर्मेनिया => 10
यूएसए => 9
उजबेकिस्तान => ४
स्विट्जरलैंड => ४
जॉर्जिया => ३
बुल्गारिया => २
लातविया => २
स्वीडन => २
जर्मनी => २
आइसलैंड => 1
तुर्कमेनिस्तान => १
कोरिया गणराज्य => १
आयरलैंड => 1
मैसिडोनिया => १
अजरबैजान => १
रोमानिया => 1
स्पेन => १
यूके => 1
फ्रांस => १
मोलदोवा => १
किर्गिस्तान => १
पोलैंड => 1
सर्बिया => १

200 लोगों ने क्वालीफाइंग दौर में प्रवेश किया। उनमें से पहले 10:

1. एंड्री मकसे
2. डेनिस मुखामियानोव
3. उपनाम peter50216 के साथ सदस्य
4. विक्टर बारिनोव
5. अलेक्जेंडर बेरिकिन
6. मिखाइल रोज़्नर
7. मैक्सिम कालिनिन
8. ईडन का रोमन
9. इगोर किरोव
10. एंड्रे ज़ायकिन

नीचे दिए गए कार्यों की चर्चा रूसी कोड कप वेबसाइट पर भी उपलब्ध है।

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

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

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

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

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

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

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

इनपुट की पहली पंक्ति में एक पूर्णांक n (1 ≤ n) 104) - परीक्षणों की संख्या है। अगली n पंक्तियों में प्रारूप hh: mm: ss, साथ ही पूर्णांक k (1) k ≤ 2000) का S और F समाहित है - परीक्षा के आरंभ और अंत का समय और मिनटों में वह समय जिसके लिए इगोर कार्यक्रम लिखेंगे।
यह गारंटी दी जाती है कि परीक्षणों में समय सही तरीके से निर्धारित किया गया है।

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

एक अलग लाइन पर प्रत्येक परीक्षण मामले के लिए समस्या का उत्तर प्रिंट करें। यदि इगोर परीक्षा पास करता है, तो परफेक्ट प्रिंट करें। अगर इगोर को एक टेस्ट लिखना होगा, तो टेस्ट प्रिंट करें। अन्यथा, फेल प्रिंट करें।

उदाहरण:

इनपुट डेटा	उत्पादन
4 01:02:03 01:05:03 3 23:12:14 00:14:59 91 00:00:00 00:00:00 1000 01:00:00 05:00:00 666	उत्तम कसौटी उत्तम विफल

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

हम फॉर्मूला 60 × 60 × hh + 60 × mm + ss का उपयोग करके सेकंड में परीक्षा की शुरुआत और समाप्ति का समय का अनुवाद करते हैं, साथ ही साथ इगोर सूत्र 60 × k का उपयोग करके कार्यक्रम लिखने में खर्च करेंगे। फिर, हम सूत्र समय _{परीक्षा} = (समय _{समाप्ति} - समय _{प्रारंभ} + 24 × 60 × 60)% (24 × 60 × 60) का उपयोग करके परीक्षा की लंबाई की गणना करते हैं, यदि समय _{परीक्षा} = 0, तो वास्तव में परीक्षा की लंबाई 24 × 60 × 60 है। यदि कार्यक्रम का लेखन समय परीक्षा की अवधि से कम है, तो उत्तर बिल्कुल सही है। यदि परीक्षा लिखने का समय परीक्षा की अवधि से कम है, एक घंटे (60 × 60 सेकंड) तक बढ़ जाता है, तो उत्तर टेस्ट है। अन्यथा, उत्तर विफल है।

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

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

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

कई वर्षों के असफल प्रयासों के बाद, वैज्ञानिकों ने अंततः अंतरिक्ष में एक तर्कसंगत सभ्यता के साथ एक संबंध स्थापित करने में कामयाबी पाई और पाया कि एलियंस की वर्णमाला में केवल दो अक्षर होते हैं: a और b। संदेशों को प्राप्त करने के लिए, एक विशेष रिसीवर डिज़ाइन किया गया था, जो वर्णों को ए, बी और साथ ही विशेष चरित्र को बाहर निकालता है ?, यदि यह पता लगाना संभव नहीं था कि किस चरित्र को प्रेषित किया गया था।

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

एलियंस द्वारा एक संभावित संदेश प्राप्त करने वाले वैज्ञानिकों द्वारा डिज़ाइन किया गया एक उपकरण, ऊपर वर्णित संपत्ति को ध्यान में रखे बिना एक पंक्ति को पढ़ने के लिए सभी संभव तरीके देता है। उदाहरण के लिए, स्ट्रिंग "एब ??" प्राप्त करते हुए, डिवाइस "अबा", "अबाब", "अब्बा" और "एबब" लाइनों को प्रदर्शित करता है, जिनमें से केवल स्ट्रिंग "अबाब" वास्तव में एलियंस से एक संदेश हो सकता है, और अन्य तीन नहीं कर सकते हैं।

डिवाइस की गुणवत्ता में सुधार करने के लिए, वैज्ञानिक यह जानना चाहते हैं कि डिवाइस द्वारा प्रदर्शित लोगों में से कितनी लाइनें एलियंस से संदेश नहीं हो सकती हैं। ऐसा करने में उनकी मदद करें।

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

पहली पंक्ति में एक सकारात्मक पूर्णांक n होता है - वैज्ञानिकों द्वारा प्राप्त संदेश में शब्दों की संख्या।
अगली अगली पंक्तियों में संदेश से शब्द शामिल है, जिसमें अक्षर a, b और .. शामिल हैं। यह गारंटी है कि सभी शब्दों की लंबाई समान है, और यह भी कि प्रत्येक शब्द में कम से कम एक है? .. सभी शब्दों की कुल लंबाई 200,000 से अधिक नहीं है। यह गारंटी नहीं है कि प्रत्येक शब्द को एलियंस से संदेश के रूप में डिक्रिप्ट करने का कम से कम एक तरीका है।

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

एन लाइनों को प्रिंट करें। I-th लाइन में प्रतिस्थापित करने के तरीकों की संख्या प्रिंट करें? अक्षर a, b पर ताकि i-th शब्द एलियन का सही संदेश नहीं है। चूंकि विधियों की संख्या बहुत बड़ी हो सकती है, इसलिए इसे 10 ⁹ +7 मोडुलो आउटपुट करना आवश्यक है।

उदाहरण:

इनपुट डेटा	उत्पादन
3 ab। ब भेड़? अब्बू ???	1 2 7

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

ध्यान दें कि उत्तर सभी संभावित संदेशों की संख्या के बराबर है, शून्य से दुहराव की संख्या। प्रत्येक पंक्ति में प्रश्नों की संख्या m और 2l पंक्ति की लंबाई से निरूपित करें। फिर सभी संभावित संदेशों की संख्या 2 ^{मीटर है} । अग्रानुक्रम दोहराव की संख्या निम्नलिखित तर्क से पाई जा सकती है। यदि पद पर मैं एक प्रश्न चिह्न है, और पद पर i + l या _{b है} , तो पद पर पुनरावृत्ति में मैं समान अक्षर होना चाहिए। यदि दोनों पदों पर i और i + l प्रश्न चिह्न हैं, तो उत्तर को दो से गुणा करना होगा। इसी तरह, हम उस स्थिति पर विचार करते हैं जब प्रश्न चिह्न स्थिति i + l पर खड़ा होता है। अगर पदों पर i और i + l अलग-अलग अक्षर हैं, तो इस तरह की लाइन के लिए अग्रानुक्रम दोहराता है।

रनटाइम ओ (संदेश की लंबाई)।

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

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

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

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

मैच शुरू करने से पहले, रेफरी को सभी खिलाड़ियों को दो टीमों में विभाजित करना चाहिए और उन्हें नंबर आवंटित करना चाहिए। कुल मिलाकर, 2n खिलाड़ी मैच में भाग लेते हैं, जिनमें से जज n बेतरतीब ढंग से चुने गए खिलाड़ियों को पहली टीम में भेजते हैं, और बाकी खिलाड़ियों को दूसरे नंबर पर भेजते हैं। उसके बाद, रेफरी दोनों टीमों के सभी खिलाड़ियों को नंबर प्रदान करता है।

दोनों टीमों के खिलाड़ियों को नंबर मिलते हैं, जिनमें से प्रत्येक 1 से n तक का पूर्णांक है। एक ही टीम के सभी खिलाड़ियों की संख्या जोड़ीदार है। परंपरागत रूप से, पहली टीम में, खिलाड़ियों को अपने विकास के अवरोही क्रम में नंबर मिलते हैं, और दूसरे में, आरोही क्रम में।

जिन छात्रों ने सदी के कई मैचों को देखा है, वे प्रत्येक मैच के "मनोरंजन" की गणना करने के लिए प्यार करते हैं - एक ही संख्या के साथ विभिन्न टीमों के खिलाड़ियों के बीच जोड़ीदार विकास अंतर का योग। इसलिए, यदि पहली टीम 180 और 190 सेंटीमीटर की ऊंचाई वाले खिलाड़ियों द्वारा खेली जाती है, और दूसरे में - 170 और 205 सेंटीमीटर की ऊंचाई वाले खिलाड़ी हैं, तो इस मैच का मनोरंजन 180- 205 है। + | 190 - 170 | = 45. अब वे सभी प्रतिभागियों के विकास को जानते हुए, "सदी के मैच" के मनोरंजन की गणितीय अपेक्षा की गणना करने में रुचि रखते हैं। उनकी मदद करें।

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

प्रत्येक मैच के विवरण में दो लाइनें होती हैं। पहली पंक्ति में एक पूर्णांक 2n भी है - प्रतिभागियों की संख्या अगले "शताब्दी के मैच" में। अगली पंक्ति में 106 से अधिक नहीं - 2n जोड़ीदार प्राकृतिक संख्याएं हैं - सभी प्रतिभागियों की वृद्धि।
सभी मैचों में भाग लेने वाले प्रतिभागियों की कुल संख्या 106 से अधिक नहीं है।

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

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

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

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

उदाहरण:

इनपुट डेटा	उत्पादन
1 4 २० ३० १० ४०	40.0

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

बता दें कि मैच में 2 × n खिलाड़ी भाग लेते हैं। हम उन्हें वृद्धि के क्रम में क्रमबद्ध करते हैं। अब हम निम्नलिखित कथन को सिद्ध करते हैं: टीमों द्वारा किसी भी विभाजन के लिए आवश्यक राशि समान है, और _{n + 1} + a _{+ n + 2} + ... + _{2 × n} - ₁ - a ₂ - ... - a _{n के} बराबर है। हम सुधार करते हैं: किसी भी खिलाड़ी की संख्या जिनकी संख्या n से अधिक नहीं होती है, उन्हें हमेशा माइनस साइन के साथ आवश्यक राशि में शामिल किया जाता है, और ऐसे खिलाड़ी की संख्या जिनकी संख्या n से अधिक होती है उन्हें प्लस के साथ वांछित राशि में शामिल किया जाता है।

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

इस कथन को सिद्ध करने के बाद, समस्या का समाधान स्पष्ट हो जाता है। उदाहरण के लिए, आप सभी खिलाड़ियों को विकास के द्वारा O (n × log2n) के आधार पर क्रमबद्ध कर सकते हैं, और फिर एक ऋण के साथ पहला n और दूसरे के साथ खाते में ले सकते हैं।

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

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

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

1 से 3 एन तक पूर्णांक के सेट पर विचार करें। इन संख्याओं को तीन सरणियों ए, बी और सी लंबाई में वितरित करना आवश्यक है ताकि किसी भी 1 से n के लिए निम्नलिखित सत्य हो: एक _i + b _i = c _i

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

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

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

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

उदाहरण:

इनपुट डेटा	उत्पादन
1	1 2 3
2	-1

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

समाधान का मुख्य विचार कटऑफ के साथ पूर्व-गणना और गणना है। सबसे पहले, पता करें कि उत्तर के किन मूल्यों का अस्तित्व नहीं है। 1 से 3 एन तक सभी संख्याओं का योग 3n * (3n + 1) / 2 है। दूसरी ओर, हम एस द्वारा सरणी सी के तत्वों के योग का निरूपण करते हैं। तब ए और बी में तत्वों का योग भी एस के बराबर होता है। हम 2S = 3n * (3n + 1) / 2, अर्थात 3n * (3n + 1) / 2 4 से विभाज्य होना चाहिए, जो कि सत्य है अगर और केवल n 0 या 1 मोडुलो 4 से तुलनीय है। ऐसे मामलों में जहां n को 4 से विभाजित करने का शेष 2 या 3 है, कोई गारंटीकृत समाधान नहीं है। अन्य सभी एन के लिए स्थिति में निर्दिष्ट शर्तों के तहत, एक समाधान मौजूद है।

खोज को गति देने के लिए, आंकड़े और कतरन को लागू किया जाना चाहिए। लेखक का समाधान इस तथ्य का उपयोग करता है कि दिए गए प्रतिबंधों के तहत, यदि कोई समाधान है, तो एक समाधान है जिसमें सरणी 1 से n तक की संख्याओं से भरा है। इस अनुमान के साथ, लेखक का समाधान 1 से 36 तक सभी n के लिए 3 सेकंड में एक उत्तर खोजने में सक्षम है।

समस्या ई। वन घटना
विचार: विटालि डीमनिअनुक
बोध: विटालि दुमंजुक
विश्लेषण: विटाली डमींजुक

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

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

बैटलैंड एक बहुत ही हरा-भरा और पर्यावरण के अनुकूल देश है जहाँ कई जंगल, नदियाँ और झीलें हैं। Baytland के सभी जंगलों में एक उत्तम आयत का आकार है। I-th वन की भुजाओं की लंबाई n _i और m _i किलोमीटर है। प्रत्येक जंगल को आयत के किनारों के समानांतर रेखाओं में विभाजित किया जाता है, जिसकी लंबाई एक किलोमीटर के बराबर होती है। प्रत्येक वर्ग का अपना वनपाल होता है।

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

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

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

पहली पंक्ति में एक धनात्मक पूर्णांक t होता है - बैटलैंड में वनों की संख्या।
अगली टी लाइनों में से प्रत्येक में दो नंबर n _i और m _{i हैं} - i-th फ़ॉरेस्ट के किनारों की लंबाई। (1 ≤ n _i ≤ 10 ⁷ , 1 ≤ m _i n 10 ⁷ nm) 2)।
Baytland में जंगलों की संख्या 10,000 से अधिक नहीं है।

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

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

उदाहरण:

इनपुट डेटा	उत्पादन
2 13 45	2 2015/144

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

आइए हम जलाऊ लकड़ी एक्स के वितरण के संभावित परिदृश्यों में से एक को नामित करें। हम l _{i, j} (x) को एक फंक्शन के रूप में परिभाषित करते हैं जो एक के बराबर होता है यदि फ़ॉरेस्ट में रहने वाले फ़ॉरेस्टर निर्देशांक i और j में सर्दियों के लिए जलाऊ लकड़ी है, और अन्यथा शून्य। सर्दियों के लिए जलाऊ लकड़ी रखने वाले वनवासियों की संख्या जंगल के सभी वर्गों के लिए राशि l _{i, j} (x) के बराबर है। फिर, गणितीय अपेक्षाओं की रैखिकता के अनुसार, अपेक्षित अपेक्षाएं वन की सभी चौकों पर _j, गणितीय अपेक्षाओं l _i के योग के बराबर होती हैं। गणितीय प्रत्याशा l _{i, j} : E (l _{i, j} ) = 0 × p _{i, j} + 1 × (1-p _{i, j} ) = 1 - p _{i, j} , जहाँ p _{i, j} , प्रायिकता है कि संबंधित वनपाल के पास सर्दियों के लिए जलाऊ लकड़ी नहीं थी। पी _{i, j की} गणना उन घटनाओं की संभावनाओं के उत्पाद के रूप में करना संभव है जो कि फॉरेस्टर को संबंधित पड़ोसी से जलाऊ लकड़ी प्राप्त नहीं हुई थी।



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

अगला आरसीसी क्वालीफाइंग राउंड 16 जून को होगा। हम कार्यों के विश्लेषण को प्रकाशित करेंगे। देखते रहो!