SPOJ Problems Hints

Problem Number: 302 Problem Name : Count on Cantor
Catagory : Pattern Finding
Sit on the chair-table with pen & paper.You will then see it creates a triangle.Also,try to find out another pattern for faster implementation :) If it's a "ODD" length triangle,it increases from bottom to top.If it is "Even" length triangle,it increases from top to bottom.Now,gear up yourself for getting Accepted :)

Problem Number: 2727 Problem Name : ARMY - Army Strength
Catagory : Easy AD-Hock
No need to use array/vector/priority_queue. Look at the problem, weakest strength army will be killed from that side.If weakest strength army in the both sides,then you have to do a deletion process from the MechaGodzilla's side.This process will give you a TLE. Just think a little bit more! Yep! Which side belongs to the strongest strength army will be won.If both side's strongest strength equal,this time MechaGodzilla will be lost :)

Problem Number: 95 Problem Name : STPAR - Street Parade
Catagory : Stack,Easy AD-Hock
You have to re-arrange your love car in ascending order which is starting from 1 ,ending at n. First find out 1.After that or before that which are not in the correct position,keep them one by one into stack. Then every time when you will get an element which is the next position(1,2,...,N) ,check out top value from stack.If top value is the next position,then do pop up operation from the stack and keep doing this process untill top value not equal next position (And check out whether your stack is empty or not). After finally if your stack is empty,then obviously you have already  done that!Otherwise,correct re-arrange is impossible to construct :)

Problem Number: 379 Problem Name : PERMUT2 - Ambiguous Permutations
Catagory : Easy AD-Hock
Don't feel weired if you don't get the problem. Read this problem more & more carefully.Hope,you will get that! One point is that it's not a permutation problem.It's an indexing problem.From given array,you have to put value at new array index.After constructing new array,compare both of them.If both are equal,say that's an ambiguous,otherwise not.

Problem Number: 1436 Problem Name : PT07Y - Is it a tree
Catagory : Depth First Search
Simple DFS is effective.And remember if(edge!=node-1),then that graph will not construct a tree.Because,greater than (node-1) edge,obviously cycle will be created. 

UVA-10370

প্রবলেমটি পড়ুন এবং বুঝুন

#include<bits/stdc++.h>

using namespace std;

int main()
{
    int test,people;

    cin>>test;
    while(test--)
    {
        double average=0;
        cin>>people;
        int value[people],counter=0;
        for(int i=0;i<people;i++)
        {
            cin>>value[i];
            average+=value[i];
        }
        average/=people;
        for(int i=0;i<people;i++)
        {
            if(average<value[i])
                counter++;
        }
        average=(counter*100)/(double)people;
        printf("%.3lf%%\n",average);
    }
    return 0;
}

UVA-382

প্রবলেমটি পড়ুন এবং বুঝুন

#include<iostream>

using namespace std;

int which_number(int a)
{
    long int sum=0,d;
    for(int i=1; i*i<=a; i++)
    {
        if(a%i==0)
        {
            d=a/i;
            if(i==a)
                continue;
            else if(i==1)
                sum+=1;
            else
                sum=sum+i+d;
        }
    }
    if(sum==a)
        cout<<a<<"  PERFECT\n";
    else if(sum<a)
        cout<<a<<"  DEFICIENT\n";
    else
        cout<<a<<"  ABUNDANT\n";
}

int main()
{
    int a,i=0;

    while((cin>>a))
    {
        if(i==0)
        {
            cout<<"PERFECTION OUTPUT\n";
            i++;
        }
        if(a==0) break;
        if(a<10)         cout<<"    ";
        else if(a<100)   cout<<"   ";
        else if(a<1000)  cout<<"  ";
        else if(a<10000) cout<<" ";
        which_number(a);
    }
    cout<<"END OF OUTPUT\n";
    return 0;
}

গ্লোবাল ভ্যারিয়েবল

                                                                       গ্লোবাল ভ্যারিয়েবল

আজ আমরা জানবো গ্লোবাল ভ্যারিয়েবল সম্বন্ধে।

