सभी कार्यों और Yandex.Algorithm परिणामों का विश्लेषण

कुछ ही घंटों पहले, ओपन प्रोग्रामिंग चैम्पियनशिप Yandex.Algorithm 2013 का अंत सेंट पीटर्सबर्ग में हुआ था। प्रतियोगिता में 100 मिनट के प्रत्येक ऑनलाइन राउंड शामिल थे, 84 देशों के 3,000 से अधिक प्रोग्रामर ने जीत के लिए लड़ाई लड़ी। तीन क्वालीफाइंग राउंड के परिणामों के अनुसार, शीर्ष 25 फाइनल में पहुंच गया।



फाइनलिस्ट्स को 100 मिनट में छह एल्गोरिथम समस्याओं को हल करना था। पहला स्थान ACM ICPC 2013 के हालिया विजेता ने NRU ITMO Gennady Korotkevich (पर्यटक) की टीम में लिया, जिसने कम से कम पेनल्टी टाइम स्कोर किया। दूसरा स्थान NRU ITMO के येवगेनी कपुन (ईटमोर) स्नातक में गया। तीसरा स्थान ताइवान के प्रतिनिधि शी बिक्सुन ने लिया।

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

टास्क ए कट!

समस्या और पार्सिंग द्वारा लिखित: जैकब पचोकी, वारसॉ यू

इनपुट फ़ाइल का नाम : स्टडिन
आउटपुट फ़ाइल नाम : stdout
समय सीमा : 8 सेकंड
मेमोरी सीमा : 512 एमबी

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

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

इस मामले में:

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

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

इनपुट फ़ाइल का प्रारूप। इनपुट फ़ाइल की पहली पंक्ति में विश्वविद्यालय का नाम है। नाम में अपरकेस और निचले अक्षर लैटिन, स्पेस, कॉमा (",") और हाइफ़न ("-") हो सकते हैं।
यह गारंटी है कि लाइन एक स्थान के साथ शुरू और समाप्त नहीं होती है और इसमें लगातार दो स्थान नहीं होते हैं। इनपुट फ़ाइल में वर्णों (रिक्त स्थान सहित) की संख्या 10 ⁶ से अधिक नहीं है।

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

stdin	stdout
वारसॉ विश्वविद्यालय	विश्वविद्यालय। डब्ल्यू के
सेंट पीटर्सबर्ग नेशनल रिसर्च यूनिवर्सिटी ऑफ आईटी, मैकेनिक्स एंड ऑप्टिक्स	सेन। पे। ना। अनुसंधान यूनी। आई।, एम। और ओ।
अर्बिना में यूनिवर्सिटी ऑफ इलिनोइस-शैम्पेन	विश्वविद्यालय। I. के U.-C में
, कार्नेगी -, - मेल्लोएन -, -, - विश्वविद्यालय-	, Ca .--, - मेल्लोएन -, -, - यू.-
उदमुर्तियन विश्वविद्यालय	Udm। यू

नोट। «विश्वविद्यालय। डब्ल्यू का। "वारसॉ विश्वविद्यालय" के लिए लेक्सिकोग्राफिक रूप से सबसे छोटा संक्षिप्त नाम है, क्योंकि स्ट्रिंग "यूनीफॉव" अन्य रूपों के अनुरूप स्ट्रिंग्स की तुलना में लेक्सिकोग्राफिक रूप से छोटा है, उदाहरण के लिए, "यूओवी", "यूनीफोवा", "यूनिवर्सोफ़ारसॉ"।

समस्या ए का समाधान।

इनपुट को पार्स करने के बाद, कार्य निम्न में से उबलता है:

एन लाइनों के लिए ₁ , ... कुल लंबाई एन के एन, उनके गैर-रिक्त उपसर्ग p ₁ , ..., p _{n को} ज्ञात करें कि रेखा

पी ₁ पी ₂ ... पी _एन

शाब्दिक रूप से सबसे छोटा है।

