प्रोग्रामिंग एल्गोरिदम: प्रतिस्पर्धा के विजेता को ढूंढना

Question

मैं ओबीआई (अंग्रेजी में ब्राजील के ओलंपियाड, अंग्रेजी में) में प्रतिस्पर्धा करूंगा और मैं पिछले वर्षों से कुछ अभ्यास करने की कोशिश कर रहा हूं।

चॉकलेट प्रतियोगिता

कार्लोस और पाउला बस चॉकलेट गेंदों का एक बैग मिला: लेकिन मैं इस अभ्यास (मैं इसे अनुवाद, इसलिए वहाँ कुछ त्रुटियों हो सकता है) के लिए एक समाधान नहीं मिल रहा।

• वे बारी-बारी से खाते हैं, एक के बाद एक (पाउला हमेशा शुरू होता है): के रूप में वे बहुत जल्दी सब कुछ खाने के लिए, वे एक प्रतियोगिता बनाया है।
• हर बार, वे केवल 1 से एम गेंदों से खाते हैं, एम पाउला की मां द्वारा तय किया गया है, इसलिए वे चकित नहीं होते हैं।
• अगर किसी ने अपनी गेंदों में के गेंदों को खा लिया, तो अगला के गेंद नहीं खा सकता है।
• जो भी ऊपर नियमों के अनुसार खेल नहीं सकता है।

एम = 5 और 20 गेंदों के साथ नीचे दिए गए उदाहरण में, कार्लोस जीत लिया है:

Who plays  How many ate  Balls left 

            20 
Paula   5     15 
Carlos   4     11 
Paula   3     8 
Carlos   4     4 
Paula   2     2 
Carlos   1     1 

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

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

टास्क:

आपका काम जानने के लिए कि दोनों बेहतर खेलने जो प्रतियोगिता जीतने जाएगा।

इनपुट:

इनपुट केवल एक ही परीक्षण समूह है, जो मानक इनपुट (आमतौर पर कुंजीपटल) से पढ़ा जाना चाहिए होता है।

इनपुट में 2 पूर्णांक एन (2 ≤ एन ≤ 1000000) और एम (2 ≤ एम ≤ 1000) हैं, एन गेंदों की संख्या और एम प्रति मोड़ की अनुमति है।

आउटपुट:

आपका कार्यक्रम मानक आउटपुट में, प्रिंट चाहिए, विजेता के नाम वाले एक लाइन।

उदाहरण:

Input:   Output: 
5 3    Paula 
20 5   Carlos 
5 6    Paula 

मैं समस्या को हल करने की कोशिश कर रहा हूँ, लेकिन मैं पता नहीं कैसे कर सकते है।

सी में एक समाधान यहां पाया जा सकता है: http://olimpiada.ic.unicamp.br/passadas/OBI2009/res_fase2_prog/programacao_n2/solucoes/chocolate.c.txt लेकिन मैं एल्गोरिदम को समझ नहीं सकता। किसी ने किसी अन्य साइट पर इस समस्या के बारे में एक प्रश्न पोस्ट किया, लेकिन किसी ने जवाब नहीं दिया।

क्या आप मुझे एल्गोरिदम समझा सकते हैं?http://olimpiada.ic.unicamp.br/passadas/OBI2009/res_fase2_prog/programacao_n2/gabaritos/chocolate.zip

Answer 1

मान लें कि हमारे पास बूलियन फ़ंक्शन फर्स्टप्लेयरविन (एफपीडब्ल्यू) है जो दो तर्क लेता है: चॉकलेट की संख्या बाएं (सी) और अंतिम चाल (एल) यानी पिछले दौर में ली गई चॉकलेट की संख्या, जो 0 पर है पहला कदम। नियमित रूप से सही होता है अगर केवल और यदि इस स्थिति में खेलने वाले पहले खिलाड़ी को जीत की गारंटी दी जाती है।

आधार मामला है, अन्यथा FPW (0, एल) = है कि किसी भी एल के लिए गलत है! = 1

FPW (ग, एल) की गणना करने के FPW (ग, एल) सच है किसी भी एक्स के लिए करता है, तो < = एम, एक्स < = सी, एक्स! = एल, एफपीडब्ल्यू (सी - एक्स, एक्स) गलत है। अन्यथा यह झूठा है। यह वह जगह है जहां गतिशील प्रोग्रामिंग kicks, क्योंकि अब एफपीडब्ल्यू की गणना सी के छोटे मूल्यों के लिए एफपीडब्ल्यू की गणना करने के लिए कम हो जाती है।

हालांकि, इस फॉर्मूलेशन के लिए प्रविष्टियों को संग्रहीत करने के लिए एन * एम टेबल प्रविष्टियों की आवश्यकता होगी, जहां समाधान के रूप में आपने केवल 2 एन टेबल प्रविष्टियों का उपयोग किया है।

इसका कारण यह है कि यदि एफपीडब्ल्यू (सी, 0) सत्य है (चॉकलेट गिनती सी पर कोई भी चाल उपलब्ध है तो पहला खिलाड़ी जीतता है) लेकिन एफपीडब्लू (सी, एक्स) एक्स> 0, एफपीडब्लू (सी) के लिए गलत है , वाई) के लिए और वाई! = एक्स सच होना चाहिए। ऐसा इसलिए है क्योंकि यदि चाल x को अस्वीकार करने से खिलाड़ी हार जाता है, यानी खिलाड़ी केवल x खेलकर जीत जाएगा, तो चाल x को तब उपलब्ध किया जाएगा जब y को प्रतिबंधित किया गया हो। इसलिए किसी भी गिनती के लिए किसी भी गिनती 'सी' के लिए स्टोर करना पर्याप्त है जो खिलाड़ी को वहां खोने का कारण बनता है। तो आप गतिशील प्रोग्रामिंग समस्या को दोबारा कर सकते हैं ताकि पूर्ण 2-आयामी सरणी FPW (c, x) को संग्रहीत करने के बजाय आपके पास दो सरणी हों, एक मान FPW (c, 0) को संग्रहीत करता है और अन्य स्टोरों को एक प्रतिबंधित वर्जित कारण बनाता है जीतने के बजाए हारने वाला पहला खिलाड़ी, यदि कोई हो।

उद्धृत सी प्रोग्राम के सटीक पाठ को आप कैसे प्राप्त करते हैं पाठक के लिए एक अभ्यास के रूप में छोड़ दिया जाता है।

Answer 2

मुझे लगता है कि यह अभी तक गतिशील प्रोग्रामिंग में एक और बारीकी प्रच्छन्न व्यायाम है:

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

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

मैंने सभी असम्बद्ध उदाहरण कोड के माध्यम से काम नहीं किया है, लेकिन ऐसा लगता है कि यह ऐसा कुछ कर सकता है - एक गतिशील प्रोग्रामिंग का उपयोग करके तालिका बनाने के लिए रिकर्सन का उपयोग करना।