Collecting Bugs

Collecting Bugs

امروز به بررسی مساله Collecting Bugs که یکی از سوالات ACM/ICPC 2004 NEERC Northern Subregional و همچنین یکی از سوالات آخرین مسابقه هفتگی ما بود می پردازم.

صورت سوال

n نوع شیء آبی و از هر کدام به اندازه ی بی نهایت و s نوع شیء زرد و از هر کدام به اندازه ی بی نهایت داریم. هر روز یک شیء آبی و یک شیء قرمز را به تصادف انتخاب می کنیم. هنگامی که از هر نوع شیء آبی حداقل یکی و هر نوع شیء قرمز حداقل یکی انتخاب کرده باشیم دیگر ادامه نمی دهیم. می خواهیم امید ریاضی تعداد روزهایی که به آخر کار می رسیم را پیدا کنیم.

بررسی سوال

طبق تجربه، در چنین مواردی که حداکثر تعداد روزها معلوم نیست، نباید به راه حلی که به ازای هر مقداری احتمال رخداد آن را حساب کرد و جمع حاصل ضرب مقادیر در احتمالات نتیجه را حساب کرد. و باز هم طبق چندین سوال احتمالاتی که تا حالا دیده ام، این گونه مسائل اکثر با برنامه سازی پویا قابل حل شدن می باشند. برای آشنایی و یادگیری بیشتر در باره ی مسائل احتمالاتی در مسابقات برنامه نویسی و دیدن چندین مثال دیگر به مقاله ی Understanding Probabilities سایت Topcoder مراجعه کنید.

فرض کنید $F_{i,j}$ امید ریاضی حالتی باشد که در آن تعداد اشیاء آبی که تا به حال هیچ وقت انتخاب نشده اند i و تعداد اشیاء قرمز که تا به حال هیچ وقت انتخاب نشده اند برابر j باشد. چندین حال برای جفت و داریم:

1 - i = 0 و j = 0 : در این صورت دیگر لازم نیست هیچ روزی ادامه دهیم و جواب برابر با 0 خواهد بود.

2 - i = 0 و j <> 0 : به هر حال باید یک روز انتخاب را انجام دهیم. در این روز به احتمال j/s شیء زردی که قبلا هیچ وقت انتخاب نکردیم را انتخاب می کنیم و در روز های بعد باید با j-1 شی انتخاب نشده ی زرد ادامه دهیم، و با احتمال {s-j}/s یکی از اشیاء زردی را که قبلا انتخاب کردیم را انتخاب می کنیم و در روز های بعد باید با شی انتخاب نشده ی زرد ادامه دهیم. بنابراین $F_{i,j}$ در این حالت برابر خواهد بود با:

$F_{0,j} = 1 + {{j}/{s}} * {F_{0,j-1}} + {{s-j}/{j}} * {F_{0,j}}$

که با ساده کردن معادله ی بالا برای $F_{0,j}$ بدست می آوریم:

$F_{0,j} = F_{0,j-1}+{s}/{j}$

3 - i <> 0 و j = 0 : با استدلالی مشابه حالت قبلی برای این حالت بدست خواهیم آورد:

$F_{i,0} = F_{i-1,0}+{n}/{i}$

4 - i <> 0 و j <> 0 : در این صورت با احتمال {{i}/{n}} * {{j}/{s}} شیء آبی جدید و شیء زرد جدیدی انتخاب خواهیم کرد، با احتمال {{n-i}/{n}} *{{j}/{s}} شیء زرد جدید انتخاب خواهیم کرد ولی شیء آبی جدیدی انتخاب نمی کنیم، … که در این صورت $F_{i,j}$ برابر خواهد بود با:

$F_{i,j} = 1+ {{i*j}/{n*s}}*{F_{i-1,j-1}} + {{{n-i}*{s-j}}/{n*s}}*{F_{i,j}} + {{(n-i)*j}/{n*s}}*{F_{i,j-1}} + {{i*(s-j)}/{n*s}}*{F_{i-1,j}}$

که با ساده کردن معادله ی بالا خواهیم داشت:

$F_{i,j} = {1+F_{i-1,j-1}*i*j+F_{i-1,j}*i*(s-j)+F_{i,j-1}*(n-i)*j}/{s*n-(n-i)*(s-j)}$

کد من برای حل این مساله

#include <iostream>
#include <string>
#include <iomanip>
using namespace std;
int n, s;
double mat[1002][1002];
int main()
{
	cin >> n >> s;
	for(int i = 0; i <= n; i++)
		for(int j = 0; j <= s; j++)
		{
			if(i == 0 && j == 0)
				mat[i][j] = 0;
			else if(i == 0)
				mat[i][j] = mat[i][j-1] + (double)s / j;
			else if(j == 0)
				mat[i][j] = mat[i-1][j] + (double)n / i;
			else
			{
				mat[i][j] = 1 + (mat[i-1][j-1] * (double)(i * j)  +
								mat[i-1][j] * i * (double)(s - j) +
								mat[i][j-1] * (double)(n - i) * j) / (double)(s * n);
				mat[i][j] /= 1 - (double)(n - i) * (double)(s - j) / (s * n);
			}
		}
	cout.precision(4);
	cout.setf(ios::fixed | ios::showpoint);
	cout << mat[n][s] << endl;
	return 0;
}