Light OJ: 1163 - Bank Robbery

/**
* H:\Dropbox\Code\lightoj\1163 - Bank Robbery.cpp
* Created on: 2015-02-26-20.16.07, Thursday
* Verdict: Not Solved
* Author: Enamul Hassan
* Comment: This problem gives Runtime Error Verdict if used cin, cout with sync.
* Concept: Let, the given number is X = A - B. Here, B = A/10.
            So, A - A/10 = X
                A - (A-A%10)/10 = X
                10A - A + (A%10) = 10X
                9A = 10X - K , let K = A%10
                A = (10X - K)/9
                A = X + (X - K)/9
            For K equals to 0 to 9, if (X - K)%9 = 0, then A would be a solution.
            If we get a solution for K = 0, then we would also get a solution for
            K = 9 in this case. That means, if X%9 = 0, then there exists two
            solutions: A = X + X//9 - 1 and A = X + X//9.
            Otherwise the only solution would be A = X + X//9, where '//'
            indicates integer division.
**/

#include <stdio.h>
#define ll long long

int main()
{
#ifdef ENAM
//     fread;
// fwrite;
#endif // ENAM
    int t, cas=1;
    ll s, a, now;

//    clock_t begin, end;
//    double time_spent;
//    begin = clock();

    scanf("%d", &t);

    while(t--)
    {
        scanf("%lld", &s);
        printf("Case %d: ",cas++);

        if(s%9==0) printf("%lld %lld\n", s + s/9 - 1, s+s/9);
        else printf("%lld\n", s+s/9);
    }

//    end = clock();
//    time_spent = (double)(end - begin) / CLOCKS_PER_SEC;
//    cerr<<"Time spent = "<<time_spent<<endl;

   return 0;
}

Light OJ: 1289 - LCM from 1 to n

/**
* H:\Dropbox\Code\lightoj\1289 - LCM from 1 to n.cpp
* Created on: 2015-02-26-14.44.24, Thursday
* Verdict: Solved
* Author: Enamul Hassan
* Concept:  We should figure out the primes below n and its highest power below
            or equal to n. It is enough to calculate the result by multiplying
            primes raising the highest powers.
                RESULT = P1^F1 * P2^F2 * ... +* Pm^Fm,
                where P1, P2, ... Pm are primes and F1, F2, ... Fm are the highest
                powers of them respectively.
            Mod operation would be handled by "unsigned int" type automatically.
            An observation is that, only those primes would have power greater
            than one which are below or equal to square root of n. So, its easy
            to calculate the multiplication of all primes below or equal to n.
            Then we would multiply this answer by the primes below or equal to
            square root of n raising to the power one less than the highest power.
            In short,
                RESULT = P1 * P2 * ... +* Pm,
                where P1, P2, ... Pm are primes below or equal to n.
                RESULT = RESULT * P1^(F1-1) * P2^(F2-1) * ... +* Pk^(Fk-1),
                where P1, P2, ... Pk are primes below or equal to square root of
                n and F1, F2, ... Fk are the highest powers of them respectively.
**/

#include <bits/stdc++.h>
#define ll long long
using namespace std;
#define sz 100000100

const int real_size = 5761509;

ll col[sz/64+10];
int prime[real_size], cnt;
unsigned dp[real_size];
void seive()//1 indexed
{
    long long i,j,k;
    for(i=3;i<sz;i+=2)
         if(!(col[i/64]&(1LL<<(i%64))))
                for(j=i*i;j<sz;j+=2*i)
                    col[j/64]|=(1LL<<(j%64));

    prime[cnt++]=2;
    for (int i = 3; i<sz; i+=2)
        if(!(col[i/64]&(1LL<<(i%64))))
            prime[cnt++] = i;
}


unsigned find_sqrt_ans(int x)
{
    int k = sqrt(x), now;
    unsigned ret=1, cnts;
    for (int i = 0; prime[i]<=k; i++)
    {
        now = x/prime[i];
        cnts=1;
        while(now>=prime[i])
        {
            now/=prime[i];
            cnts*=prime[i];
        }
        ret*=cnts;
    }
    return ret;
}


