C++ এ বিজয়ীর ভবিষ্যদ্বাণী করুন

ধরুন আমাদের স্কোরের একটি অ্যারে আছে যা অ-নেতিবাচক পূর্ণসংখ্যা। প্রথম প্লেয়ার অ্যারের উভয় প্রান্ত থেকে একটি নম্বর বাছাই করে তারপর দ্বিতীয় প্লেয়ার এবং তারপরে প্রথম প্লেয়ার ইত্যাদি। প্রতিবার একজন খেলোয়াড় একটি নম্বর বাছাই করলে, সেই নম্বরটি অন্য খেলোয়াড়ের জন্য উপলব্ধ হবে না। সমস্ত স্কোর নির্বাচিত না হওয়া পর্যন্ত এটি চলতে থাকে। যে খেলোয়াড় সর্বাধিক স্কোর পেয়েছে সে জিতেছে। সুতরাং, যদি আমাদের স্কোর অ্যারে থাকে, তাহলে আমাদের ভবিষ্যদ্বাণী করতে হবে যে প্লেয়ার 1 বিজয়ী কিনা।

সুতরাং, যদি ইনপুটটি [1, 5, 233, 7] এর মত হয়, তাহলে আউটপুটটি True হবে, যেমন প্রথম প্লেয়ারটি 1 বেছে নিয়েছে। তারপর দ্বিতীয় প্লেয়ারটিকে 5 এবং 7 এর মধ্যে বেছে নিতে হবে। দ্বিতীয় কোন নম্বরটিই হোক না কেন। প্লেয়ার বেছে নেয়, প্রথম প্লেয়ার, 233 বেছে নিতে পারে। শেষ পর্যন্ত, প্রথম প্লেয়ারের দ্বিতীয় প্লেয়ারের (12) থেকে বেশি স্কোর (234) আছে, তাই প্রথম প্লেয়ার জিততে পারে বলে আমাদের সত্যিকারে ফিরে আসতে হবে।

এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -

যদি n 1 এর সমান হয়, তাহলে −
- প্রত্যাবর্তন সত্য
আকারের একটি অ্যারে প্লেয়ার 1 সংজ্ঞায়িত করুন:n x n, n x n আকারের একটি অ্যারে প্লেয়ার2 এবং n x n আকারের যোগফল।
আরম্ভ করার জন্য i :=0, যখন i
- j শুরু করার জন্য :=0, যখন j করুন
  - player1[i, j] :=-1
  - player2[i, j] :=-1
আরম্ভ করার জন্য i :=0, যখন i
- j শুরু করার জন্য :=i, যখন j করুন
  - যদি আমি j এর মত হয়, তাহলে −
    - যোগফল[i, j] :=arr[i]
  - অন্যথায়
    - যোগফল[i, j] :=arr[j] + যোগফল[i, j - 1]
শুরুর দৈর্ঘ্যের জন্য :=1, যখন দৈর্ঘ্য <=n, আপডেট করুন (দৈর্ঘ্য 1 দ্বারা বৃদ্ধি করুন), করুন −
- আরম্ভ করার জন্য i :=0, যখন i + দৈর্ঘ্য - 1
  - শেষ :=i + দৈর্ঘ্য - 1
  - যদি i + 1 <=শেষ হয়, তাহলে −
    - player1[i, end] :=arr[i] + (যদি player2[i + 1, end] একই হয় - 1, তারপর 0, অন্যথায় player2[i + 1, end])) এবং arr[end ] + (যদি player2[i, end - 1] -1 এর মত হয়, তাহলে, অন্যথায় player2[i, end - 1]))
  - অন্যথায়
    - player1[i, end] :=arr[i]
  - player2[i, end] :=sum[i, end] - player1[i, end]
যখন player1[0, n - 1]>=player2[0, n - 1], অন্যথায় মিথ্যা

উদাহরণ

আরো ভালোভাবে বোঝার জন্য আসুন নিচের বাস্তবায়ন দেখি -

#include <bits/stdc++.h>
using namespace std;
typedef long long int lli;
class Solution {
public:
   lli solve(vector <int> arr, lli n){
      if (n == 1)
         return true;
      lli player1[n][n], player2[n][n], sum[n][n];
      for (int i = 0; i < n; i++) {
         for (int j = 0; j < n; j++) {
            player1[i][j] = -1;
            player2[i][j] = -1;
         }
      }
      for (int i = 0; i < n; i++) {
         for (int j = i; j < n; j++) {
            if (i == j) {
               sum[i][j] = arr[i];
            }
            else {
               sum[i][j] = arr[j] + sum[i][j - 1];
            }
         }
      }
      for (int length = 1; length <= n; length++) {
         for (int i = 0; i + length - 1 < n; i++) {
            lli end = i + length - 1;
            if (i + 1 <= end)
               player1[i][end] = max(arr[i] + (player2[i + 1][end] == -1 ? 0 : player2[i + 1][end]), arr[end] + (player2[i][end - 1] == -1 ?: player2[i][end - 1]));
            else
               player1[i][end] = arr[i];
               player2[i][end] = sum[i][end] - player1[i][end];
            }
         }
         return player1[0][n - 1] >= player2[0][n - 1];
      }
      bool PredictTheWinner(vector<int>& nums) {
         return solve(nums, nums.size()) ;
   }
};
main(){
   Solution ob;
   vector<int> v = {1, 5, 233, 7};
   cout << (ob.PredictTheWinner(v));
}

ইনপুট

{1, 5, 233, 7}