मान लीजिए कि हमने पहले से ही p _{k + 1} , ..., p _n ऐसा पाया है कि string p _{k + 1} p _{k + 2} ... p _n lexicographically सबसे छोटा है। ध्यान दें कि p _{k + 1} , ..., p _{n की} यह पसंद p ₁ , ..., p _k के किसी भी विकल्प के लिए इष्टतम है। यह इस तथ्य से निम्नानुसार है कि यदि t < t ' दो तार t और t' के लिए सही है, तो < wt 'अपनी पंक्ति w के लिए ।

प्रभावी रूप से दिए गए p _{k + 1} , ...., p _n से इष्टतम उपसर्ग p _k कैसे ज्ञात करें?
टी लगाओ : = p _{k + 1} p _{k + 2} ... p _n । हमें स्ट्रिंग s की एक गैर-रिक्त उपसर्ग p खोजने की आवश्यकता है जैसे कि स्ट्रिंग pt lexicographically न्यूनतम है।

एक एल्गोरिथ्म है जो आपको प्रभावी रूप से pt की तुलना करने की अनुमति देता है और हैश का उपयोग करके तार नहीं करता है :

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

जब एक यादृच्छिक हैश का उपयोग किया जाता है, तो एल्गोरिथ्म (लॉग एन ) के लिए बहुत अधिक संभावना के साथ काम करता है।
P _k को खोजने के लिए, इसे पूरा करना आवश्यक है s _k | - 1 ऐसी तुलना जो p _{k की} गणना करने के लिए समय (| s _k | लॉग एन ) देती है। सभी _{k को} समेटते हुए, हम एल्गोरिथ्म ( N log N ) का रनिंग टाइम प्राप्त करते हैं।

समस्या बी। कोई और "बिट वाइज"

समस्या और विश्लेषण के लेखक अलेक्सई टॉल्स्टिकोव और रोमन उडोविचेंको हैं।
इनपुट फ़ाइल का नाम : स्टडिन
आउटपुट फ़ाइल नाम : stdout
समय सीमा : 2 सेकंड
मेमोरी सीमा : 512 एमबी

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

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

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

जबकि एनी को कंप्यूटिंग का शौक था, उसके माता-पिता सोच रहे थे कि उनकी बेटी को कुछ संख्या में एक्स कैसे मिल सकता है? विभिन्न तरीकों की संख्या की गणना अलग-अलग जोड़े (i, j) की संख्या के रूप में की जा सकती है जैसे कि 1 ≤ i ≤ P , 1, j , M , A _i AND B _j = X. चूँकि Anyuta के माता-पिता अपनी बेटी से कम उत्सुक नहीं हैं, इसलिए वे न केवल एक नंबर X के लिए आवश्यक तरीके ढूंढना चाहते हैं, बल्कि K नंबर X _{i के} लिए भी तुरंत चाहते हैं। अपने माता-पिता की मदद करें!

इनपुट फ़ाइल का प्रारूप। पहली पंक्ति में तीन पूर्णांक पी , एम और के (1 M पी , एम , के ) 10 ⁵ ) शामिल हैं, जो रिक्त स्थान द्वारा अलग किए गए हैं - पिता के सेट में संख्याओं की संख्या, माता के सेट में संख्याओं की संख्या, और माता-पिता के लिए ब्याज की संख्या क्रमशः। दूसरी पंक्ति में P नंबर A _{i होता है} , जिसे रिक्त स्थान द्वारा अलग किया जाता है - उन संख्याओं का समूह जो पिताजी लाए थे। तीसरी पंक्ति में एम संख्या बी _{i शामिल है} , जिसे रिक्त स्थान द्वारा अलग किया गया है - उन संख्याओं का समूह जो माँ ने लाया था। चौथी पंक्ति में K नंबर X _{i है} , जिसे रिक्त स्थान द्वारा अलग किया गया है - संख्याओं का एक सेट जिसके लिए आपको आवश्यक संख्याओं की गणना करने की आवश्यकता है। सेट ए , बी और एक्स के सभी नंबर पूर्णांक, गैर-नकारात्मक हैं और 65535 से अधिक नहीं हैं।