int main()
{
#ifdef ENAM
//     fread;
// fwrite;
#endif // ENAM
    int t, n, m, cas=1;
    unsigned ans;
//    clock_t begin, end;
//    double time_spent;
//    begin = clock();
    seive();
    dp[0]=2;
    for (int i = 1; i<real_size; i++)
        dp[i]=dp[i-1]*prime[i];
    scanf("%d", &t);

    while(t--)
    {
        scanf("%d", &n);
        ans=find_sqrt_ans(n);
        ans*=dp[upper_bound(prime,prime+cnt,n)-prime-1];
        printf("Case %d: %u\n", cas++,ans);
    }


//    end = clock();
//    time_spent = (double)(end - begin) / CLOCKS_PER_SEC;
//    cerr<<"Time spent = "<<time_spent<<endl;

   return 0;
}

Light OJ: 1226 - One Unit Machine

/**
* H:\Dropbox\Code\lightoj\1226 - One Unit Machine.cpp
* Created on: 2015-02-26-12.57.33, Thursday
* Verdict: Solved
* Author: Enamul Hassan
**/

#include <bits/stdc++.h>
#define _ ios_base::sync_with_stdio(0);cin.tie(0);

#define sz 1005
#define ll long long
#define mod 1000000007
ll bigmod(ll sonkha,ll ghat,ll vag_const)
{
    ll vag_shesh=1;
    while(ghat>0)
    {
        if(ghat%2==1)
        {
            vag_shesh=(vag_shesh*sonkha)%vag_const;
        }
        ghat/=2;
        sonkha=(sonkha*sonkha)%vag_const;
    }
    return vag_shesh;
}
ll inverse_mod(ll bivajok, ll vag_const)
{
    return bigmod(bivajok,vag_const-2, vag_const);
}

using namespace std;

int arr[sz];
ll ans, fact[(int)1e6+10];

ll factorial(int x)
{
    if(fact[x]||x==0) return fact[x];
    return fact[x] = ((x*factorial(x-1))%mod);
}


int main()
{
#ifdef ENAM
//     fread;
// fwrite;
#endif // ENAM
    int t,  cas=1;
    ll n, m;
    _
//    clock_t begin, end;
//    double time_spent;
//    begin = clock();

    fact[0]=1;

    cin>>t;

    while(t--)
    {
        ans = 1;
        cin>>n;
        for (int i = 0; i<n; i++)
            cin>>arr[i];
        m = arr[0];

        /**
        *   Lets think about the second sample test. The very basic combination is J1 J1 J2 J2 J3 J3 J3.
        *   If we consider one job, then there would be one combination: J1 J1.
        *   If we add the second job, then very basic combination would be: J1 J1 J2 J2. Here, Last J2
        *   is not movable. So, without it, there are 3 elements. but 2 of them are same. So, 3!/2! would
        *   be multiplied by the previous result.
        *   If we add the third job, then very basic combination would be: J1 J1 J2 J2 J3 J3 J3. Here,
        *   Last J3 is not movable. So, without it, there are 6 elements. but 2 of them are same and 4 of
        *   them are calculated in the previous step. So, 6!/(2!*4!) would be multiplied by the previous
        *   result which is the final result. In this way, other cases could be calculated.
        */
        for (int i = 1; i<n; m+=arr[i++])
            ans = (((((ans*factorial( m+arr[i]-1 ))%mod) *inverse_mod(factorial(arr[i] -1 ),mod))%mod)*inverse_mod(factorial(m),mod))%mod;

        cout<<"Case "<<cas++<<": "<<ans<<"\n";
    }

//    end = clock();
//    time_spent = (double)(end - begin) / CLOCKS_PER_SEC;
//    cerr<<"Time spent = "<<time_spent<<endl;

    return 0;
}

