समस्या पर विचार करें "Robot Programming Strategy" Google Code Jam 2019 से, राउंड 1C . समाधान अंत में बताता है कि

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

हालांकि, मुझे ऐसा लगता है कि यह गलत है, क्योंकि अलग-अलग चालें जरूरी नहीं कि अलग-अलग विरोधियों को खत्म कर दें।

उदाहरण के लिए विरोधियों "आरआर" और "पीपी" को लें और विश्लेषण में वर्णित समाधान पर विचार करें: हमारा कार्यक्रम "पीपी" होगा, लेकिन यह सच नहीं है कि 2 चालों के बाद हमारा कार्यक्रम सभी विरोधियों को हटा देता है। उत्तर "असंभव" होना चाहिए।

मेरा सवाल है: क्या आप सहमत हैं कि अंत में हमें यह भी जांचना चाहिए कि हमारा कार्यक्रम वास्तव में हर एक प्रतिद्वंद्वी को हराता है, और यदि नहीं तो हमें "असंभव" का जवाब देना चाहिए?

2
Federico 7 जिंदा 2020, 12:26

1 उत्तर

सबसे बढ़िया उत्तर

आपको उन लोगों को बाहर करना चाहिए जिन्हें पहले ही समाप्त कर दिया गया है। तो उदाहरण के लिए आप देते हैं - "आरआर" और "पीपी", अनुक्रम "पीएस" उन दोनों को हरा सकता है।

यह लालची एल्गोरिथ्म इस तरह से काम करता है:

Opponent 1 : RR
Opponent 2 : PP
Me         :

"पी" चुनें क्योंकि यह सभी के लिए टाई या जीत सकता है।

Opponent 1 : RR
Opponent 2 : PP
Me         : P

विरोधी 1 पहली चाल से हटा दिया गया है। अब केवल "P" बचा है इसलिए मैं "S" चुनता हूँ।

Opponent 2 : PP
Me         : PS

% Nit: विरोधियों की संख्या 2^K-1 होनी चाहिए।

1
Hanjoung Lee 7 जिंदा 2020, 10:26