आउटपुट फ़ाइल स्वरूप। एक नंबर वाली K लाइनों को प्रिंट करें। _I- th लाइन में संख्या, स्थिति में वर्णित नियमों के अनुसार सेट ए और बी से संख्याओं के लिए बिटवाइड और ऑपरेशन को लागू करके संख्या X _i प्राप्त करने के तरीकों की संख्या के बराबर होनी चाहिए।

उदाहरण

stdin	stdout
४ ४ ४ 1 2 3 4 1 2 3 4 1 2 3 4	3 3 1 1
१ २ ३ 0 १ २ 0 1 2	2 0 0

समस्या बी का समाधान

दो ए और बी दिए गए हैं, जिनमें गैर-नकारात्मक पूर्णांक 2 ^{16 तक हैं} । Q प्रश्नों की एक सरणी भी दी गई है, जिसमें 2 ¹⁶ तक की संख्याएँ भी हैं। प्रत्येक क्वेरी k के लिए , यह कहना आवश्यक है कि कितने जोड़े ( i , j ) ऐसे मौजूद हैं जैसे ऐ और बीजे = क्यूके ।

प्रत्येक सरणी में तत्वों की संख्या 100k तक है (हालांकि यह तुरंत स्पष्ट है कि 2 ¹⁶ से अधिक भिन्न नहीं हैं, लेकिन समान को संसाधित किया जाना चाहिए, इसलिए सरणियों को 100k तक होने दें)।

हम सभी अनुरोधों के जवाब पर तुरंत विचार करेंगे।

हम निम्नलिखित संकेतन f ( x , S ) - अनुक्रम S से उन तत्वों के समुच्चय का परिचय देते हैं जिनमें x से सभी बिट्स होते हैं और संभवतः कुछ और (यानी, संख्या y जैसे कि x & y = x )।
ध्यान दें कि यदि एक ( एफ ( एक्स , ए ) और बी x एफ ( एक्स , बी ) , तो ( ए और बी ) और एक्स = एक्स , यानी। ए और बी में एक्स के रूप में सभी समान बिट्स होते हैं, फिर से, संभवतः कुछ अतिरिक्त बिट्स।

आइए g ( x ) सूचकांकों के जोड़े की संख्या ( i , j ) ऐसी है कि A _i & B _j = x , यह देखना आसान है । इस प्रकार, हम उन सभी संभावित जोड़ियों से घटाते हैं, जिनके लिए A _i & B _j > x है ।

बी इनपुट में संख्याओं में बिट्स की अधिकतम संख्या होने दें। तब | f ( x , S ) | सभी एक्स के लिए O (| S | + 3 ^B ) समय में गणना की जा सकती है ( एक्स के बिट्स के सभी सबसेट को एन्यूमरेट करने की विधि का उपयोग करके)। जी ( एक्स ) के मूल्यों की गणना ओ (3 ^बी ) के समय में की जा सकती है, हालांकि, इस मामले में, बिट्स एक्स के सभी सबसेट नहीं, बल्कि सभी सुपरसेट की गणना का उपयोग करना आवश्यक है।

वर्णित समाधान का कुल परिचालन समय हे ( P + M + K + 3 ^B ) ( B = 16) है।

समस्या सी। मधुमक्खियों

समस्या लेखक - जकुबर (जैकब रादोज़्वस्की)
इनपुट फ़ाइल का नाम : स्टडिन
आउटपुट फ़ाइल नाम : stdout
समय सीमा : 5 सेकंड
मेमोरी सीमा : 512 एमबी

मधुमक्खी पालक बैतजार का शौक मधुमक्खियों द्वारा लाए गए शहद से छत्ते में बनने वाले आंकड़ों का अध्ययन है। ऐसा प्रत्येक आंकड़ा पक्ष 1 के साथ हेक्सागोनल कोशिकाओं के एक जुड़े सेट का प्रतिनिधित्व करता है, जिसके अंदर "छेद" नहीं होते हैं।

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

Baytazar संभव परिधि मूल्यों और ऐसे पैटर्न में कोशिकाओं की संख्या की पूरी सूची बनाना चाहता है। उन्होंने आपको एक प्रोग्राम लिखने के लिए कहा, जिसमें दो दिए गए संख्याओं n और p का उपयोग करते हुए पता चलता है कि क्या "छिद्रों" के बिना कोई आकृति मौजूद है जिसमें n कोशिकाएँ शामिल हैं जिनकी परिधि p है ।

उदाहरण के लिए, नीचे चित्र में, n = 4, और p = 18।



इनपुट फ़ाइल का प्रारूप। इनपुट की पहली पंक्ति में परीक्षण मामलों की संख्या T (1 ≤ T ) 1000) है। अगली टी लाइनों में से प्रत्येक एक परीक्षण उदाहरण देता है और इसमें दो पूर्णांक n और p (1 next n , p required 1000) होते हैं - आकृति का आवश्यक क्षेत्र और परिधि।

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

