मोबाइल यांडेक्स। ब्लिट्ज: हम कार्यों का विश्लेषण करते हैं

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

"गैस आपूर्ति" का कार्य

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

कंपनी n क्षेत्रों पर विचार कर रही है जो कि d ₁ ... d _i ... d _n पाइपलाइन से दूर किलोमीटर हैं और v ₁ ... v _i ... v _n गैस इकाइयाँ उत्पन्न कर सकते हैं। प्रत्येक क्षेत्र के लिए एक अलग लाइसेंस बेचा जाता है - लाइसेंस s ₁ ... s _i ... s _{n है} ।

खेतों को राजमार्ग से जोड़ने के लिए, आपको पाइपलाइन बनाने की आवश्यकता है। एक ठेकेदार जो मीटर के विभिन्न प्रकार के पाइप बिछा सकता है, इस कंपनी की मदद करता है। पाइप एक दूसरे से लंबाई में भिन्न होते हैं (l ₁ ... l _i ... l _m ) और मूल्य (p ₁ ... p _i ... p _m )। आप जैसे चाहें एक दूसरे के साथ जुड़ सकते हैं।

कंपनी के पास के सिक्के हैं और वह अधिक से अधिक गैस प्राप्त करना चाहता है।

यदि ठेकेदार ठेकेदार को इष्टतम आदेश देता है तो कंपनी कितना उत्पादन कर पाएगी?

पाइप लाइन खेत से पाइप लाइन की दूरी से अधिक लंबी हो सकती है।

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

पहली पंक्ति में एक पूर्णांक k contains 10 ^{5 होता है} ।

दूसरी पंक्ति में पूर्णांक n ≤ 15 होता है।

अगली n लाइनों में तीन पूर्णांक d _i v 100, v _i s 100 और s _i । 100 हैं।

एक स्थान से संख्याओं को अलग किया जाता है।

अगली पंक्ति में पूर्णांक m line 15 है।

अगली मी लाइनों में दो पूर्णांक l _i p 100 और p _i The 100 हैं। संख्याओं को एक स्थान से अलग किया जाता है।

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

उत्तर के साथ एकमात्र रेखा।

उदाहरण

  116
 3
 58 7 50
 81 71 56
 ५२ ५ ३१
 3
 ४। ९
 १ २५
 १ 61 ६१ 

  57 

पदच्छेद

शुरू करने के लिए, आइए अंकन को परिभाषित करें। मानदंड के साथ ऑब्जेक्ट्स डिपॉजिट (जमा) का एक वर्ग हो$$ $ इनलाइन $ Dd_ {i} $ इनलाइन $ (दूरी),$$ $ इनलाइन $ Dv_ {i} $ इनलाइन $ (उत्पादन की मात्रा) और$$ $ इनलाइन $ Ds_ {i} $ इनलाइन $ (लाइसेंस लागत)। इस प्रकार की सूचकांक वस्तुएं चर I होंगी। मापदंडों के साथ एक पिपेलिनर ऑब्जेक्ट क्लास भी है$$ $ इनलाइन $ PPl_ {j} $ इनलाइन $ (पाइप की लंबाई जो ठेकेदार बना सकता है) और$$ $ इनलाइन $ PPp_ {j} $ इनलाइन $ (इस पाइप की कीमत), जे के माध्यम से सूचकांक। ब्लिट्ज के प्रतिभागियों ने कई बार पूछा कि क्या एक प्रकार के पाइप का उपयोग दो बार किया जा सकता है। यह माना जाता है कि नहीं, और यह उदाहरण स्पष्ट रूप से दिखता है। तो इस कार्य की शर्तों से, स्वीकार करना$$ $ इनलाइन $ D_ {i} = {0, 1} $ इनलाइन $ (फ़ील्ड चुनें या नहीं) और$$ $ इनलाइन $ PP_ {j} = {0, 1} $ इनलाइन $ (एक ठेकेदार चुनें या नहीं), आप एक रैखिक प्रोग्रामिंग कार्य कर सकते हैं:

