At Coder Educational DP-J | DP Series(Episode-12)

 Problem Description here

Problem: এই প্রব্লেমে তোমাকে n সংখ্যক থালা দেয়া হবে। প্রতিটি থালা তে ১টি, ২টি অথবা ৩টি করে খাবার থাকবে। যতোক্ষণ না পর্যন্ত সবগুলো থালার সবগুলো খাবার শেষ না হয় ততোক্ষণ পর্যন্ত তুমি

একটি ছক্কার গুটি নিক্ষেপ করবে যেখানে 1 to n পর্যন্ত সংখ্যাগুলো দেখানোর সম্ভাব্যতা সমান। ছক্কা নিক্ষেপে যদি i সংখ্যাটি উঠে তাহলে তুমি i তম থালার একটি খাবার খাবে। যদি i তম থালায় কোন খাবার না থাকে তাহলে কিছুই করা লাগবে না।

তোমাকে বলতে হবে সবগুলো থালার সব খাবার শেষ করতে এক্সপেক্টেড কত সময় লাগবে? 

এই প্রব্লেমটি সলভ করতে Expected Value সম্পর্কে জানা জরুরী। 

Recursive Solution:

	#include<bits/stdc++.h>
	using namespace std;
	int n,ara[305];
	double dp[301][301][301];
	/** State-1: Number of index i such that a[i] = 1;
	State-2: Number of index i such that a[i] = 2;
	State-3: Number of index i such that a[i] = 3; **/
	double FuN(int cnt1,int cnt2,int cnt3)
	{
	if(cnt1+cnt2+cnt3 == 0)
	return 0.0;
	if(dp[cnt1][cnt2][cnt3] > 0.0)
	return dp[cnt1][cnt2][cnt3];
	int tot = cnt1+cnt2+cnt3;
	int zero = n - tot;
	int denom = n - zero;
	int opt = 0;
	double ret1=0.0 , ret2=0.0 , ret3=0.0;
	if(cnt1 > 0){
	ret1 = (n*1.0) + 1.0 * tot * FuN(cnt1-1 , cnt2 , cnt3);
	ret1 /= denom;
	ret1 *= cnt1;
	}
	if(cnt2 > 0){
	ret2 = (n*1.0) + 1.0 * tot * FuN(cnt1+1 , cnt2-1 , cnt3);
	ret2 /= denom;
	ret2 *= cnt2;
	}
	if(cnt3 > 0){
	ret3 = (n*1.0) + 1.0 * tot * FuN(cnt1 , cnt2+1 , cnt3-1);
	ret3 /= denom;
	ret3 *= cnt3;
	}
	return dp[cnt1][cnt2][cnt3] = (ret1 + ret2 + ret3)/tot;
	}
	void Solve()
	{
	int cnt[4] = {0 , 0 , 0 , 0};
	double ans;
	cin>>n;
	for(int i=1 ; i<=n ; i++){
	cin>>ara[i];
	cnt[ara[i]]++;
	}
	ans = FuN(cnt[1] , cnt[2] , cnt[3]);
	printf("%0.10f\n",ans);
	}
	int main()
	{
	Solve();
	return 0;
	}

view raw Episode-12.1.cpp hosted with ❤ by GitHub

Next Episode