Competitive Programming : July 2017

Friday, July 21, 2017

1048. Superlong Sums Timus Problem Solution & Logic

http://acm.timus.ru/problem.aspx?space=1&num=1048

এটা খুবই সোজা একটি প্রোবলেম , তোমায় ২ টা বিশাল বড় সংখ্যা যোগ করতে হবে , তোমায় সংখ্যা দুটি'র ডিজিট আলাদা করে দেয়া থাকবে । যেমন ,
   0 4
                                                       4 6
   6 5
   7 1

তাহলে , তোমায় - তোমায় বুঝতে হবে 4651+0467=? তাহলে , এখানে আমরা একটা Array আগেই Declare করে নিবো - ও ইনপুট নেবার সময়ই ডিজিট গুলো যোগ করে Array তে ধুকিয়ে নিবো । তাহলে
যদি , Array টি'র নাম a হয় - তাহলে , কি হবে ? চলো দেখি ----------
   a[0]=4    ;
                                                               a[1]=10 ;
   a[2]=11 ;
   a[3]=8    ;
এখন আরো কিছু , কারুকাজ তো বাকিই থেকে গেলো - যে ঘর গুলোতে যেমন , a[1]=10 , a[2]=11 তে এক এর অধিক ডিজিট আছে , কিন্তু - যোগ করার সময় তো - আমরা , ডান এর ডিজিট'টা লিখি ও বাম পাশের ডিজিট তো হাতে রেখে দেই , যেটা পরেরটার সাথে যোগ করি , তাই না ?? তাহলে এই কাজ'টি করবার জন্য আরো একটি লুপ চালিয়ে একদম শেষ থেকে দেখবো , a এর কোন ঘরে দুইটা ডিজিট আছে - সেখানে ডান পাশের ডিজিট'টা রেখে , বাম পাশের'টা পরেরটার সাথে যোগ দিবো । তো চলো , কোড'টা দেখে ফেলি - আর হ্যা , একটা বিষয় মাথায় রাখা প্রয়োজন ,যে - scanf & printf সাধারনত cin&cout এর চেয়েও , দ্রুত কাজ করে ,তাই আমরা এটাই ব্যবহার করবো - অন্যথায় TLE খাবার সম্ভাবনা আছে ।

#include <stdio.h>

char a[1000000];

int N,x,y;

int main(){
    scanf("%d",&N);

    for(int i = 0; i<N;++i){
        scanf("%d %d",&x,&y);
        a[i] = x+y;
    }

    for(int i=N-1;i>0;--i){
        a[i-1] += a[i]/10;
        a[i] %= 10;
    }

    for (int i = 0 ; i<N ; ++i)
    {
        printf("%d",a[i]);
    }

    return 0;
}

Thursday, July 20, 2017

1068 (Sum) Timus Problem Solution & Logic

https://timus.spatarel.ro/problem.aspx%3Fspace=1&num=1068

খুবই সহজ , একটা প্রোবলেম । তোমাকে , N এর মান দেয়া থাকবে ।তোমায় ১ থেকে N অবদি সকল নাম্বার যোগ করে , তার যোগফল দিতে হবে । N যদি , পসিটিভ হয় - তাহলে তো কথাই নেই - (N*(N+1))/2 সুত্র খাটাবো , এখন যদি - N এর মান নেগেটিভ হয় , তাহলে - কি করবে ??
ধরো , দেয়া থাকলো - N = -5, তাহলে- তোমায় যোগ করতে হবে ,১ + -১ + -২ + -৩ + -৪ + -৫ । এখন ,
-১ + -২ + -৩ + -৪ + -৫ যোগ করার সুত্র হইলো - N*(1-N)/2 ,কিন্তু - ১ যেহেতু যোগ থাকবেই , সুতরাং
সুত্রটি হবে -    1+ N*(1-N)/2 | চলো , কোড দেখি ফেলি ----

#include<iostream>
#include<cstdio>

using namespace std;

//Nayeem Mollick Joy ,Applied Physics & Electronic Engineering ,University of Rajshahi.

    int main ()
{
    int n;

    while ( scanf ("%d", &n) != EOF ) {

        int sum=0;

        if ( n <= 0 ) {
            sum=(n*(1-n)/2)+1;
        }
        else {
            sum=(n*(n+1))/2;
        }

        printf ("%d\n", sum);
    }

    return 0;
}

1001. Reverse Root Timus Problem Solution & Logic

http://acm.timus.ru/problem.aspx?space=1&num=1001

অনেক সোজা একটা প্রোবলেম , শুধু দেয়া সংখ্যার বর্গমূল করতে হবে ও দশমিকের পর চার ঘর অবদি প্রকাশ করতে হবে , চলো কোড দেখি -

#include<iostream>
#include<cstdio>
#include<cmath>
#include<vector>
#include<algorithm>
#include<iomanip>

using namespace std;

//Nayeem Mollick Joy ,Applied Physics & Electronic Engineering ,University of Rajshahi.

int main()

{
    vector<double> v;

    double n;

    while(cin>>n) v.push_back(n);

    for(int i=v.size()-1;i>=0;i--) cout<<setprecision(4)<<fixed<<sqrt(v[i])<<endl;

    return 0;
}

1785. Lost in Localization Timus Problem Solution & LOgic

http://acm.timus.ru/problem.aspx?space=1&num=1785

এটা শুধু if & else if এর খেলা ছাড়া আর কিছুই নয়।

প্রশ্নের টেবিলের শরতগুলো if & else if ব্যবহার করে সাজিয়ে ফেলো , তাই হবে - চলো কোড দেখি

#include<bits/stdc++.h>

using namespace std;

//Nayeem Mollick Joy ,Applied Physics & Electronic Engineering ,University of Rajshahi.

   int main()
{
int n;
while(cin>>n)
{
      if(n>=1&&n<=4)
      {
          cout<<"few"<<endl;
      }
      else if((n>=5&&n<=9))
      {
          cout<<"several"<<endl;
      }
      else if(n>=10&&n<=19)
      {
          cout<<"pack"<<endl;
      }
      else if((n>=20&&n<=49))
      {
          cout<<"lots"<<endl;
      }
      else if(n>=50&&n<=99)
      {
          cout<<"horde"<<endl;
      }
      else if(n>=100&&n<=249)
      {
          cout<<"throng"<<endl;
      }
      else if(n>=250&&n<=499)
      {
          cout<<"swarm"<<endl;
      }
      else if(n>=500&&n<=999)
      {
          cout<<"zounds"<<endl;
      }
      else if(n>=1000&&n<=2000)
      {
          cout<<"legion"<<endl;
      }
}
return 0;
}

1293. Eniya Timus Problem Solution & Logic

http://acm.timus.ru/problem.aspx?space=1&num=1293

বাচ্চা লেভেলের একটা প্রশ্ন । তোমায় , একটা আয়তাকার - প্যানেল দেয়া আছে , যার দৈ্ঘ্য ও প্রস্থ
A & B meters দেয়া আছে , ধরো - বলা আছে যে - প্যানেলটি'র ১ বর্গএকক রঙ করতে ১
ন্যানোগ্রাম রং লাগে । তাহলে , প্যানেলটির উভয় পাশে রঙ করতে কতটুকু রঙ লাগবে ??
তাহলে , আয়তাকার প্যানেলটির ক্ষেত্রফলের সমান রঙ লাগবে , বুঝাই যাচ্ছে ও যেহেতু - দুই পাশে বলেছে - সুতরাং ২ দিয়ে গুণ করতে হবে । তাহলে , ১ টা প্যানেলের উভয় পাশে রঙ করতে লাগবে -
2*A*B ন্যনোগ্রাম রঙ , তাই না ?? এখন , প্যানেলের সংখ্যাও দেয়া থাকবে - সুতরাং , সেটা দিয়ে 2*A*B কে গুণ করলেই , মোট পরিমাণ পাওয়া যাবে । চলো কোড দেখি ----

#include<iostream>
#include<cstdio>

using namespace std;

//Nayeem Mollick Joy ,Applied Physics & Electronic Engineering ,University of Rajshahi.

int main()

{
    int n,b,c;
    cin>>n>>b>>c;
    cout<<2*n*b*c<<endl;
    return 0;
}

DCP-82: Chicken Lover Devskill Problem Solution & Logic

https://www.devskill.com/CodingProblems/ViewProblem/82