$$$ इनलाइन $ \ _ \ _ सीमाएं {{i} D_ {i} * Dv_ {i} \ rightarrow अधिकतम \\ \ sum \ limit_ {i} D_ {i} * Ds_ {i} + \ योग \ सीमाएँ {j} PP_ { j} * PPp_ {j} \ leq k \\ \ sum \ limit_ {i} D_ {i} * Dd_ {i} \ leq \ sum \ limit_ {j} PP_ {j} * PPl_ [j} \\ D_ { i} = {0, 1}, PP_ {j} = {0, 1} $ इनलाइन $

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

"टावर्स और एआई" का कार्य

आर्टेम एक प्रतिस्पर्धी मोबाइल गेम खेलते हुए कृत्रिम बुद्धि विकसित कर रहा है। खेल के नियम सरल हैं।

खिलाड़ियों से पहले सी ₁ ... c _i ... c _{n की} ऊंचाई के साथ n टावर्स हैं। अपनी बारी पर, खिलाड़ी टावरों में से एक को तोड़ सकता है ताकि कई छोटे टॉवर प्राप्त हों। खिलाड़ी टावरों में भ्रमित होने से डरते हैं, इसलिए वे एक सीमा पर सहमत हुए: अलग होने के बाद, एक ही ऊंचाई के दो टावरों को प्राप्त नहीं किया जाना चाहिए। उदाहरण के लिए, 7 की ऊंचाई वाले टॉवर को (1, 2, 4) में विभाजित किया जा सकता है, लेकिन (1, 3, 3) में नहीं। ऊँचाई हमेशा एक पूर्णांक होती है।

हार जाता है जिसके पास टावर नहीं होते जो नष्ट हो सकते हैं।

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

मनुष्य हमेशा पहले चलता है। वह एआई के गेम्स के साथ खेलेंगे।

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

पहली पंक्ति में एक पूर्णांक k <500 होता है।

इसके बाद दो लाइनों के k ब्लॉक होते हैं।

प्रत्येक ब्लॉक की पहली पंक्ति एक पूर्णांक 0 <n block 50 है।

प्रत्येक ब्लॉक की दूसरी पंक्ति में एन पूर्णांक 0 <c _i The 50 है। संख्याओं को रिक्त स्थान द्वारा अलग किया जाता है।

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

k लाइनें, जिनमें से प्रत्येक सही या गलत है, इस पर निर्भर करता है कि कोई व्यक्ति गेम जीतता है या नहीं।

उदाहरण

  2
 1
 4
 2
 १ १ 

  झूठा
 झूठा 

पदच्छेद

प्रस्तावित टॉवर खेल दो खिलाड़ियों के लिए एक समान अंत वाला खेल है जिसमें इसे खींचना असंभव है।

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

यहाँ उनका संक्षिप्त विवरण है-एक खेल (स्रोत से लिंक - विस्तृत समीक्षा के लिए इस पर क्लिक करें):

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

तो, खेल "उसे" की स्थिति विशिष्ट रूप से प्राकृतिक संख्याओं के एक अनियंत्रित सेट द्वारा वर्णित है। एक चाल में, इसे किसी भी संख्या को कड़ाई से कम करने की अनुमति है (यदि परिणामस्वरूप संख्या शून्य हो जाती है, तो इसे सेट से हटा दिया जाता है)।

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

कार्य "रेटिंग संकेत"

गैल्या एक समीक्षा एग्रीगेटर विकसित कर रहा है। उसने सात-नुकीले तारों की मदद से संस्थानों की रेटिंग तय करने का फैसला किया।

इनपुट रेंडरिंग सिस्टम को ऊंचाई h और चौड़ाई w की एक आयत प्राप्त होती है, जिसके ऊपरी बाएँ कोने में बिंदु (x, y) स्थित होता है। एक स्टार को निम्नलिखित नियमों के अनुसार तैयार किया जाना चाहिए:

1. किसी तारे का आकार आयत की चौड़ाई या ऊँचाई से निर्धारित होता है - अर्थात् छोटा। (चित्र देखें।)
2. यदि आयत का एक आयाम तारे के संगत आयाम से बड़ा है, तो तारे को उस आयाम पर केंद्रित किया जाना चाहिए।
3. स्टार को इंगित किया गया है।

रेंडरिंग सिस्टम को गाली कोड से स्टार के कोने के निर्देशांक की अपेक्षा है। उन्हें गणना करने के लिए गेल की मदद करें।

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

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

एक एकल पंक्ति में पूर्णांक x, y, w और h होते हैं, जिन्हें रिक्त स्थान द्वारा अलग किया जाता है।

उदाहरण: प्रविष्टि १५० ० ५० १०० में ५० अंकों की चौड़ाई, १०० अंकों की ऊँचाई और बिंदु पर ऊपरी बाएँ कोने (१५०, ०) के साथ एक आयत दर्शाया गया है।

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

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

उदाहरण: तीन बिंदुओं (1, 2), (3, 4), (5, 6) का आउटपुट इस तरह दिखना चाहिए: 1 2 3 4 5 6।

उदाहरण

  0 0 100 100 

  ५० १ ६५ २१ ९ ० ९ 100५ ४५ १०० 65५ 65५ 50२ 50० ५० 28 21 २ ९९ 64२ २२ 21५ १५ ४५ १० २० ३५ २१ 

नोट

• आवश्यक सटीकता 10 महत्वपूर्ण अंक है।

  
  

• समन्वय प्रणाली: एक्स अक्ष को बाएं से दाएं, वाई अक्ष से ऊपर से नीचे तक निर्देशित किया जाता है:

  
  

• अपेक्षित शीर्ष क्रम:

अंकित तारों के उदाहरण:

पदच्छेद

समस्या का समाधान तीन चरणों में घटाया गया है: अंतरिक्ष में वांछित अभिविन्यास के साथ एक संदर्भ सितारा बनाने के लिए, परिणामी बिंदुओं को मापें, ऑफसेट की गणना करें और लागू करें।

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

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

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

आगे की कार्रवाई इस बात पर निर्भर करती है कि हमने पिछले चरण में क्या गुणांक चुना है:

• यदि ऊँचाई में स्केल किया जाता है - हम आयत की चौड़ाई और बाईं ओर से दाईं ओर की दूरी के बीच का अंतर लेते हैं;
• यदि चौड़ाई में स्केल किया जाता है - हम आयत की ऊंचाई और उच्चतम से निम्नतम बिंदु तक की दूरी के बीच का अंतर लेते हैं।

प्राप्त मूल्य को 2 से विभाजित करें और संबंधित माप के अनुसार अंक स्थानांतरित करें। जवाब मिला।

कार्य "चक्र की रोटेशन और स्केलिंग"

वीका स्मार्टफोन और टैबलेट के लिए एक ग्राफिक्स एडिटर विकसित कर रहा है। वह उपयोगकर्ता को दो उंगलियों के साथ स्क्रीन पर एक चक्र को घुमाने और उसके आकार को बदलने का अवसर देना चाहती है:

यह आंकड़ा उसी कोण पर घूमता है जिससे अंगुलियों को जोड़ने वाला खंड घूमता है। खंड की लंबाई के अनुपात में आकृति का आकार बदलता है। सबसे पहले, आकृति को घुमाया जाता है, और फिर इसका आकार बदल दिया जाता है। प्रारंभ में, सर्कल में निर्देशांक (x, y) और त्रिज्या r है। उपयोगकर्ता के हावभाव का वर्णन करने वाली स्पर्श घटनाओं की एक सूची दी गई है। Vika सर्कल के केंद्र और उसके त्रिज्या के अंतिम निर्देशांक की गणना करने में मदद करता है। सर्कल बिंदु (ए, बी) के सापेक्ष घूमता है।

स्पर्श घटना के विवरण में उंगली आईडी, निर्देशांक और घटना के प्रकार शामिल हैं। उपयोगकर्ता द्वारा संलग्न पहली उंगली आईडी 0, दूसरी - आईडी 1, और इसी तरह प्राप्त करती है।

एक उदाहरण:
0 337 490 ACTION_DOWN - इसका अर्थ है कि उंगली 0 के बिंदु पर (337, 490) ACTION_DOWN घटना हुई।

स्पर्श कार्यक्रम निम्न प्रकार के होते हैं:

• ACTION_DOWN - उपयोगकर्ता ने दिए गए बिंदु पर पहली उंगली को स्क्रीन पर लागू किया।
• ACTION_POINTER_DOWN - उपयोगकर्ता ने दिए गए बिंदु पर स्क्रीन पर दूसरी उंगली लगाई।
• ACTION_MOVE - उपयोगकर्ता ने अपनी उंगली को दिए गए बिंदु पर स्थानांतरित कर दिया है।
• ACTION_POINTER_UP - उपयोगकर्ता ने दूसरी उंगली को निर्दिष्ट बिंदु पर स्थानांतरित किया और इसे जारी किया।
• ACTION_UP - उपयोगकर्ता ने पहली उंगली को निर्दिष्ट बिंदु पर स्थानांतरित किया और इसे जारी किया।
• ACTION_CANCEL - उपयोगकर्ता गर्भपात।

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

पहली पंक्ति में संख्या x, y और r होते हैं, जिन्हें रिक्त स्थान द्वारा अलग किया जाता है। दूसरी पंक्ति में नंबर और बी होते हैं, जिन्हें रिक्त स्थान द्वारा अलग किया जाता है। अगली कुछ पंक्तियों में लगातार स्पर्श घटनाएं होती हैं।

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

निर्देशांक और त्रिज्या के साथ एकमात्र रेखा। नंबर रिक्त स्थान द्वारा अलग किए गए हैं।

उदाहरण

  २५२ १ ९ ४ 78
 445,559
 0 337,490 ACTION_DOWN
 1,599,490 ACTION_POINTER_DOWN
 1,576,564 ACTION_MOVE
 1,552,590 ACTION_MOVE
 0 407,375 ACTION_MOVE
 1 505 615 ACTION_MOVE
 1 482 620 ACTION_MOVE
 0 477 360 ACTION_MOVE
 1,435,616 ACTION_MOVE
 1,411,607 ACTION_MOVE
 0 547 386 ACTION_MOVE
 1 364 548 ACTION_POINTER_UP
 0 571 387 ACTION_UP 

  831 704 73 

नोट

परिणाम प्रदर्शित करते समय, गणितीय फ़ाउंडिंग के नियमों के अनुसार सभी फ़्लोटिंग-पॉइंट मानों को पूर्णांक मान पर गोल करना आवश्यक है।

पदच्छेद

इस तथ्य के बावजूद कि इशारा जटिल लगता है, इसे दो घटकों में विभाजित किया जा सकता है: रोटेशन और स्केलिंग। आकृति को घुमाने के लिए, हमें रोटेशन के कोण की गणना करने की आवश्यकता है, जिसे निम्नलिखित सूत्र का उपयोग करके प्राप्त किया जा सकता है:
a = atan2 (prevTouchX2 - prevTouchX2, prevTouchY2 - prevTouchY1) - atan2 (currentTouchX2 - currentTouchX1, currentTouchY2 - currentTouchY1)।

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

कार्य "सड़क निर्माण"

एक मोबाइल गेम में, मुख्य चरित्र एक दूर के ग्रह पर एक आधार बनाता है। वह परिधि के साथ शुरू होता है - सीधे लेजर दीवारों द्वारा जुड़े टॉवर। मुख्यालय के आर्किटेक्ट उसे निर्देशांक (x ₁ , y ₁ ) ... (x _i , y _i ) ... (x _n , y _n ) के साथ n टावरों को दिखाते हुए एक योजना भेजते हैं। आधार रक्षा के दृष्टिकोण से, एक सीधी रेखा में तीन या अधिक पड़ोसी टॉवर लगाने का कोई मतलब नहीं है। कर्मचारी आर्किटेक्ट, हालांकि, कभी-कभी इस तरह से टावरों की स्थिति बनाते हैं, इसलिए खिलाड़ी को स्वयं अतिरिक्त मध्यवर्ती टावरों को निकालना पड़ता है।

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

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

यदि यह पता चला है कि आप बेस के बाहर सड़क को प्रशस्त कर सकते हैं, तो नायक बेस को असुरक्षित घोषित करता है और ग्रह से दूर उड़ जाता है।

किचन में कितने रोबोट काम करेंगे?

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

पहली पंक्ति में तीन पूर्णांक 4 ≤ n, 10 ⁷ , 1 ≤ k contains n और एक अभाज्य संख्या 105 <p <11 × 104 है। संख्याओं को रिक्त स्थान द्वारा अलग किया जाता है।

अगली n लाइनों में दो पूर्णांक 0 <x _i , y _i <109 हैं। संख्याएँ रिक्त स्थान से अलग हो गई हैं।

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

उत्तर के साथ एकमात्र रेखा। यदि आधार सुरक्षित नहीं है, तो −1 प्रिंट करें।

उदाहरण 1

  4 1 101363 है
 ० ०
 १ ०
 १ १
 ० १ 

  101,361 

एकमात्र सड़क को प्रशस्त करने के दो तरीके हैं: (0, 0) - (1, 1) और (1, 0) - (0, 1)। दो रोबोट उनमें लगे होंगे, और बाकी रसोई में जाएंगे: पी - 2 = 101 361।

उदाहरण 2

  4 1 101363 है
 १ ०
 २ ०
 ० १
 १ २ 

  -1 

यहां आप (1, 0) - (0, 1) के बीच सड़क बना सकते हैं, और यह बेस के बाहर है। नायक आधार को असुरक्षित के रूप में पहचानता है, इसका उत्तर base1 है।

उदाहरण 3

  4 1 101363 है
 ० ० 
 १ ०
 २ ०
 ० १ 

  101,363 

टावर्स (0, 0), (1, 0) और (2, 0) एक ही पंक्ति में हैं, इसलिए नायक मध्य टॉवर (1, 0) का निर्माण नहीं करेगा। किसी भी सड़क को पक्का नहीं किया जा सकता है, इसलिए, सभी रोबोट तुरंत रसोई में जाएंगे: पी = 101 363।

पदच्छेद

हम समस्या के समाधान को तीन चरणों में विभाजित करते हैं।

पहला कदम इनपुट वर्टेक्स डेटा सेट के लिए निर्धारित करना है कि क्या बहुभुज उत्तल है, और यदि हां, तो कितने वास्तविक कोने हैं। एक बहुभुज उत्तल है यदि इसके सभी कोने किसी भी किनारे का समर्थन करने वाली रेखा के एक तरफ स्थित हैं। आसन्न कोने के प्रत्येक ट्रिपल के लिए$$ $ इनलाइन $ (x_ {i-1}, y_ {i-1}), (x_ {i}, y_ {i}), (x_ {i + 1}, y_ {i + 1}) $ inline $ वैक्टर के एक जोड़े का निर्माण$$ $ इनलाइन $ ab = ((x_ {i-1}, y_ {i-1}), (x_ {i}, y_ {i})) और bc = ((x_ {i}, y_ {i})] (x_ {i + 1}, y_ {i + 1})) $ इनलाइन $ , और ab.x bc.y - bc.x ab.y. की अभिव्यक्ति के चिन्ह की गणना करें।यदि अभिव्यक्ति 0 है, तो कोने एक सीधी रेखा पर स्थित हैं और समस्या की स्थिति के अनुसार, मध्य शीर्ष में खड़े टॉवर गायब हो जाते हैं, टावरों की कुल संख्या को कम करते हैं। यदि सभी प्रकार के कोने के लिए उत्पाद का चिह्न 0 या हमेशा समान है, तो दूसरे चरण पर जाएं, यदि नहीं, तो हम आधार को असुरक्षित मानते हैं और उत्तर -1 को प्रिंट करते हैं।

