"১০০ গেম" নামে একটি গেম ধরে নিই, যেখানে দুজন খেলাড়ি পালা পালায় ১ থেকে ১০ পর্যন্ত যেকোনো পূর্ণসংখ্যা একটি রানিং টোটালে যোগ করে। যে খেলাড়ি প্রথমে রানিং টোটালকে ১০০ বা তার বেশি করে, সে জয়ী হয়। এখন যদি গেম পরিবর্তন করি যাতে খেলাড়ি পূর্ণসংখ্যাগুলো পুনরায় ব্যবহার করতে না পারে?
উদাহরণস্বরূপ, যদি দুজন খেলাড়ি ১..১৫ সংখ্যাগুলোর একটি কমন পুল থেকে রিপ্লেসমেন্ট ছাড়া পালা পালায় টOTAL ১০০ বা তার বেশি হওয়া পর্যন্ত টেনে।
তাহলে দেওয়া হলো একটি maxChoosableInteger এবং অন্য একটি desiredTotal — নির্ধারণ করুন প্রথম খেলাড়ি জয় বাধ্য করতে পারবেন কিনা, ধরে নিলে দুজনই অপ্টিমালি খেলছে।
আমরা সবসময় ধরে নিতে পারি maxChoosableInteger ২০-এর চেয়ে বড় হবে না এবং desiredTotal ৩০০-এর চেয়ে বড় হবে না। তাই যদি ইনপুট হয় maxChoosableInteger = ২০, desiredTotal = ১১, তবে রেজাল্ট হবে false। প্রথম খেলাড়ি যা বেছে নিতেছে, সে হারে যাবে।
সমাধানের ধাপগুলো:
সাইজ 2^21-এর একটি dp অ্যারে তৈরি করুন
solve() মেথড ডিফাইন করুন, যা n, s, এবং mask নেবে
যদি s <= 0 হয়, তবে false রিটার্ন করুন
যদি dp[mask] != -1 হয়, তবে dp[mask] রিটার্ন করুন
ret := false সেট করুন
i = 1 থেকে n পর্যন্ত লুপ চালান
যদি (mask i বিট রাইট শিফ্ট) আড্ড হয়, তবে
ret := ret OR (inverse of solve(n, s – i, mask XOR 2^i))
dp[mask] := ret
ret রিটার্ন করুন
মেইন মেথড থেকে:
যদি desiredTotal <= 0 হয়, তবে true রিটার্ন করুন
i = 0 থেকে 2^21 পর্যন্ত লুপ চালান dp[i] := -1 সেট করতে
যদি desiredTotal > (প্রথম n সংখ্যার যোগফল) হয়, তবে false রিটার্ন করুন
return solve(n, desiredTotal, 0)
উদাহরণ (C++)
নিচের ইমপ্লিমেন্টেশন দেখুন ভালো বুঝতে −
#include <bits/stdc++.h> using namespace std; class Solution { public: int dp[1 << 21]; bool solve(int n, int s, int mask){ if(s <= 0) return false; if(dp[mask] != -1) return dp[mask]; bool ret = false; for(int i = 1; i <= n; i++){ if(!((mask >> i) & 1)){ ret |= (!solve(n, s - i, (mask ^ (1 << i)))); } } return dp[mask] = ret; } bool canIWin(int n, int desiredTotal) { if(desiredTotal <= 0) return true; for(int i = 0; i < (1 << 21); i++)dp[i] = -1; if(desiredTotal > (n * (n + 1)/ 2))return false; return solve(n, desiredTotal, 0); } }; main() { Solution ob; cout << (ob.canIWin(10,11)); }
ইনপুট
10 11
আউটপুট
0