Light OJ: 1077 - How Many Points?

/**
* H:\Dropbox\Code\lightoj\1077 - How Many Points.cpp
* Created on: 2015-02-26-01.22.10, Thursday
* Verdict: Solved
* Author: Enamul Hassan
* Problem Link: http://www.lightoj.com/volume_showproblem.php?problem=1077
**/

#include <stdio.h>
#include <algorithm>

#define ll long long

using namespace std;

int main()
{
#ifdef ENAM
//     fread;
// fwrite;
#endif // ENAM
    int t, cas=1;
    ll a, b, x, y;
//    clock_t begin, end;
//    double time_spent;
//    begin = clock();

    scanf("%d", &t);
    while(t--)
    {
        scanf("%lld %lld %lld %lld", &a, &b, &x, &y);
        /**
        *   At first lets simplify the problem. Lets assume that there exists n lattice points
        *   in between segment AB. If a lattice point breaks down a segment into two, then the
        *   answer = n + 1. we should take the absolute difference of x co-ordinate and y
        *   co-ordinate between these two points. That means we made the scenario originated.
        *   In co-ordinate, one of two points became (0,0). Lets name the new segment as A'B'
        *   Now, think, when does a lattice point come in this case while traversing from A'
        *   to B'? A lattice point comes when we pass an integer amount in x co-ordinate and
        *   at the same time we should pass an integer amount in y co-ordinate. If we found
        *   the first lattice point, then the distance between the lattice point and A' would
        *   be repeated until we reach B' and name this distance d. That means, we would get
        *   the second lattice point if we pass d distance from the first lattice point, third
        *   lattice point would be revealed by second and so on. It can be proved
        *   mathematically that this n is equal to GCD of(difference of x co-ordinate,
        *   difference of y co-ordinate between).
        *   Now, come to the mathematical view. Lets think about the segment A'B'. One of the
        *   two corner points is (0,0) and let the other is (p,q). Now, the equation for this
        *   line is y = (p/q)*x. Here, we should bring p/q to the least possible term. It can
        *   done by taking GCD(p,q) = G and y = ((p/G)/(q/G))*x.  From the points on the
        *   equation y = (p/q)*x, only those points would be counted as lattice points which
        *   are integers and its both x and y co-ordinates are less than p and q respectively.
        *   These points can obtain by  letting G ranging 1 to G in equation y=((p/G)/(q/G))*x.
        *   An example may clear the scenario. Lets consider three cases.
        *           1. (2,3),
        *           2. (4,6) and
        *           3. (6,9)
        *   The equation of these three lines are y = (2/3)*x, y = (4/6)*x and y = (6/9)*x
        *   respectively. Lets take their GCD and make them Least possible term. Here, GCD
        *   equals to 1, 2, 3 respectively and all of them indicates one single line y =
        *   (2/3)*x. But we would count 1, 2, 3 lattice points for the equation no 1, 2, 3
        *   respectively. Our answer is one more than this GCD, because we are missing point
        *   (0,0) in the scenario.
        *   Do some paper work if you could not understand the scenario till now.
        */
        printf("Case %d: %lld\n",cas++,1LL+__gcd(abs(x-a),abs(y-b)));
    }


//    end = clock();
//    time_spent = (double)(end - begin) / CLOCKS_PER_SEC;
//    cerr<<"Time spent = "<<time_spent<<endl;

   return 0;
}

সকল প্রশংসা শুধুমাত্র দুই জগতের স্রষ্টার জন্য

বিসমিল্লাহির রহমানির রহিম।