दूसरा कदम। एक उत्तल एन-गॉन के अंदर कश्मीर डिस्जाइनल विकर्णों के निर्माण के तरीकों की संख्या है $$वी=1/ (के+1)(एन-3k )(एन+के-१k )$V = 1/(k+1){N-3\choose k}{N+k-1\choose k}$, लेकिन हमें अभिव्यक्ति पी - वी मॉड पी की गणना करने की आवश्यकता है, जहां पी एक प्रमुख है।

कल्पना कीजिए एन! कैसे$$a∗pe$a * p^e$ , — a, p gcd(a, p) = 1.

$$(nr)=(n!)/(r!(nr)!)=a1∗pe1/a2∗pe2∗a3∗pe3=(a1/a2∗a3)∗pe1−e2−e3${n\choose r} = (n!)/(r!(nr)!) = a_{1}*p^{e_{1}}/a_{2}*p^{e_{2}}*a_{3}*p^{e_{3}} = (a_{1}/a_{2}*a_{3})*p^{e_{1}-e_{2}-e_{3}}$

$$e1−e2−e3>0$e_{1}-e_{2}-e_{3} > 0$, , p p.

$$e1−e2−e3>0$e_{1}-e_{2}-e_{3} > 0$= 0$$a1/a2∗a3$a_{1}/a_{2}*a_{3}$ mod p.