বাচ্চা একটা প্রোবলেম , তোমায় কিছু সংখ্যা দেয়া থাকবে । যদি , কোনো সংখ্যা - ১২০ বা ১২০ এর বেশী হয় , তাহলে - প্রিন্ট করবে - Good Boy Sifat আর না হলে - প্রিন্ট করবে , Naughty Boy Sifat
চলো - কোড দেখি , এবার ।

#include<iostream>

using namespace std;

int main()

{
    cin.tie(0);

    ios::sync_with_stdio(0);

   int t;
   cin>>t;
   int sum,n;
   while(t--)
   {
       cin>>n;
       if(n>=120)
       {
           cout<<"Good Boy Sifat"<<endl;
       }
       else{
            cout<<"Naughty Boy Sifat"<<endl;
       }
   }
   return 0;

}

In C#......................................

using System;

public class Test

{
    public static void Main()

    {

        int t=Convert.ToInt32(Console.ReadLine());

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

   {
          int n=Convert.ToInt32(Console.ReadLine());
       if(n>=120)

       {
           Console.WriteLine("Good Boy Sifat");
       }

       else{
            Console.WriteLine("Naughty Boy Sifat");
       }
   }

    }
}

DCP-85: Tomorrow is Eid !! Devskill Problem Solution & Logic

https://www.devskill.com/CodingProblems/ViewProblem/85

খুবই সহজ একটা প্রোবলেম , তোমায় বলা হবে - আজ কততম রমজান ? তোমায় বলতে হবে , কাল ঈদ হবার সম্ভাবনা আছে ? নাকি , নাই ??? বুঝতেই , পারছো - যদি , ২৯/৩০ তম রোজা হয় , তাহলেই কেবল কাল রোজা হতে পারে অন্যথায় নয় । চলো , কোড দেখি ---

#include <bits/stdc++.h>
using namespace std;

int main() {

    int n;

    while(cin>>n)

    {

      if(n==29||n==30)

      {

          cout<<"YES"<<endl;

      }

      else

      {
          cout<<"NO"<<endl;
      }

    }
    return 0;
}

Sunday, July 16, 2017

2066. Simple Expression Timus Problem Solution & Logic

http://acm.timus.ru/problem.aspx?space=1&num=2066

মজার একটি প্রোবলেম , তোমায় ছোট থেকে বড় অনুযায়ি তিনটি সংখ্যা দেয়া থাকবে -

তোমায় , সংখ্যা তিন'টির মাঝে - /*/+ চিহ্ন বসিয়ে চেক করে দেখতে হবে - সবচেয়ে কম ,কোন মান'টা আসে ?? ধরো , দেয়া আছে - 1 2 3 , তাহলে - এটাকে 1 - ( 2 * 3) করে প্রকাশ করলেই , কেবল
সবচেয়ে কম মান (- 5) পাবো , সুতরাং - উত্তর = - 5। এখন একটু , চিন্তা করে দেখো - শর্ত অনুযায়ী সবচেয়ে কম মান পাবার জন্য দুই ধরনের ইকুয়েশন ব্যবহার করলেই চলে -

একটা হলো (a-(c*b) এবং আরেকটি (a-b-c) সুতরাং - এই দুইটা ইকুয়েশন এর মধ্যে যেটা সবচেয়ে সবচেয়ে কম হবে ?

 সেটাই হবে , উত্তর । চলো , কোড দেখি এবার -----

#include<bits/stdc++.h>

using namespace std;

// Nayeem Mollick Joy ,Applied Physics & Electronic Engineering ,University of Rajshahi.


   int main()
{

    int a,b,c;
    cin>>a;
    cin>>b;
    cin>>c;
    cout<<min((a-(c*b)),(a-b-c))<<endl;
    return 0;

}

1083. Factorials!!! Timus Problem Solution & Logic

http://acm.timus.ru/problem.aspx?space=1&num=1083

টাইমাস অনলাইন জাজ এর প্রশ্নগুলো - সলভ করতে বেশ মজাই লাগবে , যদি - তুমি বুঝতে পারো ??
না হলে , মাথা খারাপ হয়ে যাবে । এটা , খুবই সহজ একটি সহজ একটি প্রোবলেম - তোমায় একটা সংখ্যা ও কয়েকটি ' ! ' চিহ্ন দেয়া থাকবে । কয়টি , ! চিহ্ন দেয়া থাকবে -- সেটার উপর , তোমার ধারাটি
কেমন হবে ? সেটা ডিপেন্ড করবে ? ? যেমন যদি 10 !!! দেয়া থাকে , তাহলে তোমায় গুণ করতে হবে
10·7·4·1 । কিন্তু , যদি- 10 !! দেয়া থাকে , তাহলে- তোমায় , 10.8.6.4.2 | অর্থাৎ , যে কয়টা ! চিহ্ন থাকবে - ঠিক তত করে ,দেয়া সংখ্যা থেকে কমিয়ে কমিয়ে - গুণ করতে হবে যতক্ষণ না , ১ এর সমান অথবা , এর চেয়ে এক ধাপ বড়'তে না থামে । চলো এবার কোড দেখি ----

#include<bits/stdc++.h>

#define sf scanf
#define pf printf

using namespace std;

//Nayeem Mollick Joy ,Applied Physics & Electronic Engineering ,University of Rajshahi.

   int main()
{

   int n,l,ans=1;

   string x;

   cin>>n>>x;

   l=x.size();

   while(n>1)

   {
       ans=ans*n;
       n=n-l;
       cout<<n<<" ";
   }
    cout<<endl<<ans<<endl;
    return 0;
}

DCP-382: Prime and Even-Odd Devskill Problem Solution & Logic

https://www.devskill.com/CodingProblems/ViewProblem/382

এটা , খুব একটা মজার প্রোব্লেম - সামান্য ব্রেইন খাটালেই হয়ে যাবে , অনেকেই প্রশ্ন পড়ে মনে করবে যে-
প্রাইম সংখ্যাগুলি --- বোধহয় , 10^18 অবদি - জেনারেট করতে হবে , কিন্তু - সেটার কি কোনো প্রয়োজন আছে ?? তোমাকে , N & M এর মান দেয়া থাকবে , তোমায় বলতে হবে - Nতম প্রাইম+ Mতম প্রাইম এর যোগফল , জোড় হবে ? নাকি , বিজোড় হবে ??

এটা করার আগে , কিছু বিষয় - খেয়াল রাখি

১) একমাত্র ২ এমন একটি প্রাইম সংখ্যা , যেটা জোড় ।

২) ২ ছাড়া বাকিসব , প্রাইম বিজোড় - কোনো সন্দেহ নাই ।

৩)কোনো জোড় সংখ্যা +কোনো বিজোড় সংখ্যা = কোনো বিজোড় সংখ্যা ।

( যদি , N & M এর যে কোনো একটার মান 1 হয় - তাহলে , Nতম প্রাইম + Mতম প্রাইম এর যোগফল অবশ্যই বিজোড় হবে,যেহেতু - 1 তম প্রাইম শুধু জোড় , বাকিসব বিজোড় ।    )

৪) কোনো বিজোড় সংখ্যা + কোনো বিজোড় সংখ্যা = কোনো জোড় সংখ্যা ।
অথবা, কোনো জোড় সংখ্যা + কোনো জোড় সংখ্যা = কোনো জোড় সংখ্যা ।

( যদি , N & M এর মান সমান হয় - তাহলে ,Nতম প্রাইম + Mতম প্রাইম এর যোগফল অবশ্যই জোড় হবে / যদি , N & M এর মান সমান নাও হয় তাহলেও , যেহেতু ২ ছাড়া সব প্রাইম বিজোড় তাই , ২টার যোগফলও জোড় হবে । )

#include<bits/stdc++.h>

using namespace std;

//Nayeem Mollick Joy, Applied Physics & Electronic Engineering, University of Rajshahi.

typedef unsigned long long llu;

int main()

{
    llu n,m;

    while(cin>>m>>n)
    {
        if(m==n )
        {
            cout<<"Even"<<endl;
        }
        else if(m==1||n==1)
        {
            cout<<"Odd"<<endl;
        }
        else{
            cout<<"Even"<<endl;
        }
    }
    return 0;
}

DCP-385: Power Of 5 Devskill Problem Solution & Logic

https://www.devskill.com/CodingProblems/ViewProblem/385

