LightOJ 1038 Solution

Race to 1 Again : Solution

আমরা ৬ এর জন্য Expected Value বের করবো.

ধরি, Expected Value হচ্ছে E. এবং ৬ এর divisor গুলা হলো : [১, ২, ৩, ৬] = মোট ৪টি।

৬ কে তার যেকোনো একটা divisor দিয়ে ভাগ দেয়ার probability = ১/৪

ভাগ দেওয়ার পর নতুন সংখ্যাটি = ৬/divisor    [যদি ৩ দিয়ে ভাগ দেয় , নতুন সংখ্যা  = ৬/৩ = ২]

এখানে,

             base case হচ্ছে, E(1) = 0.

তাহলে ৬ এর জন্য Expected Value কে লেখা যায়,

                            

 E(6) = (1/4)*( E(6/1) + 1 ) + (1/4)*( E(6/2) + 1 ) + (1/4)*( E(6/3)

 

                                + 1) + (1/4)*( E(6/6) + 1)

 E(6) =  (1/4) * ( E(6) + 1 + E(3) + 1 + E(2) + 1 + E(1) + 1 )

 4*E(6) = E(6) + E(3) + E(2) + 4

 3*E(6) = E(3) + E(2) + 4

এখানে ৩ এর divisor গুলা হলো : [১, ৩] = মোট ২টি,  তাই

 E(3) = (1/2) * ( E(3/1) + 1) + (1/2) * (E(3/3) + 1 )

    

 E(3) =  (1/2) * ( E(3) + 1 + E(1) + 1 )

 2*E(3) = E(3) + E(1) + 2

        

 E(3) = E(1) + 2

    

 E(3) = 2

আবার ২ এর divisor গুলা হলো : [১, ২] = মোট ২টি,  তাই

   

 E(2) = (1/2) * ( E(2/1) + 1) + (1/2) * (E(2/2) + 1 )

    

 E(2) =  (1/2) * ( E(2) + 1 + E(1) + 1 )

 2*E(2) = E(2) + E(1) + 2

        

 E(2) = E(1) + 2

    

 E(2) = 2

সুতরাং লিখা যায়. 

        E(6) = (2 + 2 + 4) / 3

যদি ভালো করে খেয়াল করো তাহলে দেখবে , 

     E(6) = ( divisor_of(3) + divisor_of(2) + divisor_of(6) ) / (divisor_of(6) - 1 )

Coding Part :

#include<bits/stdc++.h>

#define ld long double

#define N 100000

using namespace std;

vector<int>d[N+5];

ld dp[N+5];

void divisor()

{

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

    {

        for(int j=i;j<=N;j+=i)

            d[j].push_back(i);

    }

}

ld expected_value(int n)

{

    if(n == 1)

        return 0;

    if(dp[n] >= 0)

        return dp[n];

    int cnt = d[n].size();

    dp[n] = cnt;

    for(int i=0;i<cnt-1;i++)

        dp[n] += expected_value(d[n][i]);

    dp[n] = dp[n]/(cnt-1);

    return dp[n];

}

int main()

{

    int t, k = 1;

    cin >> t;

    for(int i=0;i<=N;i++)

        dp[i] = -1;

    divisor();

    while(t--)

    {

        int n;

        cin >> n;

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

        cout << "Case " << k++ << ": ";

        cout << expected_value(n) << "\n";

    }

    return 0;

}