ধরুন রিমা নিচের গেমটি খেলেন, যেটি ঢিলেঢালাভাবে কার্ড গেম "21" এর উপর ভিত্তি করে। তাই রিমা 0 পয়েন্ট দিয়ে শুরু করে, এবং K পয়েন্টের চেয়ে কম থাকা অবস্থায় নম্বর আঁকে। এখন, প্রতিটি ড্রয়ের সময়, সে রেঞ্জ [1, W] থেকে এলোমেলোভাবে পয়েন্টের একটি পূর্ণসংখ্যা অর্জন করে, যেখানে W দেওয়া হয়, এবং এটি একটি পূর্ণসংখ্যা। এখন প্রতিটি ড্র স্বাধীন এবং ফলাফলের সমান সম্ভাবনা রয়েছে। রিমা K বা তার বেশি পয়েন্ট পেলে নম্বর আঁকা বন্ধ করে দেয়। আমাদের সম্ভাব্যতা খুঁজে বের করতে হবে যে তার এন বা কম পয়েন্ট আছে?
সুতরাং যদি N =6, K হল 1 এবং W হল 10, তাহলে উত্তর হবে 0.6, যেহেতু রিমা একটি একক কার্ড পায়, তারপর থামে, 10 সম্ভাব্যতার মধ্যে 6টিতে, সে N =6 পয়েন্টে বা তার নিচে। পি>
এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -
- যদি k 0 হয়, অথবা N>=K + W, তাহলে 1 ফেরত দিন
- N + 1 আকারের একটি অ্যারে ডিপি তৈরি করুন, dp[0] সেট করুন :=1
- wsum সেট করুন :=1.0, ret :=0.0
- আমি 1 থেকে N
- রেঞ্জের মধ্যে
- dp[i] :=wsum / W
- যদি i
- যদি i – W>=0, তারপর wsum :=wsum – dp[i - W]
- রিটার্ন রিটার্ন
আরো ভালোভাবে বোঝার জন্য আসুন নিচের বাস্তবায়ন দেখি -
উদাহরণ
#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