খুবই সহজ একটি , প্রোবলেম - তোমাকে একটা সংখ্যা দেয়া থাকবে - তোমায় বলতে হবে - সংখ্যাটিকে
5^X আকারে , প্রকাশ করা যাবে কি না ?? যেখানে , X একটি অঋণাত্বক সংখ্যা ।

যেমন , 625 কে 5^4 আকারে , প্রকাশ করা যাবে । সুতরাং উত্তর হবে হ্যা , আর না হলে- না ।

আমরা আগে কোড দেখি , তারপর - বিভিন্ন অংশ নিয়ে আলোচনা করি , সেটাই বেটার হবে ।

#include<bits/stdc++.h>

using namespace std;

typedef unsigned long long llu;

bool pwr(llu n)
{
    bool ans=false;
    llu x=1,i;
    for(i=0;;i++)
    {
        x=x*5;
        if(x>n)
        {
            break;
        }
        else if(x==n)
        {
            ans=true;
            break;
        }
    }
    if(n==1)
    {
        ans=true;
    }
    return ans;
}

int main()
{
    llu N;
    int T;
    cin>>T;
    while(T--)
    {
        cin>>N;
        if(pwr(N))
        {
            cout<<"YES"<<endl;
        }
        else{
            cout<<"NO"<<endl;
        }
    }
    return 0;
}

আমরা , একটি bool pwr ফাংশন ইউস করেছি , যেটা - বলে দিবে , আমাদের উত্তর হ্যা হবে নাকি , না হবে ??

for(i=0;;i++)
    {
        x=x*5;
        if(x>n)
        {
            break;
        }
        else if(x==n)
        {
            ans=true;
            break;
        }
    }

এই লুপটি , এক এক করে - 5^1=5 , 5^2=25 , 5^3=125, 5^4=625 এভাবে , জেনারেট করতে থাকবে ,
যদি , আমদের দেয়া মান এর সমান হয়ে যায় - তখন

else if(x==n)
        {
            ans=true;
            break;
        }

আমাদের , ans=true করে দিয়ে - লুপ টা ব্রেইক করে দেয় , আর যদি - আমাদের দেয়া মান এর থেকে ,এই লুপ এর ভেতরে যে মান জেনারেট হয় - তার মান বেশী হয় ,তাহলেও -

if(x>n)
        {
            break;
        }

if statement ইউস করে - লুপ কে ব্রেইক করে দেয় । আশা করি , কোড'টি - কোডব্লক্সে, রান করালে
আরো ক্লিয়ার হবে । আর হ্যা, 1 কে কিন্তু, 5^0 হিসেবে - প্রকাশ করা যায় । তাই সেটা , আলাদা করে
লিখে দিয়েছি ।

DCP-374: Bit Need Devskill Problem Solution & Logic

https://www.devskill.com/CodingProblems/ViewProblem/374

মোটামুটি খুব সহজ একটি , প্রোবলেম । বাইনারিতে কিভাবে , কনভার্ট করতে হয় ?? যারা জানে , তাদের জন্য কোনো ব্যপারই না । একটা ডেসিমেল এর সংখ্যাকে - বাইনারিতে রিপ্রেসেন্ট করতে - সর্বনিম্ন কয়টা বিট লাগবে ? মানে , কয়টা ডিজিট দিয়েই আমরা একটা ডেসিমেল সংখ্যাকে বাইনারিতে রিপ্রেসেন্ট করতে পারবো ? চলো , ৭ এর বাইনারি ফর্ম কি হয় ?? একটু দেখে আসি ।

                                 ৭%২ =১ ,
        (৭/২= ৩)          ৩%২=১,
         (৩/২= ১)          ১ %২=১
         (১/২=০)    যেহেতু , ০ পেয়েছি সুতরাং প্রোসেস বন্ধ ।

৭ এর বাইনারি রিপ্রেসেন্ট করতে কমপক্ষে , তিনটি বিট ১১১ লাগছে ।

তাহলে , আমরা - ২ দিয়ে ভাগ করে করে - শুধু ভাগশেষ গুলো নিচ্ছি , যখন ০ হয়ে যাচ্ছে , তখন- বন্ধ করে দিচ্ছি । চলো , এবার কোড দেখি - তবে হ্যা , ০ শূন্য এর বেলায় একটু সাবধান থাকবে

#include<bits/stdc++.h>

//Nayeem Mollick Joy, Applied Physics & Electronic Engineering,University of Rajshahi.

using namespace std;

int main()
{
    int T;
    unsigned long long int x,i;
    cin>>T;
    while(T--)
    {
        i=0;
        cin>>x;
        if(x==0)
        {
            cout<<"1"<<endl;
        }
        else{
        while(x!=0)
        {
            if(x!=0){
            i++;
            }
            x=x>>1;

        }
        cout<<i<<endl;
        }
    }
    return 0;
}

Saturday, July 15, 2017

DCP-330: Power Function Devskill Problem Solution & Logic

https://www.devskill.com/CodingProblems/ViewProblem/330

খুবই সহজ এবং মজার একটি প্রোবলেম । নীচের শর্ত অনুযায়ী কাজ করতে হবে ,

if x is a odd number then f(x) = (-1) * ( 2 ^ x ) , 
Otherwise f(x) = 2 ^ x .

`তোমায় , দেয়া সংখ্যাটি - জোড় নাকি , বিজোড় ?? এটার উপর ভিত্তি করে - আগে মাইনাস / প্লাস বসাতে হবে । পাওয়ার এর কাজটুকু করার জন্য , আলাদা একটা পাওয়ার ফাংশন বানিয়ে নিবে ।`

`এখন কথা হলো , তোমায় একেবারে প্রথম ডিজিট'টা প্রিন্ট করতে হবে । এটা কিন্তু , ১০ দিয়ে ভাগ দিয়ে দিয়েই বের করা যায় । কিন্তু , আমরা কিন্তু - এখানে ,10 ভিত্তিক log ইউস করতে পারি ।`

যেমন , তোমায় যদি বলে --- Log10(1000)=? তাহলে , কি হবে ?? উত্তর হবে , ৩ । মানে , ১০ এর উপরে ৩ হলে , আমরা ১০০০ মান'টি পাবো , এখন আমরা যদি - 1000 কে pow(10,3)/10^3 দিয়ে ভাগ দেই , তাহলে কিন্তু - কতো পাবো ? 1০০০/10^3 = 1 !! এর মানে , প্রথম ডিজিট পেয়ে গেছি , তাই না ?? ঠিক এই কাজটি , আমরা করবো - ধরো , দেয়া আছে - 6 তাহলে , পাওয়ার ফাংশনে হবে - (2^6)=64 |

`এখন , log10(64) করলে , কি মান আসবে ?? 1.8... এরকম কিছু , তাহলে - যেহেতু , আমরা যেহেতু int variable ইউস করবো , সুতরাং মান নিবে 1 হিসেবে .8 নিবে না , অর্থাৎ প্রথম ডিজিট হবে - 64/pow(10,1) = 6 | চলো , এবার কোড দেখি ---`

`#include<bits/stdc++.h> using namespace std;`

//Nayeem Mollick Joy, Applied Physics & Electronic Engineering, University of Rajshahi. typedef unsigned long long llu; llu pow(llu n) { llu x=1,i; for(i=0;i<n;i++) { x=x*2; } return x; } int main() { llu t,N,ans,m,y; cin>>t; while(t--) { cin>>N; m=log10(pow(N)); y=pow(10,m); ans=pow(N)/y; if(N%2==0) { cout<<"+"<<ans<<endl; } else { cout<<"-"<<ans<<endl; } } return 0; }

Friday, July 14, 2017

DCP-196: Break Simulator Devskill Problem Solution & Logic

https://www.devskill.com/CodingProblems/ViewProblem/196

ছোটবেলায় , ত্বরণ ও মন্দন নিয়ে অনেককিছুই পড়েছি , সেই মন্দনেরই একটা প্রোবলেম এটা । একটা , গাড়ি ধরো চলতেছে , কোনো একটা সময়ে ব্রেক কষে - তার কিছুক্ষুন পর , গাড়িটি থেমে যায় - এখন , গাড়ির বেগ   V দেয়া ছিলো ও কত সময় পর ( T ) গাড়ি থামলো , সেটাও দেয়া আছে । তাহলে , কি বলতে পারবে না ? গাড়িটির মন্দন কতো ??? হুম, V/T । মাইনাস দিতে ভুলো না ,আবার ।