यदि कई सही उत्तर हैं, तो उनमें से किसी को भी प्रिंट करें।

stdin	stdout
3 ४ १ 18 ३ १ 18 ३ १२	RLRRRRLRLRLRRRRLRL नहीं LRRRLRRRLRRR

समस्या सी का समाधान

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

हम कोशिकाओं की संख्या n को ठीक करते हैं और पी के संभावित मूल्य का अध्ययन करते हैं जैसे कि पी पक्षों के साथ एक बहुभुज मौजूद है। जाहिर है, पी भी होना चाहिए।

यह देखना भी आसान है कि p 4 n + 2 से अधिक नहीं हो सकता है (बहुभुज की परिधि जिसमें पंक्ति में n कोशिकाओं से युक्त और किनारे पर सीमा होती है; हम इस बहुभुज को एक श्रृंखला कहते हैं )।

दूसरी ओर, सामान्य विचारों से यह स्पष्ट है कि न्यूनतम परिधि का बहुभुज एक प्रकार का बड़ा षट्भुज है। औपचारिक रूप से, इसकी परिधि सूत्र द्वारा दी गई है ।

यह पता चला है कि ये प्रतिबंध न केवल आवश्यक हैं, बल्कि पर्याप्त भी हैं।

निर्माण एल्गोरिथ्म इस प्रकार है: हम एक श्रृंखला के साथ शुरू करते हैं जिसमें n कोशिकाएं होती हैं और अधिकतम परिधि होती है। इसके अलावा, जबकि हमारे बहुभुज की परिधि p से बड़ी है, हम बहुभुज की "पूंछ" से एक सेल को हटाते हैं और इस सेल को "हेड" में जोड़ते हैं, परत द्वारा एक बड़ी षट्भुज परत बनाते हैं (चित्रण में तीर 1 देखें)।



यह चाल परिधि को 2, 4 या 6 से कम करती है, इसलिए अंत में हमें परिधि को 2 या 4 से बढ़ाना होगा, कुछ कोशिकाओं को स्थानांतरित करना होगा (उदाहरण के लिए, आंकड़े में तीर 2 के अनुसार "पूंछ" से सेल को आगे बढ़ाना)।

कुछ कार्यान्वयन के लिए, एन के छोटे मूल्यों के लिए मामलों का अलग से विश्लेषण करना आवश्यक होगा, साथ ही ऐसे मामले जब परिधि किसी दिए गए एन के लिए न्यूनतम मूल्य के करीब हो।

समस्या डी। एनी और क्यूब्स

समस्या और विश्लेषण के लेखक रोमन उदोविचेंको हैं।

इनपुट फ़ाइल का नाम : स्टडिन
आउटपुट फ़ाइल नाम : stdout
समय सीमा : 2 सेकंड
मेमोरी सीमा : 512 एमबी