, a b mod p = (a mod p ) (b mod p) mod p,$$k−1$k^{-1}$ mod p =$$(k)p−2$(k)^{p-2}$ mod p p.

तीसरा कदम।$$e1−e2−e3$e_{1}-e_{2}-e_{3}$ n! 1 2 … p (p+1) ... 2p (2p+1) ..., (p+1) ... (2p-1) mod p = 1 2 ...(p-1)=(p-1)!.. , n mod p = ($$(p−1)!k$(p-1)!^k$ k (n mod p)!)mod p, k = floor(n/p).

« »

n , . t ₁ … t _i … t _n , d _i - i- .

, , . , — , — , , . .

: , , . .

; , . , .

, ?

1 < n ≤ 3 × 10 ³ .
n 0 ≤ t _i ≤ 10 ⁴ 0 ≤ d _i ≤ 10 ⁴ . .

. — .

  5
2 2
1 1
3 4
1 10
1 2 

 10.25000000 

, . k=1 , , .

() , . 1,5 , , . , .

« »

2D- . , : n- (x ₁ , y ₁ )...(x _i , y _i )...(x _n , y _n ). — , . . , — , .

, [0 1 2 3 4], 1 3 1 3, [1 2 3] [0 1 3 4].

, . . , , .

, ?

n ≤ 500. n x y. .