চলো , কোড দেখি ---

#include <bits/stdc++.h>

//Nayeem Mollick Joy , Applied Physics & Electronic Engineering, University of Rajshahi.

using namespace std;

int main()

{
   int T;
   double v,t;

   scanf("%d",&T);

   while(T--)

   {
       scanf("%lf %lf",&v,&t);
       printf("-%.02lf\n",v/t);
   }
    return 0;
}

DCP-38: Mysterious Pond Devskill Problem Solution & Logic

https://www.devskill.com/CodingProblems/ViewProblem/38

খুবই মজার একটি প্রোবলেম , কয়েকটা ছেলে - পুকুরে ঝাপ দিয়েছে , তাদের সবার বেগ দেয়া আছে , তোমায় ছেলেগুলোর নাম ও বেগ দেয়া আছে , তোমায় বলতে হবে কার গতি সবচেয়ে বেশি ছিলো ?? আর কার সবচেয়ে কম ছিলো ?? তাদের নাম প্রিন্ট করতে হবে । এখন এই জন্য , আমি STL এর MAP
ইউস করে , সমাধান করেছি । এটা , নোড দিয়েও করা যায় - যদি কেউ করতে চায় । STL জানা না থাকলে , খুব শীঘ্রই এটা শিখে নেয়া উচিত । প্রতিযোগিতা মূলক প্রোগ্রামিং -এ এটা বেশ প্রয়োগযোগ্য ।

                           চলো , কোড দেখি এবার --------

#include<iostream>
#include<cmath>
#include<map>
#include<algorithm>

using namespace std;

//Nayeem Mollick Joy , Applied Physics & Electronic Engineering, University of Rajshahi.

int main()

{
    map<string,int>joy;
    string s,n1,n2;
    int t,a,v;
    cin>>t;
    while(t--)
    {
        cin>>a;
        int i=0,mx=0,mn=1000001;
        while(a--)
        {
            cin>>s>>v;
            joy.insert(make_pair(s,v));
        }
        map<string,int>::iterator itr=joy.begin();
        map<string,int>::iterator jony=joy.end();
        for(itr;itr!=jony;itr++)
        {
            if(mx<(*itr).second)
            {
                n1=(*itr).first;
                mx=(*itr).second;
            }
            if(mn>(*itr).second){
                n2=(*itr).first;
                mn=(*itr).second;
            }
        }
        cout<<n1<<" "<<n2<<endl;
        joy.clear();
    }
    return 0;
}

DCP-65: Magical Bank Devskill Prolem Solution & Logic

https://www.devskill.com/CodingProblems/ViewProblem/65

এটার জন্য , খুব একটা কথা আমি - বলবো না , কারণ - এরকম একটা প্রোবলেম ,ডেভস্কিল-এ এর আগেও একটা আছে , চকলেট এর প্রোবলেম, সেটার লিংক দিচ্ছি - কষ্ট করে বুঝে পড়ে নাও ,
             তাহলে -   এটা কোনো প্রোবলেমই না। শুধু বলবো যে - সারির সংখ্যাটা বের করতে হবে , সুত্র তো জানাই আছে , ((sqrt(1+(8*n)))-1)/2 ।

http://nayeemmollickjoy.blogspot.com/2017/07/dcp-111-chocolates-devskill-problem.html

চলো কোড দেখি এবার ,

#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>

using namespace std;

//Nayeem Mollick Joy, Applied Physics & Electronic Engineering , University of Rajshahi.

int main()
{
    int t,x,i,ans;
    cin>>t;
    while(t--)
    {
        cin>>x;
        ans=ceil(((sqrt(1.0+(8*x)))-1.0)/2.0);
        cout<<ans<<endl;
    }
    return 0;
}

DCP-74: Mobile Key Devskill Problem Solution & Logic

https://www.devskill.com/CodingProblems/ViewProblem/74

খুবই সহজ একটা প্রোবলেম , ১ থেকে ১ করে বাড়তে থাকবে , কিন্তু - প্রতি লাইনে , মাত্র ৩ টি করে সংখ্যা থাকবে , নীচে ধারাটি দেখালাম

                                       1   2  3
                                       6   5  4
                                       7   8  9
                                       12  11 10
                                       13  14 15
                                       and so on...

 এখানে তোমায় N এর মান , দেয়া থাকবে - তোমায় তত তম লাইনের ৩ টা মান প্রিন্ট করতে হবে ।

কি মনে হচ্ছে ?? লুপ খাটালেই তো হয় , তাই না ?? আসলে কি , লুপ খাটানো কি খুব জরুরী ??

উত্তর হবে - না । কারণ , কততম লাইনের মান , বের করবা ?? তত তম লাইনকে , ৩ দিয়ে গুণ দিলেই

সেই লাইনের বড় মান'টি পেয়ে যাবা - তারপর সেখান থেকে , ১ কমিয়ে ২ কমিয়ে মান দুইটি প্রিন্ট করবা ।

বিজোড় নাম্বার লাইন হলে , ছোট মান'টি আগে - তারপর আসতে আসতে বড় মান ও জোড় নাম্বার লাইন হলে,

বড়ো মান'টি আগে , তারপর ১ করে কমাতে কমাতে ছোট মান ।

যেমন,  N = 4 দেয়া আছে , তাহলে - মানগুলি হলো , (3*4)12    (3*4 -1)11   (3*4 - 2)10

খুবই সহজ , তাই না ?? চলো , কোড দেখি -----

#include<iostream>

// Nayeem Mollick Joy,Applied Physics &Electronic Engineering,University of Rajshahi.

using namespace std;

void pattern(unsigned long long int N)
{
    if(N%2==0)
    {
        N=N*3;
        cout<<" "<<N<<" "<<N-1<<" "<<N-2<<endl;
    }
    else
    {
        N=N*3;
        cout<<" "<<N-2<<" "<<N-1<<" "<<N<<endl;
    }
}

int main()

{
   int t;

   cin>>t;

   unsigned long long int N;

   for(int i=1;i<=t;i++)
   {
       cin>>N;
       cout<<"Case #"<<i<<":";
       pattern(N);
   }

   return 0;

}

DCP-210: Gabu and the Series Devskill Problem Solution & Logic

https://www.devskill.com/CodingProblems/ViewProblem/210

                  0, 2, 8, 18, 32, 50, 72, 98......... n.

একটি সিরিজ , প্রথমে - এই সিরিজটির লজিক খুজে বের করতে হবে , তোমায় । ২ ও ৮ এর মাঝে , ডিফারেন্স কতো ?? ৬ তারপর    ৮ ও ১৮ এর মধ্যে ডিফারেন্স ১০ ,    তারপর ৩২ ও ১৮ এর মধ্যে ডিফারেন্স ১৪ ,     ৫০ ও ৩২ এর মধ্যে ডিফারেন্স ১৮    ..........................................
কি বুঝলে , ডিফারেন্স শুরুতে ছিলো ৬ তারপর থেকে ,শুধু ৪ করে বাড়তে শুরু করে দিয়েছে এভাবেই সিরিজটি চলতে থাকবে । তো চলো , সবই তো বুঝলাম , কোড দেখি ------

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define mx 1000001
ll ar[mx];
void series()
    {
        ar[1]=0;
        ar[2]=2;
        int i=3;
        ll p=6;
        while(i<mx){
            ar[i]=ar[i-1]+p;
            p+=4;
            i++;
        }
    }
int main()
    {
        series();
        int t;
        ll n;
        scanf("%d",&t);
        while(t--){
            scanf("%lld",&n);
            printf("%lld\n",ar[n]);
        }
        return 0;
}

DCP-69: Miraclaw and funny sum Devskill Problem Solution & Logic

https://www.devskill.com/CodingProblems/ViewProblem/69

এটা খুবই সহজ একটা প্রোবলেম । Miraclaw নামে , একটা বাচ্চা ছেলে - তার সামনে , কিছু বাস্ক সিরিয়ালি সাজানো আছে বাস্কগুলোর মধ্যে কিছু মারবেল আছে , ছেলেটি -মার্বেল গোনার সময় একটু ভুল করে ফেলে , যেটা যত নাম্বার বক্স সেই সিরিয়াল নাম্বার'টা সেই বাক্সএর মোট মার্বেল বাদ দিয়ে গণনা করে ( তবে , নেগেটিভ হলে নয়) , এভাবে গোনার ফলে - বাক্সে , মোট কতগুলো মার্বেল গুনতে ভুল হবে , সেটাই বের করতে হবে ।