গত পর্বে যেহুতু আমরা লোকাল ভ্যারিয়েবল সম্পর্কে জেনেছি,সেহেতু আমাদের জন্যে এ পর্বে গ্লোবাল ভ্যারিয়েবল সম্পর্কে জানতে গিয়ে আশা করি বেগ পেতে হবে না।

শুরুতেই একটি গল্প বলি।

আমার এলাকার এক ছেলে আছে। অনেক ভালো ক্রিকেট খেলে। এলাকার সবাই তাকে চিনে।ছেলেটার নাম সাকিব আল হাসান।

ধরো,তোমার এলাকার এক ছেলে সাকিব আল হাসানের মতো বেশ বড়মাপের ক্রিকেটার।ধরেই নাও যে মাশরাফি বিন মর্তুজার বাড়ি তোমাদের এলাকায়। মাশরাফিকে তোমাদের এলাকার সবাই চিনে।

আচ্ছা,সাকিব আল হাসান আমার এলাকার লোক হলেও তুমি কিন্তু সাকিব আল হাসানকে ঠিকই চিনো। আবার মাশরাফি বিন মর্তুজা তোমার এলাকার লোক হলেও আমি কিন্তু মাশরাফিকে চিনি। অর্থাৎ,মাশরাফি এবং সাকিব দুজনেই লোকাল হিরো হওয়ার সাথে সাথে ন্যাশনাল হিরোও কিন্তু।এদের দুজনকেই সবাই চিনে ফেলেছে।

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

গ্লোবাল ভ্যারিয়েবল এর শর্টকাট সংজ্ঞা আমরা এভাবে দিতে পারি যে,যে ভ্যারিয়েবলকে আমরা সকল ফাংশন থেকেই একসেস করতে পারি তাকে গ্লোবাল ভ্যারিয়েবল বলে।

গ্লোবাল ভ্যারিয়েবলকে সাধারণত সব ফাংশনের উপরে ডিক্লেয়ার করা হয়।কারণ,কোনো ভ্যারিয়েবলকে যখন গ্লোবালি ডিক্লেয়ার করবে,ভ্যারিয়েবলটি তার নিচের সকল ফাংশন থেকেই একসেস করা যাবে শুধু। তবে,তোমার প্রোগ্রামের সুবিধার্তে তুমি এটা যেকোনো ফাংশনের বাইরেই ডিক্লেয়ার করতে পারো।

নিচের কোড দেখে নাওঃ

#include<stdio.h>

int sum=0;          ///global variable

int  main()

{

       int a=10,b=30;                            ///local variable

       sum=a+b;                                      ///sum গ্লোবাল ভ্যারিয়েবল হওয়ায় কম্পাইলার তাকে চিনতেছে

       printf(“sum=%d\n”,sum);

     return 0;

}

এই প্রোগ্রামের আউটপুট হবে 

 sum=40

আশা করি গ্লোবাল ভ্যারিয়েবল সম্পর্কে কিছুটা হলেও ধারণা এসেছে।

গ্লোবাল ভ্যারিয়েবল সম্পর্কিত কিছু সাধারণ বিষয়ের উত্তরঃ

১।ভাইয়া,আমি যখন গ্লোবাল ভ্যারিয়েবলকে ডিক্লেয়ার করি তখন গ্লোবাল ভ্যারিয়েবলের ইনিশিয়াল ভ্যালু কত থাকে?? 

উওর হচ্ছে,ভাইয়া,গ্লোবাল ভ্যারিয়েবলের ইনিশিয়াল ভ্যালু জিরো থাকে।যদিও লোকাল ভ্যারিয়েবলের ক্ষেত্রে তুমি একটা গার্বেজ ভ্যালু পাবে(উল্টাপাল্টা ভ্যালু আর কি)।

নিচের কোড দেখলে আরো ক্লিয়ার হবেঃ

#include<stdio.h>

int sum;                                    ///global variable [ ইনিশিয়ালি sum এঁর ভেতর কিছু অ্যাসাইন করা হয়নি ]

int main()