. — .

उदाहरण 1

  4
100 100
200 100
200 200
100 200 

 0.000000 

उदाहरण 2

  6
167 84
421 84
283 192
433 298
164 275
320 133 

 326.986753 

, , . « » : — . : , ( ) .

, ? ( , , ). : , , , . , , ( ) . even-odd rule: . — , ( ) , — .

, , — , . (, , ):

• ( );
• : , - ;
• ( , 10-5 );
• even-odd rule — ;
• : 180 .

«DNA»

, . , , . n . , . : A, T, G C. . .

n. n . . 6⋅10 ⁶ .

. . . . . , .

( , ):

5
TTT
GAAGCT
CAAT
AGA
AGGCA

2 TTT
6 AGA
28 AGA
30 AGA
57 CAAT
86 AGA
100 GAAGCT
190 TTT
191 TTT
196 AGA
219 TTT
232 AGA
271 TTT
284 TTT
285 TTT
298 TTT
320 TTT
330 TTT
331 TTT
342 TTT
373 AGA
397 AGA
488 AGA
509 AGA
524 AGA
565 TTT
574 AGA
605 AGA
625 CAAT
630 AGA
681 CAAT
718 TTT
719 TTT
744 AGGCA
754 AGA
784 AGA
808 TTT
821 CAAT
833 AGA
861 CAAT
879 AGA
921 AGA
955 AGA

, . — , — . , . . , .

, .

«QR Quest»

t, . t n _i , .

t , .

उदाहरण 1

  4
8 10 1 9 2 6 7 8
14 2 0 11 10 4 1 0
6 6 4 1 10 0 11 6
11 4 3 4 14 8 12 5 

  0
 13
 15
 5 

उदाहरण 2

  4
9 10 6 2 12 11 7 2
3 10 1 14 13 13 1 1
6 8 8 5 3 2 6 4
5 11 5 5 3 1 10 7 

  3
 9
 2
 7 

, . QR- , . - .

— , 4 . , .

, xor- A, B C, a ₀ ...a ₇ :
R = A[a ₀ , a ₁ ] ^ B[a ₂ , a ₃ ] ^ B[a ₄ , a ₅ ] ^ C[a ₆ , a ₇ ].