C++-এ নিউ ২১ গেম সমস্যা সমাধান

মান করুন রিমা একটি গেম খেলছে, যা "২১" কার্ড গেমের ওপর ভিত্তি করে তৈরি। রিমা ০ পয়েন্ট থেকে শুরু করে এবং K পয়েন্টের চেয়ে কম থাকা পর্যন্ত সংখ্যা ড্র করছে। প্রতিটি ড্রয়ে, সে [1, W] রেঞ্জ থেকে র‍্যান্ডমলি একটি পূর্ণসংখ্যা পয়েন্ট পায়, যেখানে W একটি পূর্ণসংখ্যা। প্রতিটি ড্র স্বাধীন এবং ফলাফলগুলোর সমান সম্ভাবনা রয়েছে। রিমা K বা তার বেশি পয়েন্ট পেলে ড্র করা বন্ধ করে। আমাদের বের করতে হবে সে N বা তার কম পয়েন্ট পাওয়ার সম্ভাবনা কত?

যদি N = 6, K = 1 এবং W = 10 হয়, তবে উত্তর হবে 0.6, কারণ রিমা একটি কার্ড পেয়ে থেমে যায়, ১০টি সম্ভাবনায় ৬টি কেসে সে N = 6 পয়েন্ট বা তার কমে থাকে।

এটি সমাধান করার জন্য নিচের ধাপগুলি অনুসরণ করুন −

• যদি k = 0 হয় অথবা N >= K + W হয়, তবে 1 ফেরত দিন
• N + 1 আকারের একটি dp অ্যারে তৈরি করুন, dp[0] := 1 সেট করুন
• wsum := 1.0, ret := 0.0 সেট করুন
• i = 1 থেকে N পর্যন্ত
  • dp[i] := wsum / W
  • যদি i < K হয়, তবে wsum := wsum + dp[i], অন্যথায় ret := ret + dp[i]
  • যদি i - W >= 0 হয়, তবে wsum := wsum - dp[i - W]
• ret ফেরত দিন

উদাহরণ কোড

#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    double new21Game(int N, int K, int W) {
        if(K == 0 || N >= K + W) return 1.0;
        vector <double> dp (N + 1);
        dp[0] = 1;
        double Wsum = 1.0;
        double ret = 0.0;
        for(int i = 1; i <= N; i++){
            dp[i] = Wsum / W;
            if(i < K){
                Wsum += dp[i];
            }else ret += dp[i];
            if(i - W >= 0) Wsum -= dp[i - W];
        }
        return ret;
    }
};

main(){ Solution ob; cout << (ob.new21Game(6, 1, 10)); }

ইনপুট

6 1 10

আউটপুট

0.6