চলো কোড দেখি , আর বেশি কথা বলবো না

#include <bits/stdc++.h>
using namespace std;

int main()

{
   int t;

   cin>>t;

   while(t--)

   {
       int n,a;
       cin>>n;
       int i=0,sum=0,pum=0;
       while(n--)

       {
           cin>>a;
           sum=sum+a;
           if((a-i)>=0)
           {
               pum=pum+(a-i);
           }
           i++;
       }
       cout<<sum-pum<<endl;
   }

   return 0;

}

DCP-243: The 9th Power Devskill Problem Solution & Logic

https://www.devskill.com/CodingProblems/ViewProblem/243

খুবই সহজ একটি বাচ্চা প্রোবলেম ।

তোমায় , N এর মান দেয়া থাকে । তোমায় , বলতে হবে - 9 উপর পাওয়ার N বসালে , যে উত্তর আসবে ,
সেই সংখ্যার শেষ এর ডিজিট কত হবে ?? চলো , ২-৩ টা নাম্বার এর জন্য চেক করে দেখি ---

N=1 , Then ------- 9^1= 9 , Last Digit = 9

N=2 , Then--------9^2=81, Last Digit = 1

N=3 , Then ---------9^3= 729, Last Digit = 9

কি ?? কোনো , সিকুয়েন্স চোখে পড়লো কি ???? হুম , ধরতে পেরেছো -------
           N এর মান জোড় হলে , লাস্ট ডিজিট হবে সবসময় -- ১
           N এর মান বিজোড় হলে , লাস্ট ডিজিট হবে সবসময় --- ৯

চলো , কোড দেখি ----

#include<iostream>

using namespace std;

int main()

{
    int n,t;
    cin>>t;
    while(t--){
    cin>>n;
    if(n%2==0)
    {
        cout<<"1"<<endl;
    }
    else{
    cout<<"9"<<endl;
    }
    }
    return 0;
}

DCP-191: Counting Multiples Devskill Problem Solution & Logic

https://www.devskill.com/CodingProblems/ViewProblem/191
সহজ একটি প্রবলেম , কিন্তু - কে কতটা এফিসিয়েন্ট ভাবে করতে পারবে ? সেটাই দেখার বিষয় .
এই প্রোবলেম এর জন্য একটা বিষয় মাথায় রাখতে হবে ,

তোমায় যদি বলে ? 1 থেকে 100 অবদি 9 এর কয়টি গুণিতক আছে/ কয়টি সংখ্যা 9 দিয়ে নিঃশেষে বিভাজ্য হবে ?? তাহলে , কিন্তু লুপ চালানোর দরকার নেই , ১০০ কে ৯ দিয়ে ভাগ করলেই উত্তর পেয়ে যাবো ।

এখন আসি প্রোবলেম -এ , ধরো তোমায় বললো ৩ ডিজিট এর কয়টি সংখ্যা ৩ দিয়ে নিঃশেষে বিভাজ্য হবে ?? ৩ ডিজিট মানে (10^3 -1) = 999 পর্যন্ত চেক করতে হবে , তাই তো ?? কিন্তু , তুমি যদি - ৯৯৯ কে ৩ দিয়ে ভাগ দেও , তাহলে - একেবারে ১ থেকে ৯৯৯ পর্যন্ত কয়টা ৩ এর গুণিতক ? সেটা বের হবে ।
কিন্তু , আমার তো দরকার শুধু ৩ ডিজিট এর কয়টা সংখ্যা ৩ দিয়ে বিভাজ্য , তার পরিমাণ । তাইলে , কি করা যায় ?? হুম , একটা বুদ্ধি আছে - ( 10^(3-1) -1 ) = 99 পর্যন্ত যে কয়টা ৩ এর গুণিতক আছে , সেটা বের করে - ১ থেকে ৯৯৯ পর্যন্ত কয়টা ৩ এর গুণিতক আছে ,সেটা থেকে বাদ দিলেই কিন্তু - ১০০ থেকে ৯৯৯ পর্যন্ত কয়টি সংখ্যা ৩ এর গুণিতক ? সেটা বের হয়ে যাবে ,অর্থাৎ আমরা ৩ ডিজিট এর কয়টা সংখ্যা ৩ এর গুণিতক ? সেটা পেয়ে যাবো , তাই না ?? চলো , এবার তাহলে ইমপ্লিমেন্ট করে ফেলি - কোড দেখি চলো ------------------

#include<iostream>
#include<cstdio>
#define ll long long

using namespace std;

ll powr(ll a,ll b)
    {
        ll p=1;
        for(int i=0;i<b;i++)p=p*a;
        return p;
    }
int main()
    {
        ll t,n,k,c;
        ll a,b,d,e;
        scanf("%lld",&t);
        while(t--){
            a=0;
            b=0;
            c=0;
            scanf("%lld %lld",&n,&k);
            a=powr(10,n-1);
            b=(a*10)-1;
            d=(a-1)/k;
            e=b/k;
            c=e-d;
            printf("%lld\n",c);
        }
        return 0;
}

DCP-147: Brother's Challange Devskill Problem Solution & Logic

https://www.devskill.com/CodingProblems/ViewProblem/147

এর চেয়ে সহজ প্রোবলেম আর কি হতে পারে ?? তোমাকে , একটা সংখ্যা দেয়া থাকবে , তোমায় বলতে হবে - ১ থেকে সেই সংখ্যার আগ অবদি যে কয়টা সংখ্যা ৩ বা , ৫ দ্বারা নিঃশেষে বিভাজ্য হবে তাদের যোগফল কতো ?? বেশি কিছু বলার নেই , কোড দেখে আসি , চলো ----

#include<iostream>
#include<cstdio>

////Nayeem Mollick Joy , Applied Physics And Electronic Engineering,University Of Rajshahi.

using namespace std;

typedef long long ll;

int main()

{
    int N;

    ll sum=0;

    cin>>N;

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

    {
        if(i%3==0||i%5==0)
        {
            sum=sum+i;
        }
    }
    cout<<sum<<endl;

    return 0;
}

DCP-111: Chocolates Devskill Problem Solution & Logic

https://www.devskill.com/CodingProblems/ViewProblem/111

খুবই সহজ একটি প্রোবলেম ,

                             c
                            c c
                           c c c
                          c c c c
                         c c c c c
                        c c c c c c

তোমাকে কিছু পরিমাণ , চকলেট দেয়া থাকবে ----- উপরোক্তভাবে সাজানোর পর , যে কয়টি চকলেট বাকি থাকবে , সে কয়টা তোমাকে আউটপুটে দেখাতে হবে । এটা খুব সহজেই লুপ চালিয়েই করতে পারবে , কিন্তু - তাতে Time Limit Exceeded খাবার সম্ভাবনা আছে , তাই আমদের সুত্র ব্যবহার করে করতে হবে । 

তোমাকে , দেয়া n সংখ্যক চকলেট দিয়ে কয়টি , এরকম সারি বানানো যাবে - তার একটি , সূত্র আছে ।

সেটা হলো , ((sqrt(1+(8*n)))-1)/2 । এখন কথা হলো , N টি চকলেট দিয়ে - যে কয়টা সারি ,

এই সুত্র দিয়ে বানাতে পারবো । সে কয়টা , সারিতে মোট কয়টা চকলেট থাকবে সেটা বের করতে হবে ,

উপরের সিকুয়েন্স দেখে বুঝতেই পারছো --- প্রতিটি সারিতে চকলেট এর পরিমাণ , আগের সারি থেকে ১ করে বাড়ছে । অর্থাৎ , ১+২+৩+৪ ... এর মানে , যেটা - যততম সারি সেটাতে সে কয়টা চকলেট আছে । 

    তোমায় যদি , দেয়া থাকে N=23 । তাহলে , এরকম সারি - বানানো যাবে ,
         ((sqrt(1+(8*n)))-1)/2 সুত্র অনুযায়ী - মোট 6 টি ।

এখন,এই ৬টি সারিতে মোট চকলেট থাকবে-(৬*(৬+১)/২)=২১টি [ যেহেতু, এটা ১+২+৩+৪+৫+৬ ধারা হবে]

তাহলে , চকলেট দিয়ে এরকম সারি বানানোর পর বাকি থাকবে , মোট 23-21=2 টি । এটাই , আমাদের উত্তর , চলো কোড দেখি এবার 