{

   printf(“kono value assign korar age sum er maan holo %d\n”,sum);

         int a;                                   ///local variable [  ইনিশিয়ালি a তে কিছুই অ্যাসাইন করা হয় নাই ]

        printf(“ ’a’ te kono kichu assign korar age local variable ‘a’ er maan holo %d \n”,a);

   return 0;

} 

আউটপুটে sum এর মান হবে 0

কিন্তু a এর মান হিসেবে উল্টাপাল্টা একটা ভ্যালু প্রিন্ট হয়েছে।

বিভিন্ন Data Type এর জন্যে গ্লোবাল ভ্যারিয়েবলের ইনিশিয়াল ভ্যালু হল

Data Type Initializer int 0 float 0 double 0 char ‘\0’ pointer NULL

২।ভাইয়া,আমি যদি লোকাল এবং গ্লোবাল ভ্যারিয়েবল দুইটাকেই একই নামে ডিক্লেয়ার করি তবে কি হবে??

উত্তর হলো,লোকাল এবং গ্লোবাল ভ্যারিয়েবল দুইটাই যদি একই নামে ডিক্লেয়ার করা হয়,তবে কম্পাইলার লোকাল ভ্যারিয়েবলের হয়ে কাজ করবে।নিচের প্রোগ্রামটার দিকে খেয়াল করোঃ

#include<stdio.h>

int sum=100;                                  /// global variable

int main()

{

      int a=10,b=20,sum;               ///local variable[ sum এখানেও ডিক্লেয়ার করা হয়েছে,এখানে sum লোকাল ভ্যারিয়েবল]

  sum=a+b;

  printf(“sum er maan holo %d\n”,sum);

  return 0;

}

আউটপুট হবে------

sum er maan holo 30

খেয়াল করে দেখো,sum নামে লোকাল ভ্যারিয়েবল এবং গ্লোবাল ভ্যারিয়েবল ডিক্লেয়ার করা হলেও sum এর মান হিসেবে আমরা লোকাল ভ্যারিয়েবলের মানকেই পেয়েছি।গ্লোবাল ভ্যারিয়েবলের মান ছিলো ১০০।কিন্তু আমরা sum এর মান পেয়েছি 30, সেটা লোকাল ভ্যারিয়েবলের মান ৩০।

***মনের ভেতর উঁকি দিয়ে ওঠা আর একটি প্রশ্নের উওরঃ

গ্লোবাল ভ্যারিয়েবল সবসময় আপডেটেড ভ্যালু ক্যারি করে। ধরো,main() ফাংশনে তোমার গ্লোবাল ভ্যারিয়েবলে অ্যাসাইন করা হয়েছিলো ৫০।গ্লোবাল ভ্যারিয়েবলের ভেতর কোনো কিছু যতক্ষণ না অ্যাসাইন না করবো ততক্ষণ গ্লোবাল ভ্যারিয়েবলের মান কিন্তু ৫০ই থাকবে। ধরো,main() থেকে কল করা কোনো ফাংশনের ভেতর ঐ গ্লোবাল ভ্যারিয়েবলটির ভেতর ৩০ অ্যাসাইন করা হলো। এবার বলো তো,ঐ গ্লোবাল ভ্যারিয়েবলটির মান কত এখন?? এখন,ঐ গ্লোবাল ভ্যারিয়েবলটির মান হলো ৩০।কারণ,গ্লোবাল ভ্যারিয়েবল সবসময় তার ভেতর অ্যাসাইন করা ইমিডিয়েট ভ্যালুটা ক্যারি করে।

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

এই ছিলো গ্লোবাল ভ্যারিয়েবল সম্পর্কিত আজকের পর্ব।লোকাল ভ্যারিয়েবল সম্মন্ধে পড়ুন এখানে।

UVA-299

প্রবলেমটি পড়ুন এবং বুঝুন


#include<iostream>

using namespace std;

int main()
{
    long int test,n;
    cin>>test;
    while(test--)
    {
        cin>>n;
        int a[n],counter=0;

        for(int i=0; i<n; i++)
        {
            cin>>a[i];
            for(int k=0; k<i; k++)
            {
                if(a[i]<a[k])
                {
                    int t=a[k];
                    a[k]=a[i];
                    a[i]=t;
                    counter++;
                }
            }
        }
        cout<<"Optimal train swapping takes "<<counter<<" swaps."<<endl;
    }
    return 0;
}