সকল প্রশংসা একমাত্র আল্লাহ্‌ তায়ালার জন্য যিনি জগতসমূহের রব। আমার প্রতিটি নিঃশ্বাস ওনার এক অফুরন্ত নেয়ামত মাত্র। নশ্বর এ পৃথিবী শুধুমাত্র কিছু বালু কণার জমাটবদ্ধ একটি সাময়িক অবস্থা। তিনি যখন চাইবেন তখনই এটি ধ্বংস করতে পারেন। তিনি যেমন খুশি তেমন বানাতে পারেন, তিনি যেমন খুশি তেমন ভাঙ্গতে পারেন। তার কাছে সব কিছুই অফুরন্ত। মানুষকে তিনি দান করেছেন ছোট্ট এক জীবন, যে জীবনের শেষ হওয়া সময়ের বিষয় মাত্র। মানুষকে তিনি দুর্বল করে পাঠিয়েছেন, কিন্তু দিয়েছেন শক্তিশালী চিন্তা শক্তি, সুন্দর বিবেক। আল্লাহ্‌ তায়ালা সকলকে ওনার দেওয়া নেয়ামতগুলো সঠিকভাবে সঠিক যায়গায় ব্যবহার করার তৌফিক দান করুন।

বিশ্ববিদ্যালয়ে ভর্তির সময়ই একটি ইচ্ছা ছিলো, যা কিছু শিখবো, তার শতভাগকেই একটি সুন্দর লিখিতরূপ দিয়ে প্রকাশ করবো, যাতে করে ওই বিষয়ে শিখার ক্ষেত্রে আমার অনুজরা সহজেই বিষয়টি বুঝতে পারে। কিন্তু ৩য় বর্ষ পর্যন্ত সব সময় এটি চিন্তায়ই থেকে গেলো, খসরাগুলো সুন্দরভাবে লিখার কোন সুযোগ পেলাম না। হয়তো তার অনেক কিছু ভুলেও গিয়েছি। তাই ঠিক করেছি, যা কিছু শিখবো, তার খসরাই প্রকাশ করবো, যাতে করে অন্তত নিজের মনে থাকে জিনিসগুলো, পরে কখনো বিস্তারিত লিখতে গেলে লিখতে পারি।

বিভিন্ন সময় প্রবলেম সল্ভিংয়ের ক্ষেত্রে দেখেছি, বিভিন্ন অনলাইন জাজে জাজ ডাটায় সমস্যা থাকে কিন্তু এজন্য প্রবলেম সল্ভারদের ভুগতে হয়। তাছাড়া একজন প্রাথমিক প্রবলেম সল্ভার যখন একটি সমস্যা অনেক চিন্তা করেও সমাধান করতে না পারে তখন সে অনেক সময় হতাশ হয়ে এ থেকে ফিরে যায়। তাই আমার সল্ভ করা বিভিন্ন অনলাইন জাজের সমসসাগুলোর সমাধান এখানে সংরক্ষণ করবো। যাতে করে প্রাথমিক প্রবলেম সল্ভার কোড দেখে হলেও শিখতে পারে। অসৎ উদ্দেশ্যে কেউ ব্যবহার করলে তার সম্পূর্ণ দায়ভার তার নিজের। অসৎ ব্যক্তিদের আধিপত্য খুবই ক্ষণস্থায়ী এবং এর পরিণাম ভয়াবহ, আমার ছোট্ট এ জীবনেই তা বারবার প্রমাণিত হতে দেখেছি।

আমি যদি কোন কিছু পারি সে ব্যাপারে সহযোগিতা করতে কখনো আমি বিন্দুমাত্র কার্পণ্য করি না। কেউ যদি জানেন যে আমি একটা জিনিস জানি, আর আপনার যদি তা জানার বা বুঝার দরকার হয়, তাহলে অবশ্যই আমাকে ই-মেইল করবেন, ইনশা-আল্লাহ, আমি আন্তরিকভাবে চেষ্টা করবো আপনাকে সহযোগিতা করতে। আর যদি আমি জানি কিনা নিশ্চিত না হন, তাও ই-মেইল করতে পারেন, জানলে অবশ্যই জানানোর চেষ্টা করবো।

অসংখ্য ধন্যবাদ সবাইকে। আল্লাহ্‌ সবাইকে ভালো রাখুন।

আল্লাহ্‌ হাফিজ।