#include <bits/stdc++.h>

////Nayeem Mollick  Joy , Applied Physics And Electronic Engineering,University Of Rajshahi.

using namespace std;

typedef unsigned long long llu;

int main()

{
    llu n,column=0,total=0;

    int T;

    cin>>T;

    while(T--)

    {
        cin>>n;

         column=((sqrt(1+(8*n)))-1)/2;

         total=(column*(column+1))/2;

         cout<<column<<endl<<n-total<<endl;
    }
    return 0;
}

Wednesday, July 12, 2017

10035 - Primary Arithmetic Uva Problem Solution & Logic

https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=976

ছোট বেলায় আমরা প্রথম যখন যোগ করা শিখি , তখন আমরা হিসেব করতাম হাতে কত থাকে ?? ধরো , যোগ করতে বললো    555 + 555

তাহলে , ডান দিক থেকে শুরু করি - ৫+৫ =১০ বসাবো ০ , হাতে থাকবে ১
                  তারপর ৫+৫ = ১০ এর সাথে হাতে থাকা ১ যোগ করলাম তাহলে হলো ১১ বসাবো ১
     হাতে থাকলো , আবারো ১ ।
তারপর , ৫+৫=১০ এর সাথে হাতে থাকা ১ যোগ করে পেলাম ১১ , বসাই ১ . আবার হাতে থাকে ১ ।।
আর কোনো , কিছু নাই সুতরাং হাতে থাকা ১ বসিয়ে দেই , তাহলে মোট যোগফল পেলাম ১১১০।

এখন এই যোগ করার সময় হাতে থাকার ঘটনা ঘটলো , মোট ৩ বার সেটাই হবে আমাদের উত্তর ।হাতে থাকার এই ঘটনাকে আমাদের প্রোগ্রামের ভাষায় carry বলে । চলো , কোড দেখি ------------

#include<bits/stdc++.h>

// Nayeem Mollick Joy ,Applied Physics & Electronic Engineering , University of Rajshahi.

using namespace std;

int main()
{
   long long int a,b;
   while(cin>>a>>b)
   {
       int carry=0,count=0;
       if(a==0&&b==0)
       {
           break;
       }
       while(a||b)
       {
           carry=(a%10+b%10+carry)/10;    // শেষ এর ডিজিট গুলো যোগ করছি , সেই জন্য ১০ দিয়ে ভাগ করে ভাগশেষ গুলো যোগ করছি //
           a=a/10; // ১ টা করে ডিজিট যোগ করছি , আর - সেটা ১০ দিয়ে ভাগ করলেই যে ভাগফল পাবো , সেটাতে আর শেষ এর ডিজিট'টা থাকছে না , এভাবেই একটা করে ডিজিট কমাতে থাকবো , শেষ এর থেকে //
           b=b/10;
           if(carry) // হাতে , কিছু আছে কি না ?? সেটা চেক করছি , যদি থাকে -তাহলে count এক করে বাড়তে থাকবে //
           {
               count++;
           }

       }

       if(count==0)
       {
           cout<<"No carry operation."<<endl;
       }
       else if(count==1)
       {
           cout<<count<<" carry operation."<<endl;
       }
       else{
       cout<<count<<" carry operations."<<endl;
       }
   }
   return 0;
}

299 - Train Swapping Uva Solution & Logic

https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=235

      খুবই সহজ একটা প্রোবলেম , যদি তুমি বিষয়টা ধরতে পারো ???

বিভিন্নরকম সর্টিং আছে , তার ভেতর বাবল সর্ট খুব জনপ্রিয় , এই প্রোবলেম তারই উদাহরণ ।

বাবল শর্ট জানা না থাকলে , জেনে নাও । চলো কোড দেখে আসি ,

#include<bits/stdc++.h>

// Nayeem Mollick Joy ,Applied Physics & Electronic Engineering , University of Rajshahi.

using namespace std;

int main()
{
   int t,n,a[50];
   cin>>t;
   while(t--)
   {
       cin>>n;
       for(int i=0;i<n;i++)
       {
           cin>>a[i];
       }
       int swaps=0;
       for(int k=0;k<n;k++)
       {
           for(int j=0;j<n-1;j++)
           {
               if(a[j+1]<a[j])
               {
                   int temp=a[j];
                   a[j]=a[j+1];
                   a[j+1]=temp;
                   swaps++;
               }
           }
       }
       printf("Optimal train swapping takes %d swaps.\n",swaps);
   }
   return 0;
}

11332 - Summing Digits Uva Solution & Logic

https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=2307

খুবই সহজ একটা প্রোবলেম , একটি সংখ্যা দেয়া থাকবে , যতক্ষন না - সংখ্যাটি ১০ এর ছোট না হয় , ততক্ষন তার ডিজিটগুলোর যোগফল বের করতে হবে । যেমন , ধরো দেয়া আছে সংখ্যাটি ১২৩৪৯

তাহলে , f(12349) = 1+2+3+4+ 9 = 19

              f(19) = 1+9 =10

              f(10) = 1+0 = 1

          যখন , এভাবে ভাংতে ভাংতে ১০ এর ছোট হয়ে যায় , ঠিক তখনই সেটাই হবে উত্তর ।
চলো কোড দেখি ,

#include<bits/stdc++.h>

using namespace std;

int main()
{
    int t;
    long long int n;

while(scanf("%lld",&n)==1){

      if(n==0)
      break;

        t=0;
        while(true){

                while(n!=0){
                        t=t+(n%10);
                        n=n/10;
                }

                if(t/10==0){
                  break;
                        }

                else{
                    n=t;
                    t=0;
                    }

                   }

        printf("%d\n",t);
}

    return 0;
}

10783 - Odd Sum Uva Problem Solution & Logic

https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=1724

প্রোবলেম'টি যে কেউ সলভ করতে পারবে , কিন্তু - এখানেও অনেকভাবেই , প্রোবলেম এর উত্তর এফিশিয়েন্ট করা যায় । যেহেতু , এফিসিয়েন্ট করার সুযোগ আছে , সেহেতু - আমি , লুপ খাটিয়ে করার পক্ষপাতি নই । এইসব ছোটখাট প্রোবলেম যদি , এফিসিয়েন্ট করে করা শুরু করি , এখন থেকেই - তাহলে বড় বড় প্রোবলেম এর ক্ষেত্রে সুবিধা হবে ।

যদি কখনো বলে , প্রথম ২/৩/৪ টি বিজোড় সংখ্যার যোগফল বের করো । তাহলে, কি হতে পারে ?? হাতে কলমে দেখি , চলো

   ১+৩=৪ ,    ১+৩+৫=৯             , ১+৩+৫+৭=১৬ ,১+৩+৫+৭+৯=২৫

            কি? বুঝা যায় ?? হুম, যোগফল গুলো অলটাইম ততগুলো বিজোড় সংখ্যার বর্গ হয় ।
            তাহলে , প্রশ্ন অনুযায়ী - আমাকে ২ টি সংখ্যা দিবে --- a & b এদের মাঝে যতগুলো বিজোড়
আছে , তাদের যোগফল বের করতে হবে ।

তাহলে , প্রথমে ১ থেকে b অবদি মোট কয়টা বিজোড় সংখ্যা আছে ?? সেটা -- ২ দিয়ে ভাগ দিলেই পাবো , তারপর যে কয়টা বিজোড় সংখ্যা আছে তাকে বর্গ করলেই
১ থেকে b অবদি সবগুলোর যোগফল বের হয়ে যাবে । এখন ১ থেকে a এর আগ অবদি, বিজোড়্গুলোর
যোগফল বের করবো --

                       এখন, ১ থেকে b এর যোগফল থেকে , ১ থেকে a এর আগ অবদি, বিজোড়্গুলোর
                    যোগফল বাদ দিলেই , আমরা ------- a থেকে b অবদি যতগুলি বিজোড় আছে তাদের
                                                                      যোগফল পাবো । চলো কোড দেখি ,

#include<bits/stdc++.h>

// Nayeem Mollick Joy , Applied Physics & Electronic Engineering , University of Rajshahi.

using namespace std;

