LightOJ 1248 Solution

Dice (III) : Solution

একটা n sides dice দেওয়া থাকবে। আমাদের বের করতে হবে, Dice এর প্রত্যেকটা side at least একবার করে পেতে হলে গড়ে(Expected) কয়বার Dice টাকে throw করতে হবে?

ধরি, n sides Dice throw এর এক পর্যায়ে আমরা Dice এর x টা side এখনো পাই নাই তাহলে অবশিষ্ট (n - x) টা sides already আমরা পেয়েছি।

আমরা না পাওয়া Dice এর x টা sides পেতে চাই। 

ধরি, x টা sides পেতে Expected number of throw হলো f(x).

এখন আমরা dice টা যদি throw করি তাহলে দুইটা ঘটনা ঘটতে পারে : 

১. যে sides গুলা আগে পেয়ে ছিলাম তার মধ্যে থেকে যেকোনো একটা আবার পেতে পারি, ফলে Expected number of throw এর কোনো Change হবে না। 

যার Probability হলো = (n - x )/n

২. আর যদি নতুন একটা sides পাই যা আগে পাই নাই তাহলে Expected number of  throw ১ কমে যাবে| নতুন Expected number of throw হবে f(x-1). 

যার Probability হলো = x/n

যা উপরের ছবির মতো

সুতরাং আমরা লিখতে পারি  Expected number of throw,

                

                 f(x) = (n-x)/n * f(x) + (x/n) * f(x-1) + 1

                 f(x) - (n-x)/n * f(x) = 1 + (x/n) * f(x-1)

                 f(x) * (1 - (n-x)/n) = 1 + (x/n) * f(x-1)

            

                 f(x) * (x/n) = 1 + (x/n) * f(x-1)

                 f(x) = (n/x) + f(x-1)

উপরের সমীকরণ অনুযায়ী যদি আমাদের n টা (n = 0, 1, 2,  3, 4......) sides এর একটা dice দেওয়া থাকে এর প্রত্যেকটা side একবার করে পেতে হলে Expected number of throw আমরা লিখতে পারি,

  

                  f(0) = 0

                  f(1) = 1/1

                  f(2) = 2/1 + 2/2

                  f(3) = 3/1 + 3/2 + 3/3

                  .

                  .

                  .

                  .

                  f(n) = n/1 + n/2 + n/3 + n/4 + ............... + n/n

Coding Part :

#include<bits/stdc++.h>

using namespace std;

int main()

{

    int t, k = 1;

    cin >> t;

    while(t--)

    {

        int n;

        cin >> n;

        double ans = 0;

        cout << showpoint << fixed << setprecision(10);

        for(int i=1;i<=n;i++)

            ans += (double)n/(double)i;

        cout << "Case " << k++ << ": " << ans << "\n";

    }

    return 0;

}