পাইথনে প্রথম খেলোয়াড় টার্গেট অর্জন করলে জিতবে কিনা চেক করার প্রোগ্রাম

পাইথনে দুইটি সংখ্যা k এবং target দেওয়া আছে। আমল এবং বিমল একটি গেম খেলছে। প্রতিটি রাউন্ডে আমল ১ থেকে k পর্যন্ত একটি সংখ্যা বেছে নিয়ে টোটাল স্কোরে যোগ করে (শুরু ০ থেকে)। যিনি প্রথমে টোটালকে target-এ পৌঁছান বা তার বেশি করবেন, সে জিতবে। আমল সবসময় প্রথম খেলে। উভয়ই অপ্টিমালি খেললে আমল জিততে পারবে কিনা তা বের করতে হবে।

উদাহরণ

ইনপুট: k = 5, target = 10

আউটপুট: True

কারণ: আমল যদি প্রথমে ৪ বেছে নেয়, তবে বিমল ১, ২, ৩, ৪, বা ৫ যেকোনো বেছে নিলে, আমল পরের ruchে ৫ বেছে নিয়ে ১০ অর্জন করতে পারবে।

এলগরিদম (গেম থিওরি - নিম-লাইক)

এটি একটি ক্লাসিক টেক-অওয়ে গেম (take-away game)। জিতের কন্ডিশন:

if target % (k + 1) != 0:
    return True   # প্রথম খেলোয়াড় জিতে
else:
    return False  # দ্বিতীয় খেলোয়াড় জিতে

পাইথন ইমপ্লিমেন্টেশন

def solve(k, target):
    return target % (k + 1) != 0

k = 5
target = 10
print(solve(k, target))  # Output: True

ইনপুট

5, 10

আউটপুট

True

গাণিতিক ব্যাখ্যা

• প্রতিটি প্লেয়ার ১ থেকে k পর্যন্ত যেকোনো সংখ্যা বেছে নিতে পারে।
• সুরক্ষিত পজিশন (winning positions): যেসব নম্বর থেকে Gegner কে হার নিশ্চিত করা যায়।
• প্যাটার্ন: k+1 এর গুনিতকগুলো हार পজিশন (losing positions)।
  • যদি target % (k+1) == 0, প্রথম খেলোয়াড় হারবে (দ্বিতীয় খেলোয়াড় সবসময় কাউন্টার করতে পারবে যাতে যোগফল k+1 হয়)।
  • অন্যথায়, প্রথম খেলোয়াড় target % (k+1) বেছে নিয়ে জেতে পারে।

উদাহরণ বিশ্লেষণ (k=5, target=10)

• k+1 = 6, 10 % 6 = 4 != 0 -> প্রথম খেলোয়াড় জিতবে
• আমল বেছে নেয় ৪ -> টোটাল = ৪
• বিমল বেছে নেয় x (১-৫) -> টোটাল = ৪+x
• আমল বেছে নেয় ৬-x -> টোটাল = ১০ -> জয়!

এই লজিকটি যেকোনো k এবং target এর জন্য কাজ করে।