लिटिल एनी को क्यूब्स के साथ खेलना पसंद है। उसके पास एन पोजिशन हैं, एक पंक्ति में व्यवस्थित किया गया है और 1 से एन तक गिना गया है, जिसमें वह क्यूब्स से टॉवर बनाना पसंद करती है।
एक टॉवर कुछ क्यूब्स हैं जो एक दूसरे के ऊपर स्थित हैं। टॉवर की ऊँचाई इसमें घनों की संख्या है। टॉवर संख्या उस स्थिति संख्या से मेल खाती है जिसमें यह टॉवर बनाया जा रहा है।

प्रारंभ में, सभी पद खाली हैं। हर मिनट निम्नलिखित होता है।

1. Anyuta क्रमिक रूप से N - 1 से 1 की संख्या के साथ स्थिति में दिखता है।
2. यदि किसी भी स्थिति में मैं क्यूब्स हो, और टॉवर की ऊंचाई i + 1 में टॉवर की ऊंचाई से अधिक या उसके बराबर हो, तो Anyuta एक को i- वें स्थान से i (1 +) तक मरता है।
3. Anyuta के बाद सभी पदों के माध्यम से देखा है, वह स्थिति 1 नंबर में एक पासा टॉवर को जोड़ता है।

एक उदाहरण है । बता दें कि पदों की संख्या N = 6 है, और टावरों की ऊंचाई 5 0 1 3 4 1 है (नंबर 1 से एन तक बाएं से दाएं)। फिर अगले मिनट में निम्नलिखित होगा।

1. Anyuta स्थिति 5 को देखेगा: इसमें टॉवर की ऊँचाई 4 है, जबकि अगली स्थिति में टॉवर की ऊँचाई 1. है। Anyuta स्थिति 5 से स्थिति 6 में एक व्यक्ति को स्थानांतरित कर देगा। 6. टावरों की ऊँचाई 5 0 1 3 3 2 हो जाएगी ।
2. Anyuta स्थिति 4 को देखेगा: इसमें टॉवर की ऊँचाई 3 है, और अगली स्थिति में टॉवर की ऊँचाई 3 है। Anyuta किसी की मृत्यु को स्थान 4 से स्थिति 5 में स्थानांतरित कर देगा। टावरों की ऊँचाई 5 0 1 2 4 2 हो जाएगी ।
3. स्थिति 3 से स्थिति 4 तक, Anyuta घन को स्थानांतरित नहीं करेगा, क्योंकि स्थिति 4 में टॉवर की ऊंचाई स्थिति 3 में टॉवर की ऊंचाई से अधिक है।
4. पोजीशन 2 से पोजीशन 3 तक कोई भी पुतु को ट्रांसफर नहीं करेगा, क्योंकि पोजीशन 2 में डाइस नहीं हैं।
5. अंत में, स्थिति 1 से स्थिति 2 तक, Anyuta एक मर को स्थानांतरित कर देगा। टावरों की ऊंचाई 4 1 1 2 4 2 के बराबर होगी।
6. इन क्रियाओं के बाद, Anyuta एक क्यूब को स्थिति नंबर 1 में जोड़ देगा, और टावरों की ऊंचाई 5 1 1 2 4 2 के बराबर हो जाएगी।

ऊपर वर्णित उदाहरण में एक मिनट में टॉवर ऊंचाइयों को बदलना

एक बार, एनी खेलने से थक गई थी, और उसने यह गणना करने का फैसला किया कि कुछ निश्चित मिनटों के बाद उसके पास कितने क्यूब्स होंगे। चूँकि अन्नुता अभी भी छोटी है, और बहुत सारे क्यूब्स हैं, उसने मदद के लिए आपकी ओर रुख किया।
औपचारिक रूप से, आपको Q प्रश्नों का उत्तर देने की आवश्यकता है जैसे " B _i मिनट के बाद S _i से F _{i की} संख्या वाले कुल टावरों में कुल कितने क्यूब्स होंगे"। अनुरोध स्वतंत्र हैं: प्रत्येक अनुरोध में यह माना जाता है कि शुरू में सभी पद खाली हैं, और उसके बाद i> B _i मिनट पास होते हैं।