int main()
{
    int T,a,b,b1;
    cin>>T;
    for(int i=1;i<=T;i++)
    {
        cin>>a>>b;
        if(b%2!=0)
        {
             b1=(b>>1)+1;
        }
        else{
             b1=(b>>1);
        }

        int B=b1*b1;
        int A=(a>>1)*(a>>1);
        cout<<"Case "<<i<<": "<<B-A<<endl;
    }
    return 0;
}

Tuesday, July 11, 2017

COMDIV - Number of common divisors Spoj Problem Solution & Logic

http://www.spoj.com/problems/COMDIV/

এটা অনেকভাবেই করা যায় । কিন্তু , কথা হলো --- কোন পদ্ধতি সবচেয়ে এফিসিয়েন্ট ?? সেটা , বুঝতে হবে । তোমাকে , দুইটা সংখ্যা দেয়া থাকবে , দুইটা সংখ্যার মধ্যে মোট কয়টা সধারণ গুননীয়ক আছে তার পরিমাণ তোমাকে বের করতে হবে । চলো , দেখি তো ৬ ও ১২ এর মধ্যে কয়টা সধারণ গুননীয়ক আছে ----

২০ = ১০*২ = ৫*২*২*১
৬       =    ৩*২*১

সাধারণ , গুননীয়ক মোট ২ টা , ২ ও ১ । আচ্ছা , এই সাধারন গুননীয়ক গুলো গুণ করলে কি হবে , বলো তো ???   ২ *১ =২ , যা ২০ ও ৬ এর গ সা গু । তাই না ?? এর মানে , ২ টি সংখ্যার মধ্যে , কমন গুননীয়কগুলি'র গুনফল হলো , সংখ্যা ২ টির   গু সা গু ।

অর্থাৎ , সংখ্যা দুইটির গ সা গু বের করে যদি , মোট গুননীয়ক এর সংখ্যা বের করতে পারি - সেটাই হবে আমাদের ২ টি সংখ্যার মধ্যে - মোট সধারন গুননীয়ক এর সংখ্যা । চলো , কোড দেখি ----------

#include <iostream>
#include<cstdio>
#include<cmath>

using namespace std;

long int gcd(long int a,long int b)

{
    if(b==0)
    {
        return a;
    }
    else
    {
        return gcd(b,a%b);
    }
}

int main()

{
    int t;
    long int a,b,i,g;
    scanf("%d",&t);
    while(t--)

    {
        scanf("%ld %ld",&a,&b);
        int count=0;
        g=gcd(a,b);
        for(i=1;i<=sqrt(g);i++)
        {
            if(i*i==g)
            {

                    count++;
            }
            else if(g%i==0)
            {
               count=count+2;
            }
        }
        printf("%d\n",count);
    }
    return 0;
}

CEQU - Crucial Equation Spoj Problem Solution & Logic

http://www.spoj.com/problems/CEQU/

মজার একটি প্রোবলেম , একটি ইকুয়েশন ax + by = c এর কো-এফিসিয়েন্ট গুলো ( a,b,c ) দেয়া থাকবে ।

তোমায় , বলতে হবে --- equation টি'র আদৌ কোনো সলিউশন আছে ?? নাকি , নাই ????
এখন , ধরো a=8 , b=4 & c=3 দেয়া আছে , তোমায় বলা হলোও - এই ইকুয়েশন এর কোনো সলিউশন আছে কি না ??তাহলে চলো, চেক করি --------------------------

                                       8x + 4y = 3


যদি , x=1 & y= -1        8 - 4 = 4
                                      যদি,   x=2 & y=-2        16-8=8
যদি, x=3 & y= - 2       24-8=16
   যদি, x=4 & y= -2    32-8=24
যদি, x=5 & y=-9        40-36=4
   ..................................................................................
   ....................................................................................

এভাবে সারাজীবন চেষ্টা করলেও , উত্তর কোনোদিনও ৩ হবে না , এর মানে এর কোনো সলিউশন নেই ।
বলো তো , কিভাবে ? আমি এত্ত সিউর হচ্ছি --- যে , এর কোনো সলিউশন নেই ??

তুমি কি লক্ষ করেছো ??? ইকুয়েশন এর উত্তর 4,8,16,24,4 ............ ইত্যাদি হয় ।শুধু তাই নয় , এই উত্তর গুলো , সবসময়ই a & b এর   গ সা গু এর গুণিতক হবে । অর্থাৎ , c এর মান যদি a & b এর গ সা গু এর গুণিতক হয় , তাহলেই কেবল এর সলিউশন সম্ভব , আর না হলে নয় ।

চলো , এবার কোড দেখি

#include <iostream>

using namespace std;

long int gcd(long long int a , long long int b){

    if(b==0 || a==0) {
        return 0;
    }
    if(b%a==0){
        return a;
    }
    else{
        return gcd(b%a,a);
    }

}

int main()
{
    long long int T,a,b,c,g;

    cin>>T;

    for (int i = 1; i <= T; ++i)
    {

        cin>>a>>b>>c;

        g=gcd(a,b);

        if(c%g==0)
            cout<<"Case "<<i<<": Yes"<<endl;
        else
            cout<<"Case "<<i<<": No"<<endl;
    }
    return 0;
}

ATOMS - Atoms in the Lab SPOJ Problem Solution & Logic

http://www.spoj.com/problems/ATOMS/

খুবই সহজ একটি প্রোবলেম , তোমায় বলা আছে যে - একটা Atomic Research Centre - এ N সংখ্যক
Atom আছে , যেটা ১ সেকেন্ড পর পর K সংখ্যক টুকরোতে পরিনত হয় । এখন , লক্ষ রাখতে হবে , মোট Atom এর টুকরোর পরিমাণ যেনো , M ছাড়িয়ে না যায় । তাহলে , টুকরোর পরিমাণ ১ সেকেন্ড পর পর K গুণ করে বাড়তে থাকবে , যে পর্যন্ত না M ছাড়িয়ে যায় । তারপর , কয় সেকেন্ড লাগলো ??
সেটাই হবে , আমাদের উত্তর ।

কিন্তু , সমস্যা হলো - K ,N, M এর মান অনেক বেশী বড়ো রেঞ্জ এর হবে

         K ,N, M <= 10^18

সেই জন্য , আমাদের N=N*K করে , বাড়িয়ে M অবদি চেক করার চেয়ে ,

S=1 , ধরে - S=S*K; করে , বাড়িয়ে M/N অবদি চেক করতে হবে - তাহলে , কিন্তু একই কাজই করা হবে এবং Overflow হবে না । কারণ, S=S*K করে বাড়ানোর কারনে , গুনফল আগের পদ্ধতি N=N*K
করে বাড়ালে , যে গুনফল হতো - তার চেয়ে N গুণ কম হবে । আর , সেই জন্যই আমাদের লিমিটেশনও
M কে N দিয়ে ভাগ দিয়ে কমিয়ে M/N করে নিয়েছি । ঘুরেফিরে , একই কাজ করেছি - যেনো , মেমোরি'তে Overflow না হয় । চলো , কোড দেখি -------

#include<iostream>
#include<cstdio>

using namespace std;

int main()

{

    int p;

    scanf("%d",&p);

    while(p--)

    {

        unsigned long long int n,k,m,s=1,t=0;

        scanf("%llu%llu%llu",&n,&k,&m);

        if(n>m)

            printf("0\n");

        else

        {

            while(s<=m/n)

            {

                s=s*k;

                if(s<=m/n)

                  {

                    t++;

                   }

            }

            printf("%llu\n",t);

        }

    }

    return 0;

}

FCTRL2 - Small factorials SPOJ Problem Solution & Full Logic

http://www.spoj.com/problems/FCTRL2/

ফ্যাক্টোরিয়াল খুবই মজার ও পরিচিত একটা বিষয় , কিন্তু , যখনই - অনেক বড়ো একটি সংখ্যার ফ্যাক্টোরিয়াল বের করতে বলে , তখন বেশ ঝামেলায় পড়তে হয় । যেমন , যদি ৫০ এর ফ্যাক্টরিয়াল বের করো তাহলে হবে , 30414093201713378043612608166064768844377641568960512000000000000

এত্ত বড়ো সংখ্যা তো , int টাইপ variable স্টোর করতে পারবে না , তাই একটু কষ্ট করে এমন একটা ব্যবস্থা করতে হবে , যেনো , এই সংখ্যা'র ডিজিটগুলোকে একটা int টাইপ অ্যারে'তে ঢুকাতে হবে ।
তারপর , সেটাকে প্রিন্ট করলেই হয়ে যাবে ।

