मान लीजिए हमारे पास एक सरणी height है। n अलग-अलग टावर हैं जिनकी अलग-अलग ऊंचाई है। अमल और बिमल एक गेम खेल रहे हैं। गेम के नियम इस प्रकार हैं:
अमल हमेशा पहले खेलता है
प्रत्येक चाल के दौरान, वर्तमान खिलाड़ी ऊंचाई X के एक टावर को चुनता है और इसे Y अलग-अलग टावरों में तोड़ देता है जिनमें से प्रत्येक की ऊंचाई Z है। [Y*Z = X; X और Y > 1]
जिसके पास कोई चाल नहीं होगी वह गेम हार जाएगा
हमें विजेता का नाम खोजना है।
तो, यदि इनपुट height = [3,1,2] है, तो आउटपुट बिमल होगा, क्योंकि प्रारंभिक ऊंचाई {3,1,2} हैं। यदि अमल टावर 2 की ऊंचाई को ऊंचाई 1 के दो टावरों में तोड़ता है, तो नई ऊंचाई सरणी {3,1,1,1} होगी, बिमल ऊंचाई 3 वाले टावर को तोड़कर ऊंचाई 1 के तीन टावर बना सकता है, इसलिए अमल के पास कोई चाल नहीं होगी और बिमल जीत जाएगा।
इसे हल करने के लिए, हम निम्न चरणों का पालन करेंगे:
- एक फ़ंक्शन util() परिभाषित करें। यह limit लेगा, प्रारंभिक limit मान 10^3+5 है
- result := आकार limit की एक सरणी जिसे 0 से भरा गया है
- i को 2 से limit - 1 तक की रेंज में, करें
- s := एक नया सेट
- j को 1 से i के वर्गमूल के फ्लोर तक की रेंज में, करें
- d := i/j का भागफल, r := i/j का शेषफल
- यदि r, 0 के समान है, तो
- यदि j विषम है, तो
- result[d] को s में डालें
- यदि d विषम है, तो
- result[j] को s में डालें
- यदि j विषम है, तो
- j := 0
- जब तक j, s में मौजूद है, करें
- j := j + 1
- result[i] := j
- result लौटाएं
- g := util()
- मुख्य विधि से, निम्न कार्य करें:
- r := 0
- height में प्रत्येक i के लिए, करें
- r := r XOR g[i]
- यदि r शून्येतर है, तो
- "अमल" लौटाएं
- अन्यथा,
- "बिमल" लौटाएं
उदाहरण
बेहतर समझ के लिए निम्न कार्यान्वयन देखें:
def util(limit=10**3+5): result = [0] * limit for i in range(2, limit): s = set() for j in range(1, int(i**0.5)+1): d, r = divmod(i, j) if r == 0: if j & 1: s.add(result[d]) if d & 1: s.add(result[j]) j = 0 while j in s: j += 1 result[i] = j return result g = util() def solve(height): r = 0 for i in height: r ^= g[i] if r: return "Amal" else: return "Bimal" height = [3,1,2] print(solve(height))
इनपुट
[3,1,2]
आउटपुट
Bimal