इनपुट फ़ाइल का प्रारूप । इनपुट की पहली पंक्ति में दो पूर्णांक N और Q (2 ≤ N , 10 ¹⁸ , 1 ≤ Q the 100 000) हैं - क्रमशः टावरों के लिए पदों की संख्या और अनुरोधों की संख्या। अगली क्यू लाइनों में से प्रत्येक में तीन पूर्णांक S _i , F _i और B _i (1 next S _{i i} F _i ≤ N , 1 _i B _i ¹⁸ 10 ¹⁸ ) हैं - अनुरोध के लिए आरंभ और अंत की स्थिति और मिनटों की संख्या के बाद समाप्त पांसी क्रियाओं की शुरुआत।

आउटपुट फ़ाइल स्वरूप । Q पंक्तियों को प्रिंट करें, प्रत्येक क्वेरी के लिए एक। प्रत्येक पंक्ति में एक नंबर प्रिंट करें - अनुरोध का उत्तर। इनपुट में दिखाई देने वाले क्रम में अनुरोधों का जवाब दें।

उदाहरण

stdin	stdout
१० ३ १ १ १ १ १० १०० १० १० ११	1 100 2
1,000,000,000,000 2 1 1234 412412314 100000000000 999999999999 1000000000010	1234 900000000006

समस्या डी का समाधान

सबसे पहले आपको यह समझने की आवश्यकता है कि क्यूब्स पदों में कैसे चलते हैं। उदाहरण के लिए, मामला जब N = 5 पर विचार करें।

पहले पांच मिनट में, क्यूब्स स्थिति 1 से एक स्थिति एन तक एक-एक करके "रेंगना" करेगा, जब तक कि एक क्यूब प्रत्येक स्थिति में दिखाई न दे और टावरों की ऊंचाई [1, 1, 1, 1, 1] हो।
छठे मिनट में, क्यूब चौथे स्थान से पांचवें स्थान पर चला जाएगा, क्यूब्स बाईं ओर एक स्थिति को दाईं ओर ले जाएगी, और स्थिति नंबर 1 पर एक नया क्यूब दिखाई देगा: [1, 1, 1, 1, 2]।
सातवें मिनट में, क्यूब्स केवल पदों (3,2,1) से क्रमशः स्थिति (4,3,2) तक जाएंगे, और ऊंचाइयां [1, 1, 1, 2, 2] हो जाएंगी।

आठवें मिनट में, क्यूब्स 1-4: [1, 1, 1, 2, 3] पदों से हट जाएंगे।

सिमुलेशन जारी रखते हुए, हम प्राप्त करते हैं:

• 9 वें मिनट: [1, 1, 2, 2, 3]
• 10 वें मिनट: [1, 1, 2, 3, 3]
• 11 वां मिनट: [1, 1, 2, 3, 4]

एक और 4 मिनट के बाद, टावरों की ऊंचाई बराबर हो जाएगी [1, 2, 3, 4, 5]। एक और 5 मिनट के बाद, ऊँचाई [2, 3, 4, 5, 6] हो जाएगी, एक और 5 ~ - [3, 4, 5, 6, 7] के बाद।

इस प्रकार, निम्नलिखित पैटर्न को नोटिस करना मुश्किल नहीं है:

1. पहले एन मिनटों में, टावरों की ऊँचाई [1, ..., 1, 0, ..., 0];
2. इसके अलावा, टावरों की ऊँचाई का रूप [1, ..., 1, 2, 3, ..., x ], या [1, ..., 1, 2, 3, ..., k - 1, k है । k , k + 1, ..., x ];
3. के बाद टावरों की ऊंचाई की शुरुआत के कुछ मिनट बाद फार्म [1, 2, 3, ..., एन - 1, एन ];
4. उसके बाद, एक सर्कल में सभी टावरों में एक पासा जोड़ा जाता है।

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

टास्क ई। गणितीय जादू