UVA-12289

প্রবলেমটি পড়ুন এবং বুঝুন

#include<iostream>
#include<string>

using namespace std;

void justify(char *ch)
{
    string o="one",t="two",th="three";
    int i=0,counter[3]={0};

    while(*(ch+i)!='\0')
    {
            if(o[i]==*(ch+i))
            counter[0]+=1;
            else if(t[i]==*(ch+i))
            counter[1]+=1;
            else if(th[i]==*(ch+i))
            counter[2]+=1;
        i++;
    }
   
    int v,maximum=0;
   
    for(i=0;i<3;i++)
    {
        if(maximum<=counter[i])
        {
            maximum=counter[i];
            v=i;
        }
    }
    if(v==0)
        cout<<"1\n";
    else if(v==1)
        cout<<"2\n";
    else if(v==2)
        cout<<"3\n";
}

int main()
{
    int test;
    cin>>test;
    while(test--)
    {
        string str;
        cin>>str;
        justify(&str[0]);
    }
    return 0;
}

লোকাল ভ্যারিয়েবল

লোকাল ভ্যারিয়েবল

আজ আমরা জানবো লোকাল ভ্যারিয়েবল সম্বন্ধে।

ধরো,তোমার এলাকার নাম গোবরা।তোমার এলাকার এক মেধাবী ছাত্র আছে যার নাম নূর-আলম। ছেলেটাকে সবাই এলাকার গর্বের ধন মনে করে।তোমার এলাকার সব জায়গায় নূর-আলমের নামডাক।তোমাদের কাছে নূর-আলম একজন হিরো।

এবার শোনো আমার এলাকার গল্প। আমার এলাকার নাম সোবহানসড়ক। আমার এলাকায় একজন মেধাবী ছাত্র আছে,নাম আসলাম।সে খুব ভদ্র,স্কুল-কলেজে সবসময় খুব ভালো রেজাল্ট করে। আমাদের এলাকার যে কারো কাছে গিয়ে যদি বলো যে,”ভাই,আসলাম কে চিনেন কি না?”।দেখবে যে,সবাই তাকে একনামে চিনে ফেলতেছে। আসলামও আমাদের এলাকার হিরো।

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

আমাদের লোকাল ভ্যারিয়েবল ঠিক এমন। নিজের এলাকার বাইরে লোকাল ভ্যারিয়েবলকে কম্পাইলার চিনে না।লোকাল ভ্যারিয়েবলকে তার নিজের এলাকার লোকজন শুধু চিনে।প্রোগ্রামিংয়ে এলাকা নির্ধারিত হয় কার্লি ব্রাকেট এর মাধ্যমে।কার্লি ব্রাকেট আমাদের কাছে সেকেন্ড ব্রাকেট নামেই পরিচিত। প্রোগ্রামিংয়ে একটি কার্লি ব্রাকেটের ওপেনিং পার্ট থেকে সেই কার্লি ব্রাকেটের এন্ডিং পার্ট পর্যন্ত একটি এলাকা।

নিচের কোড দেখে কপি পেস্ট করে রান করে দেখো যে কম্পাইলার তোমাকে কি সিগন্যাল দেই।

#include<stdio.h>

int main()

{

                int a[5]={10,20,30,40,50};///এই ভ্যারিয়েবলের জন্যে কার্লি ব্রাকেটের ওপেনিং পার্ট হলো উপরের ব্রাকেট টি।যতক্ষণ না এই কার্লি ব্রাকেটের এন্ডিং পার্ট আমরা না পাচ্ছি,ততক্ষণ এই ভ্যরিয়েবলকে কম্পাইলার চিনবে   

    int i;//এই ভ্যারিয়েবলটির ক্ষেত্রেও উপরের একই কথা

for(i=0;i<5;i++)

{

    int t;

   if(a[i]%2==0)

                t=0;///a[i] এর মান জোড় হলে t=0 হবে

 else

                t=1; ///a[i] এর মান জোড় না হলে t=1 হবে

}

                printf(“t er maan holo %d\n”,t);

     return 0;

}