এখন প্রথমে , কোড দেখো - তারপর ,কিভাবে কাজ করছে ? ? সেটা ব্যাখ্যা করলে , মনে হয় একটু ইজি হবে -----

#include <bits/stdc++.h>

using namespace std;

#define max 500

int multiply(int x,int res[],int res_size);

void factorial(int n)

{
    int res[max];

    res[0]=1;

    int res_size=1;

    for(int x=2;x<=n;x++)
    {
        res_size=multiply(x,res,res_size);
    }

    for(int i=res_size-1;i>=0;i--)
    {
        cout<<res[i];
    }
    cout<<endl;
}

int multiply(int x,int res[],int res_size)
{
    int carry=0;

    for(int i=0;i<res_size;i++)
    {
        int prod=res[i]*x+carry;
        res[i]=prod%10;
        carry=prod/10;
    }

    while(carry)
    {
        res[res_size]=carry%10;
        carry=carry/10;
        res_size++;
    }

    return res_size;
}

int main()
{
    int t,n;
    cin>>t;
    while(t--)
    {
        cin>>n;
        factorial(n);
    }
    return 0;
}

কোড দেখে ভয় পাবার কিছুই নেই , ধরো , ৫ এর ফ্যাক্টোরিয়াল বের করতে হবে । তাহলে ,কিভাবে কাজ করবে ? চলো , দেখে নেয়া যাক ।

প্রথমে , factorial() নামক void function কে call করা হবে , সুতরাং-----আমরা সেই   factorial() ফাংশন-এ চলে যাবো ---------------

প্রথমেই , একটি res নামে একটি অ্যারে decalre করলাম ,যার সাইজ নির্ধারণ করলাম ৫০০ এর মতো,সর্বাধিক ৫০০ ডিজিট অবদি , অ্যারেটি ধারণ করতে পারবে ।

প্রথমে , res[0]=1 মানে , প্রথম ভ্যালু ১ -এ ইনিশিয়ালাইজ করলাম -সুতরাং int res_size=1;যেহেতু , অ্যারেতে কেবল একটি'র মান বসানো আছে । যেহেতু , ৫ এর ফ্যাক্টোরিয়াল হবে , ৫ * ৪ * ৩* ২*১ ।
১ গুণ করলেই কি ? আর না করলেই কি ? কিছুই না , তাই ১ কে ইগনোর করে

      for(int x=2;x<=n;x++)
      {
        res_size=multiply(x,res,res_size);
       }

এই লুপটা ঘুরালাম , যেটা   ২*৩*৪*৫ এর মান generate করবে । এখন , গুণ এর কাজ করার জন্য ,

int multiply(int x,int res[],int res_size)

নামক একটি ফাংশন ইউজ করেছি । এখন , প্রথমে যখন লুপ ঘুরবে , x এর মান ২ যেটা multiply
ফাংশনে ঢূকবে , এবং

for(int i=0;i<res_size;i++)
    {
        int prod=res[i]*x+carry;
        res[i]=prod%10;
        carry=prod/10;
    }

লুপটির দ্বারা , গুণ করবে আর যদি কখনো carry থাকে , মানে কোনো কিছুর গুণফল যদি - ২ ডিজিট বিশিষ্ট হয় - তাহলে প্রথম ডিজিট'টি হবে carry , মানে - যেমন ৬*৭= ৪২ , এখানে ক্যারি হলো - ৪ ।

while(carry)
    {
        res[res_size]=carry%10;
        carry=carry/10;
        res_size++;
    }

carry কে , ইমপ্লিমেন্ট করার জন্য - এই লুপ ইউজ করলাম । এখন শুধু , দেখে নেই , ৫ এর ফ্যাক্টরিয়াল এ কোড কি করছে ??

res[0]=1;

res[0]=2; ( 2 দিয়ে ১গুণ করে)

res[0]=6; ( ৩ দিয়ে ২ গুণ করে)

res[0]=4, res[1]=2; ( ৬ কে ৪ দিয়ে গুণ করে)

res[0]=0 , res[1]=2, res[2]=1; ( অনুরুপভাবে)

for(int i=res_size-1;i>=0;i--)
    {
        cout<<res[i];
    }

লুপটি ইউজ করে , প্রিন্ট করলাম তাহলে , উত্তর হবে -    120

Monday, July 10, 2017

DIVISION - Divisiblity by 3 SPOJ Problem Solution & Logic

http://www.spoj.com/problems/DIVISION/

মোটামুটি ঝামেলার একটা প্রোবলেম , নাম্বার থিওরি সম্পরকে ভালো ধারণা না থাকলে , এটা সলভ করা সম্ভব নয়।

ধরো , N = 2 দেয়া আছে, অর্থাৎ যদি বলা হয় - ২ ডিজিট বিশিষ্ট কয়টি , বাইনারি নাম্বার আছে যেগুলো ৩ দ্বারা বিভাজ্য ।

তাহলে ২ ডিজিট বিশিষ্ট ------    (০০) = ০ , ৩ দ্বারা বিভাজ্য
                                                    (১১) = ৩ ,   ৩    দ্বারা বিভাজ্য
                                                    (১০)   = ২ , ৩ দ্বারা বিভাজ্য নয়
                                                    (০১) = ১, ৩ দ্বারা বিভাজ্য নয়

           তাহলে ,মোট দুইটি সংখ্যা যেমন , ০০ && ১১ শুধু মাত্র ৩ দ্বারা বিভাজ্য ।

তাহলে , চলো দেখি ২,৩,৪,৫,৬,৭ ডিজিট বিশিষ্ট সংখ্যা'র ক্ষেত্রে কি ঘটতে পারে ?? প্যাটার্ন খোজার
চেষ্টা করি

N=1 ->1

N=2 ->2 (2*1)

N=3 ->3 (2*1)*2 - 1 = (2^2)-1

N=4 -> 6 (2^2 -1)*2 = ( 2 ^3 - 2 )

N=5 ->11 (2^3 – 2^1)*2 - 1 = (2^4 - 2^2 ) -1

N=6 ->22 (2^4 – 2^2 -1) *2 = ( 2^5 – 2^3 -2 )

N=7 ->43      (2^5 – 2^3 – 2^1)*2 - 1    = ( 2^6 – 2^4 – 2^2 ) - 1

তাহলে , দেখা যাচ্ছে - যে , N এর মান যখন জোড় ,তখন এক ধরনের ধারা , এর সুত্র হবে ,
                                                     (2^N+ 2)/3

ও N এর মান যখন বিজোড় , তখন এক ধরনের ধারা   , এর সুত্র হবে , (2^N + 1)/3

এখন দেখি ,কিছুটা সহজ মনে হচ্ছে , তাই না   ?? কিন্তু , একটু ঝামেলা আছে --

যেহেতু N এর মান অনেক বড়ো হতে পারে , তখন কিন্তু আমাদের কোড ঠিকঠাক রান

করবে না , তাই - প্রশ্নে কিন্তু বলাই আছে যে -

"Print in new line the answer modulo 1000000007."

অর্থাৎ , আমাদের প্রিন্ট করতে হবে ।

( (2^N+ 2) / 3 )%1000000007 অথবা ,
( (2^N + 1 ) /3 ) %1000000007

এখানে , আরো কিছু বিষয় আছে , Modular Multiplicative Inverse ছাড়াও আরো কিছু নিয়ম ।

এসব না জানা থাকলে , দ্রুত শিখে নেইয়া উচিত , না হলে - এই কোড'টি বুঝতে পারবে না ।।।

চলো কোড'টা দেখি ফেলি ------------------

#include <bits/stdc++.h>

using namespace std;

#define ULL unsigned long long

#define MOD 1000000007

#define INV 333333336 // Inverse modulo of 3 with 1000000007

ULL pow_mod(ULL n)
{
    ULL x=1,p=2;

    while ( n!=0 )
    {
        if(n%2!=0)
            x=(x*p)%MOD;

        p=(p*p)%MOD;

        n=n>>1;
    }

    return x;
}
int main()
{
    ULL n,result;

    while(scanf("%llu",&n)!=EOF)

    {
        if(n%2!=0){
            result = ((pow_mod(n)+1)*INV)%MOD;
            printf("%llu\n",result);
        }

        else{

            result = ((pow_mod(n)+2)*INV)%MOD;
            printf("%llu\n",result);
        }
    }

    return 0;
}