टास्क और रबोर के लेखक ओलेग ख्रीस्तेंको हैं
इनपुट फ़ाइल का नाम : स्टडिन
आउटपुट फ़ाइल नाम : stdout
समय सीमा : 2 सेकंड
मेमोरी सीमा : 512 एमबी

एक बार वसिया गणित ओलंपियाड की तैयारी कर रहा था और सो गया। वासिया ने डेविड ब्लेन का सपना देखा था जिसमें निम्नलिखित कहा गया था:

“अब मैं गणितीय जादू का प्रदर्शन करूंगा। : N , 2 ⁶³ . : - . K < N , 2 ⁶³ , . … , .

: , , , . … , . … , , . !»

, N . .

. N (2 ≤ N ≤ 100) — .

. , — , , — . , 2 ⁶³ — 1.

, , , «Impossible». , .

stdin	stdout
2	Impossible
3	2 2 2 ३ ३ 2 3

E

N = 2 ( K < N , , ). N = 3 — 8, 9, 2, 3 ({222}, {33}, {2}, {3}). , . N = 4 . .

N ≥ 5.

N > 4 2(2 ^{N -3} -1) 2 ^{N -1} (2 ^{N -3} -1) b a .
, 2 ^{N -3} -1, a N , a b . a +1 b +1 . a + 1 = (2 ^{N -2} — 2) + 1 = 2 ^{N — 2} — 1 , b + 1 = 2 ^{N -2} (2 ^{N -2} — 2) + 1 = (2 ^{N -2} ) ² — 2 * 2 ^{N -2} + 1= (2 ^{N -2} — 1) ² , , a + 1 = ( b +1) ² ,
, .

5 ≤ N ≤ 65 .

, q ₁ ,..., q _k N = k, q _k = r ₁ · r ₂ , q ₁ ,..., q _k-1 , r ₁ , r ₂ N =k+1 ( b { q _k } r ₁ r ₂ ). ( a +1) , ( b +1) .

2 ^{N -3} — 1 , 2 ⁶³ — 1 , N + 1 N +D — 1 , D — 2 ^{N -3} — 1 . N > 65 2 ^{N -2} — 1 , 2 ⁶³ — 1 .

c N 0 6, N — 2 2, N — 3 3, 2 ^{N -2} — 1 (2 ^{( N -2)/2} — 1)(2 ^{( N -2)/2} + 1) , 2 ^{N -3} — 1 — (2 ^{( N -3)/3} — 1)(2 ^{(2 N -6)/3} + 2 ^{( N -3)/3} + 1) . , N ≤ 95 2 ⁶³ — 1 . , .

N 5 6, N — 2 3, N — 3 — 2, , .

, N = 63 (2 ⁶⁰ -1 , 2 ⁶¹ -1 ), N , 96 0 5 6, 2 ^{N -3} — 1 ( << >>) , , 2 ^{N -2} — 1 . , K a + 1 ( ), K < N . , :

• N = 63 D = 13 , 64 ≤ N ≤ 75 .
• N = 71 D = 7 , N 72 77 .
• N = 77 D = 4 , N 78 81 .
• N = 78 D = 7 , N 79 84 .
• N = 83 D = 11 , N 84 93 .
• N = 90 D = 6 , N 91 95 .
• N = 95 D = 9 , N 96 100 ( 104) .

N ≤ 100.

N = 4

N = 4, , , a + 1 . , , . , , a b , a = x b , x > 1 .

C a + 1 ( b + 1 ):

1. u ² , ~ u ;
2. u ³ , ~ u ;
3. uv ² , uv ;
4. u ³ , u ² .

3 a + 1 = uv ² . b + 1 = uv ; x b + 1 = uv ² , , uv ( v — 1) = b ( x — 1) . uv b , v — 1 b , v > 1 , v — 1 = y b ≥ b nobr>, v ≥ b + 1 . u > 1, uv > v ≥ b + . विरोधाभास।

, u ≠ v , a + 1= u ³ b + 1 = u ² .