উপরের কোড রান করলে দেখবে যে, for লুপের ভেতরে t ভ্যারিয়েবল কে কম্পাইলার চিনলেও printf ফাংশনে t ভ্যারিয়েবলকে কম্পাইলার চিন্তেছে না।কারণ,t ভ্যারিয়েবল যখন তার নিজের এলাকায় ব্যবহৃত হয়েছে,তখন তাকে কম্পাইলার চিনেছে,যখন এলাকার বাইরে ব্যবহৃত হয়েছে তখন কম্পাইলার চিনতে পারে নাই। এবার তোমরা লোকাল ভ্যারিয়েবলের সংজ্ঞা আবার দেখে নাও।দেখো,অইখানে আমি বলেছি যে, লোকাল ভ্যারিয়েবলকে কম্পাইলার চিনবে একটি নির্দিষ্ট এলাকা পর্যন্ত। যেখানে ভ্যারিয়েবলটি ডিক্লেয়ার করা হয়েছে,তার ঠিক আগে যে কার্লি ব্রাকেটের ওপেনিং পার্ট{ আছে,সেই কার্লি ব্রাকেটের এন্ডিং পার্ট } পর্যন্ত ভ্যারিয়েবলটিকে কম্পাইলার চিনবে। ঐ কার্লি ব্রাকেটের বাইরে আর ভ্যারিয়েবলটিকে কেউ চিনবে না। উপরে দেখো যে,t ভ্যারিয়েবলের ঠিক আগে যে কার্লি ব্রাকেটের ওপেনিং পার্ট আছে,তার এন্ডিং পার্ট আছে printf ফাংশনের উপরে। আমাদের সংজ্ঞামতে স্বভাবতই t ভ্যারিয়েবলকে কম্পাইলার এরপর আর চিনবে না।এজন্যেই printf ফাংশনে কম্পাইলার t ভ্যারিয়েবলকে চিনতেছে না। এখন এই সমস্যা উত্তরণের জন্যে printf ফাংশন যে কার্লি ব্রাকেটের মাঝে অবস্থিত,t ভ্যারিয়েবলকে ঠিক সেই কার্লি ব্রাকেটের মধ্যেই ডিক্লেয়ার করতে হবে।

#include<stdio.h>

int main()

{

int a[5]={10,20,30,40,50};///এই ভ্যারিয়েবলের জন্যে কার্লি ব্রাকেটের ওপেনিং পার্ট হলো     উপরের ব্রাকেট টি।যতক্ষণ না এই কার্লি ব্রাকেটের এন্ডিং পার্ট আমরা না পাচ্ছি,ততক্ষণ এই ভ্যরিয়েবলকে কম্পাইলার চিনবে   

    int i,t;//এই ভ্যারিয়েবল দুটির ক্ষেত্রেও উপরের একই কথা

for(i=0;i<5;i++)

{

       if(a[i]%2==0)

                t=0;///a[i] এর মান জোড় হলে t=0 হবে

 else

                t=1; ///a[i] এর মান জোড় না হলে t=1 হবে

}

                printf(“t er maan holo %d\n”,t);///লক্ষ করে দেখো,t ভ্যারিয়েবলের কার্লি ব্রাকেটের এন্ডিং পার্ট এখনও আসে নাই। অর্থাৎ এখন t ভ্যারিয়েবল তার এলাকার মাঝেই আছে।

     return 0;

}

আসোলে,লোকাল ভ্যরিয়েবল জানা আমাদের প্রোগ্রামিংয়ের জন্যে খুব দরকারি।লোকাল ভ্যারিয়েবল নিয়ে অথবা প্রোগ্রামিং এর যেকোনো কিছু নিয়ে এট ফার্স্ট তোমাকে নিজে চেষ্টা করতে হবে সমস্যা,সমস্যা উদঘাটনের।

এই ছিলো লোকাল ভ্যারিয়েবল সম্বন্ধে।