1 ( u ² ,~ u ) 2 ( u ³ ,~ u ). a c b .

I. a = x ² y z , b = x y z ;

द्वितीय। a = x ² y ² , b = x y ² ;

III. a = x ³ y , b = x ² y ;

IV. a = x ⁴ , b = x ³ ;

V. = x ² y ² , b = x y ;

छठी। a = x ⁴ , b = x ² ;

सातवीं। a = x ³ y , b = x y ;

VIII. a = x ⁴ , b = x .

II-IV I z = y , z = x z = y = x . , VI V.

I y z t .

1. x ² t + 1 = v ² , x t + 1 = v , x ² t + 1 = x ² t ² + 2 x t + 1. x ² t ² > x ² t ( t > 1), .

2. x ² t + 1 = v ³ , x t + 1 = v . x ² t = x ^3 t ³ + 3 x ² t ² + 3 x t , , x ² t < x ³ t ³ .

V

1. x ² y ² + 1 = v ² . x , y , v > 1.

2. x ² y ² + 1= v ³ , x y + 1 = v . , ( x y ) ³ + 2( x y ) ² + 3 x y 0, x , y > 1.

VII

1. x ³ y + 1 = v ² , x y + 1 = v, x ³ y + 1 = x ² y ² + 2 x y + 1 x y ( x ² — x y ) = 2 . , 2 x y , x > 1 y > 1 .

2. x ³ y + 1 = v ³ , x y + 1 = v . , , x ³ y = x ³ y ³ + ... ( ), y > 1 .

VIII

x ⁴ + 1 x + 1. x ⁴ + 1 = ( x + 1)( x — 1)( x ² + 1) + 2 , , 2 x + 1. , x > 1.

, N = 4 .

F.

— rng58 (Makoto Soejima)
: stdin
: stdout
: 2
: 512

10 ¹⁸ , 0 10 ¹⁸ — 1. 0 5⋅ 10 ¹⁷ , . t ( t > 0) :

• x - t — 1 , t .
• t — 1 , , D x - , ( , y , 10 ¹⁸ | x — y| ≤ D , y - t -1 ), t x -
  .
• x - t .

10 ⁹ + 7 t . , .

. t D (1 ≤ t ≤ 10 ⁹ , 1 ≤ D ≤ 50), .

. — t 10 ⁹ + 7

stdin	stdout
५ १	36
२ ३	1849

F

, . . : 500 000 000 000 000 000+ x - x -.

: , t , . :

0, A .

:

• , .
• x — .
• d (0 < d ≤ D ) , ( x + d )- . d , .
• d A ( x + d )- .

.

, t A .

f ( a ₁ , a ₂ ,..., a _k ) — ,
A ={ a ₁ , a ₂ ,..., a _k }.

{ a ₁ , a ₂ ,..., a _k } , :

• 0-, a ₁ -, ( a ₁ + a ₂ )- — .
• i ( a ₁ +...+a _i +1)- ( a ₁ +...+a _{i -1} + D )- .

f ( a ₁ , a ₂ ,..., a _k ) = 2 ^{a ₁ -1 + a ₁ + a ₂ -D-1 + a ₂ + a ₃ - D -1 +...} .

, f ( a ₁ , a ₂ ,..., a _k ) ( k ≤ T ).

dp [ t ][ a ] ( t ≤ T, a ≤ D ) — f ( a ₁ , a ₂ ,..., a _t-1 , a).

:



1 + dp [1][ D ] +… + dp [ T ][ D ], O(TD) .

, . v _t — ( dp [ t ][0],…, dp [ t ][ D ]) . , v _t+1 = v _t · A t ( A —
( D +1) × ( D +1)).

v ₀ ⋅ ( A + A ² +… + A ^T ) , .

— O( D ³ ⋅ log T ).



. ACM ICPC 2013 (Niyaz Nigmatullin) (mikhailOK), Facebook Hacker Cup, Google Code Jam . 2011, (Petr), - VK Cup 2012 (s-quark) .

, , , , , , . — Google, «» Facebook.