UVA 10679 - I Love Strings!!

Problem Explanation

Category: Easy
Type: String Ad Hoc


This is simple string ad hoc problem. You just need to find out a substring of a given string. But the tricky situation is you have to find out a string which will match from the start of the given string.
Suppose you have a string  IamAgoodStudendAndILikeProgramming and your query string is mming . This is a substring string but in case of this problem this is not a solution. If your query string is IamAgoodS then it is a solution of the problem. That is your query string must have to match from the beginning of the main string.

For cource code link click here

Codeforces 946 A Partition

Explanation

category : Easy

You just need to sum up all numbers. If you find any negative number just make it positive.

Source code link

Codeforces 950 A Left-handers, Right-handers and Ambidexters

Problem Explanation

Category: Easy

One have to find out maximum number of player which is even. Check the amount of left hand player  right hand player. If the amount is not same then take a amount of player from ambidexters, which can make equal number for both left hand and right hand. after taking some player from ambidexters , if still there are some player remains in ambidexters then divide the player among left hand and right hand players. 

If the amount of ambidexters player is zero the just squre the value which is minimum of left hand and right hand players. 

Some test case

10 12 10

28

1 0 1

2

2 4 0

4

3 6 9

18

5 5 5

14

Source code link Click here

Find out divisors of a number with a efficient way

Suppose you have 24 and you need to find out all divisors of the number. The normally what we do? We just divide the number from 1 to 24. That is we have to check 24 times. For 24 it is not a problem. But if I ask you do the same operation for 1234567 or for 1000000 or for 2345678? 😛
The whole day will be spent, isn't it?
Now let's check one thing.
All divisor of 24 is 1,2,3,4,6,8,12,24 and
(1*24) = (2*12) = (3*8) = (4*6) = 24
Here we multiply first element with last element, second element with second last element and third element with third last element.
That is we need to multiply ith element and (n-1+i)th element and need to count total number of multiplication and then again multiply the total by 2.

But now the question is we are only given a number not the divisor list. Then what we should do? Yes, we will find out the list and just count with the above approach.
That is at first we divide

24 by 1 and we get 24 and the pair is (1,24)
24 by 2 and we get 12 and the pair is (2,12)
24 by 3 and we get 8 and the pair is (3,8)
24 by 4 and we get 6 and the pair is (4,6)
24 by 5 but this is not a divisor
24 by 6 and we get 4 and the pair is (4,6). We already got the pair so avoid it.
24 by 7 but this is not a divisor
24 by 8 and we get 3 and the pair is (3,8). We already got the pair so avoid it.

if we go more towards then same pair will appear that's why we will now stop. Now count how many time we did this. It is 8 times, isn't it? Carefully observe , if we stop our calculation at 5 or just before 6 that is when we get any pair which already occurred, we will be done. Carefully observe 5 is equal to integer part of (square root of 24 ) +1

Now lets take a look on the sudo code

1. Take a number n
2. For i=1 to (square-root of n) +1
3.  check if n is dividable by i or not
4. if dividable then count = count +1
5. if not go to 2 again
6. print value of count

You can check for 48,100,3000,4000. 

Now you have a home work. Follow bellow what I write

24 / 2 = 12

12 / 2 = 6

6 / 2 = 3

3 / 3 = 1

Upto 1 I get 4 result and now multiply 4*2 = 8. 

O My god!

Am I correct for the above calculation? Check yourself for 48, 100, 122 

If I correct then find out the sudo code or algorithm. 

UVA 11876 - N + NOD (N) (Explanation)

Problem Explanation

Problem Category : Medium
Algorithm: Binary Search, Mathematical Simulation

For this problem, if you know how to find out total divisor of a number in a efficient way, then your job 85% is done. For this problem at first I have found out all divisor of a number and added with that number.
That is if the number is x then x = x + divisor(x)
and also marked those x's by using an array and also found out total number of numbers in the sequence for the range 1 to 1000000. In a test case I just calculate the difference between the ranges.

If you want to use binary search algorithm the you need not sum up the array. For using binary search algorithm just store all x's in a array and run a loop from a to b and search the value and count.

One important thing. If you use array to mark the x's then you can declare the array in the main function or globally. But don't forget to set 0 to all indices of the array if you declare the array in the main function. If you declare the array globally then you need not set 0 to all indices. Now it's your choice what should to do for less time complexity 

For source code Click

UVA 11057 - Exact Sum (Explanation)

Problem Explanation

Problem Category: Easy
Algorithm : Binary search

Explanation: You are given a list of numbers which represent money and total money that the boy get. Take one element from the list and find out other element by subtracting from total amount of money. Use binary search for searching the another element after subtracting. When you will find the two number you have to check if their difference is minimum.
You can do the same operation by using loop but in worst case you will get time complexity. 

Don't forget to sort the data 😜

Sudo code:

1. Take one element from the list. This one should be  a
2.  now b = total  - a where total is the money which the boy was given in two weeks
3. check if a is greater than b, that mean this a already have checked, if it is true just break
4. if not the search b using binary search
5. When you will found check if b-a is minimum
6.  if b-a is minimum then store it as lowa and lowb.
7. Remember, your answer actually lowa and lowb

Check some test case:
8
12 9 3 15 18 5 10 6
21
8
12 9 3 15 18 5 10 6
15
8
12 9 3 15 18 5 10 6
33

If you face trouble you can see the code. Just Click

UVA 10474 - Where is the Marble? (Explanation)

Problem Explanation 
After reading the problem what do you think? Is it a problem of linear searching or anything else? Yes you can solve it by one for loop or linear search. But I think this is not a good solution.
Good approach is using binary search algorithm.
The important information I found from the description is " She would count 1...2...3" that is Meena always count from the start.
So suppose you have 5 numbers like 5 5 5 5 5 then Meena will count the first one. So if you just implement the binary search algorithm then also it will not work. You have to ensure that if there are same number in the list. And to do this just decrees the value of end index of the algorithm.
Don't forget to sort data😜
Here is the sudo code

begin =0
end = array_size-1
while begin<=end
if key_alue and mid value are same then
index = data[mid] and end = mid-1
or if key_value is greater than mid value then
begin = mid+1
or if key_value is smaller  then mid value then
end = mid-1

If you need to see the code then just  click 

UVA 10226 - Hardwood Species

/***
Md. Nazmul Hasan
Shahjalal University of Science & Technology,Sylhet.
hasan08sust@gmail.com
***/
#include<iostream>
#include<cstdio>
#include<stack>
#include<queue>
#include<map>
#include<vector>
#include<algorithm>
#include<cstring>
#include<sstream>
#include<cmath>
#include <iomanip>
using namespace std ;
typedef long long ll ;
typedef int in ;
typedef unsigned long long ull ;
const double pi = 2*acos(0) ;
#define pf printf
#define sc scanf
#define pb push_back
#define MEM(x,y) (memset((x),(y),sizeof(x)))
#define MIN(x,y) ((x) < (y) ? (x) : (y))
#define MAX(x,y) ((x) > (y) ? (x) : (y))
#define load(array,size)  for(int i=0 ; i<size ; i++) cin>>array[i]  ;
#define new_line  pf("\n")
#define clear_data(array) memset(array,0,sizeof(array))
#define highest_int 2147483647
#define lowest_int -2147483647


int main()
{
    int test,total,d;
    char str[40];
    map<string,int>my_map;
    map<string,int>::iterator it;
    vector<string>data;

    sc("%d\n\n",&test);
    while(test--)
    {
        total=0;
        while(gets(str))
        {
            if(strlen(str)==0)
                break;
            if(my_map.count(string(str))==0)
            {
                data.pb(string(str));
            }
            my_map[string(str)]++;
            total++;
        }
        sort(data.begin(), data.end());
        for(int i=0 ; i<data.size() ; i++)
        {
            d = my_map[data[i]];
            double value = (double)d / (double) total * 100.0 ;
            cout<<data[i]<<" ";
            pf("%.4lf\n",value);
        }
        my_map.clear();
        data.clear();
        if(test)
            pf("\n");
    }
}

UVA 10295 - Hay Points

/***
Md. Nazmul Hasan
Shahjalal University of Science & Technology,Sylhet.
hasan08sust@gmail.com
***/
#include<iostream>
#include<cstdio>
#include<stack>
#include<queue>
#include<map>
#include<vector>
#include<algorithm>
#include<cstring>
#include<sstream>
#include<cmath>
#include <iomanip>
using namespace std ;
typedef long long ll ;
typedef int in ;
typedef unsigned long long ull ;
const double pi = 2*acos(0) ;
#define maxi 40000
#define pf printf
#define sc scanf
#define pb push_back
#define MEM(x,y) (memset((x),(y),sizeof(x)))
#define MIN(x,y) ((x) < (y) ? (x) : (y))
#define MAX(x,y) ((x) > (y) ? (x) : (y))
#define load(array,size)  for(int i=0 ; i<size ; i++) cin>>array[i]  ;
#define new_line  pf("\n")
#define clear_data(array) memset(array,0,sizeof(array))
#define highest_int 2147483647


int main()
{
    int m,n,k,sum;
    map<string,int>my_map;
    string str,word;


    sc("%d %d",&m,&n);
    while(m--)
    {
       cin>>str>>k;
       my_map[str]=k;
    }

    while(n--)
    {
        word = "";
        sum=0;
        while(true)
        {
            cin>>str;
            if(str[0]=='.' && str.size()==1)
            {
                pf("%d\n",sum);
                word = "";
                break;
            }
            for(int i=0 ; i<str.size() ; i++)
            {
                if(str[i]==' ')
                {
                    word = "";
                    continue;
                }
                word += str[i];
                if(str[i+1]==' ' || i==str.size()-1)
                {
                    if(my_map[word])
                    {
                        //cout<<word<<" ";
                        sum += my_map[word];
                    }
                    if(i==str.size()-1)
                        word = "";

                }
            }
        }
    }
    return 0;
}

UVA 11496 - Musical Loop

/***
Md. Nazmul Hasan
Shahjalal University of Science & Technology,Sylhet.
hasan08sust@gmail.com
***/
#include<iostream>
#include<cstdio>
#include<stack>
#include<queue>
#include<map>
#include<vector>
#include<algorithm>
#include<cstring>
#include<sstream>
#include<cmath>
#include <iomanip>
using namespace std ;
typedef long long ll ;
typedef int in ;
typedef unsigned long long ull ;
const double pi = 2*acos(0) ;
#define maxi 40000
#define pf printf
#define sc scanf
#define pb push_back
#define MEM(x,y) (memset((x),(y),sizeof(x)))
#define MIN(x,y) ((x) < (y) ? (x) : (y))
#define MAX(x,y) ((x) > (y) ? (x) : (y))
#define load(array,size)  for(int i=0 ; i<size ; i++) cin>>array[i]  ;
#define new_line  pf("\n")
#define clear_data(array) memset(array,0,sizeof(array))
#define highest_int 2147483647


int main()
{
    int n,cnt,k;
    int data[10010];
    bool up, down;
    while(sc("%d",&n) &&n)
    {
       for(int i=0 ; i<n ; i++)
        sc("%d",&data[i]);

       up = down = false;
       if(data[n-1]<data[0])
        up = true;
       else
        down = true;
       data[n] = data[0];
       cnt=0;

       for(int i=1 ; i<=n ; i++)
       {
           if(data[i-1]<data[i] && down)
           {
               cnt++;
               down = false;
               up = true;
           }
           else if(data[i-1]>data[i] && up)
           {
               cnt++;
               up = false;
               down = true;
           }
       }

        pf("%d\n",cnt);
    }
    return 0;
}

UVA 11222 - Only I did it!

/***
Md. Nazmul Hasan
Shahjalal University of Science & Technology,Sylhet.
hasan08sust@gmail.com
***/
#include<iostream>
#include<cstdio>
#include<stack>
#include<queue>
#include<map>
#include<vector>
#include<algorithm>
#include<cstring>
#include<sstream>
#include<cmath>
#include <iomanip>
using namespace std ;
typedef long long ll ;
typedef int in ;
typedef unsigned long long ull ;
const double pi = 2*acos(0) ;
#define maxi 40000
#define pf printf
#define sc scanf
#define pb push_back
#define MEM(x,y) (memset((x),(y),sizeof(x)))
#define MIN(x,y) ((x) < (y) ? (x) : (y))
#define MAX(x,y) ((x) > (y) ? (x) : (y))
#define load(array,size)  for(int i=0 ; i<size ; i++) cin>>array[i]  ;
#define new_line  pf("\n")
#define clear_data(array) memset(array,0,sizeof(array))
#define highest_int 2147483647


int main()
{
    int test,p,n,cs=1,big,frnd;
    int data[10010],cntuser[5];
    sc("%d",&test);
    while(test--)
    {
        memset(data,0,sizeof(data));
        int mx=0,mn=120000;
        memset(cntuser,0,sizeof(cntuser));

        for(int i=1 ; i<=3; i++)
        {
            sc("%d",&n);
            for(int j=1 ; j<=n ; j++)
            {
                sc("%d",&p);
                if(mx<p)
                    mx=p;
                if(mn>p)
                    mn=p;
                if(data[p] || data[p]==-1)
                {
                    data[p]=-1;
                    continue;
                }
                else
                {
                    data[p] =i;
                }
            }
        }

        for(int i=mn ; i<=mx ; i++)
        {
            if(data[i]==1 || data[i]==2 || data[i]==3)
            {
                if(data[i]==1) cntuser[1]++;
                else if(data[i]==2) cntuser[2]++;
                else cntuser[3]++;
            }
        }
        if(cntuser[1]>=cntuser[2])
        {
            big = cntuser[1];
        }
        else
        {
            big = cntuser[2];
        }

        if(big>=cntuser[3])
        {
            big = big;
        }
        else
        {
            big = cntuser[3];
        }
        pf("Case #%d:\n",cs++);

        for(int i=1 ; i<=3 ; i++)
        {
            if(cntuser[i]==big)
            {
                pf("%d %d",i,big);
                for(int j=mn ; j<=mx ; j++)
                {
                    if(data[j]==i)
                        pf(" %d",j);
                }
                pf("\n");
            }
        }


    }

    return 0;
}

UVA 10050 - Hartals

/***
Md. Nazmul Hasan
Shahjalal University of Science & Technology,Sylhet.
hasan08sust@gmail.com
***/
#include<iostream>
#include<cstdio>
#include<stack>
#include<queue>
#include<map>
#include<vector>
#include<algorithm>
#include<cstring>
#include<sstream>
#include<cmath>
#include <iomanip>
using namespace std ;
typedef long long ll ;
typedef int in ;
typedef unsigned long long ull ;
const double pi = 2*acos(0) ;
#define maxi 40000
#define pf printf
#define sc scanf
#define pb push_back
#define MEM(x,y) (memset((x),(y),sizeof(x)))
#define MIN(x,y) ((x) < (y) ? (x) : (y))
#define MAX(x,y) ((x) > (y) ? (x) : (y))
#define load(array,size)  for(int i=0 ; i<size ; i++) cin>>array[i]  ;
#define new_line  pf("\n")
#define clear_data(array) memset(array,0,sizeof(array))
#define highest_int 2147483647


int main()
{
    int test,n,p,h;
    int data[3655];

    sc("%d",&test);
    while(test--)
    {
      sc("%d",&n);
      memset(data,0,sizeof(data));
      for(int i=6 ; i<=n ; i+=7){
        data[i]=-1;
        data[i+1]=-1;
      }
      sc("%d",&p);
      int cnt=0;
      for(int i=1 ; i<=p ; i++)
      {
          sc("%d",&h);
          for(int j=h ; j<=n; j+=h)
          {
            if(data[j]<0 || data[j])
                continue;
            else if(data[j]==0)
            {
                data[j]=1;
                cnt++;
            }
          }
      }
      pf("%d\n",cnt);

    }

    return 0;
}

UVA 11093 - Just Finish it up

/***
Md. Nazmul Hasan
Shahjalal University of Science & Technology,Sylhet.
hasan08sust@gmail.com
***/
#include<iostream>
#include<cstdio>
#include<stack>
#include<queue>
#include<map>
#include<vector>
#include<algorithm>
#include<cstring>
#include<sstream>
#include<cmath>
#include <iomanip>
using namespace std ;
typedef long long ll ;
typedef int in ;
typedef unsigned long long ull ;
const double pi = 2*acos(0) ;
#define pf printf
#define sc scanf
#define pb push_back
#define MEM(x,y) (memset((x),(y),sizeof(x)))
#define MIN(x,y) ((x) < (y) ? (x) : (y))
#define MAX(x,y) ((x) > (y) ? (x) : (y))
#define load(array,size)  for(int i=0 ; i<size ; i++) cin>>array[i]  ;
#define new_line  pf("\n")
#define clear_data(array) memset(array,0,sizeof(array))
#define highest_int 2147483647
#define lowest_int -2147483647


int main()
{
    int test, n,p,x;
    int petrol[200040];

    sc("%d",&test);
    int cs=1;
    while(test--)
    {
        sc("%d",&n);
        for(int i=1 ; i<=n ; i++)
        {
            sc("%d",&petrol[i]);
            petrol[n+i] = petrol[i];
        }

        for(int i=1 ; i<=n ; i++)
        {
            sc("%d",&x);
            petrol[i] -= x;
            petrol[n+i] -= x;
        }

        petrol[0] =0;
        for(int i=1 ; i<=2*n ; i++)
        {
            petrol[i] += petrol[i-1];
        }
        int s=0, mi=1,cnt=0;
        for(int i=0 ; i<=2*n ; i++)
        {
            if(petrol[i]>=mi)
            {
               if(++cnt>n)
                    break;
            }
            else
            {
                mi = petrol[i];
                s= i;
                cnt=1 ;
                if(i>=n)
                    break;
            }
        }
        if(cnt>n)
            pf("Case %d: Possible from station %d\n",cs++,s+1);
        else
            pf("Case %d: Not possible\n",cs++);
    }
}

UVA 10042 - Smith Numbers

/***
Md. Nazmul Hasan
Shahjalal University of Science & Technology,Sylhet.
hasan08sust@gmail.com
***/
#include<iostream>
#include<cstdio>
#include<stack>
#include<queue>
#include<map>
#include<vector>
#include<algorithm>
#include<cstring>
#include<sstream>
#include<cmath>
#include <iomanip>
using namespace std ;
typedef long long ll ;
typedef int in ;
typedef unsigned long long ull ;
const double pi = 2*acos(0) ;
#define maxi 40000
#define pf printf
#define sc scanf
#define pb push_back
#define MEM(x,y) (memset((x),(y),sizeof(x)))
#define MIN(x,y) ((x) < (y) ? (x) : (y))
#define MAX(x,y) ((x) > (y) ? (x) : (y))
#define load(array,size)  for(int i=0 ; i<size ; i++) cin>>array[i]  ;
#define new_line  pf("\n")
#define clear_data(array) memset(array,0,sizeof(array))
#define highest_int 2147483647

vector<int>primeFactor ;

int sumOfNumberDigit(int n)
{
    //pf("#receive %d\n",n);
    int sum =0 ;
    while(1)
    {
        if(n==0)
            break;
        sum += n%10;
        //pf("%d ",n%10);
        n = n/10;
    }
    //pf("\n");
    return sum;
}

void findPrimeFactor(int n)
{
    while (n%2 == 0)
    {
        //pf("2 ");
        primeFactor.pb(2);
        n = n/2;
    }

    for (int i = 3; i <= sqrt(n); i = i+2)
    {
        while (n%i == 0)
        {
             //pf("%d ",i);
            primeFactor.pb(i);
            n = n/i;
        }
    }

    if (n > 2){
         //pf("%d ",n);
          primeFactor.pb(n);
    }

}

int main()
{
    int test,n,sum_num,sum;
    sc("%d",&test);
    while(test--)
    {
        sc("%d",&n);
        for(int i=n+1 ;  ; i++)
        {
            //pf("New one %d\n",i);
            sum_num = sumOfNumberDigit(i);
            //pf("%d sum_num: %d\n",i,sum_num);
            findPrimeFactor(i);
            sum=0;
            //pf("\n");
            if(primeFactor.size()==1)
            {
                primeFactor.clear();
                continue;
            }
            for(int j=0 ; j<primeFactor.size() ; j++)
            {
                sum += sumOfNumberDigit(primeFactor[j]);
            }
            //pf("%d %d\n",sum,i);
            if(sum == sum_num)
            {
                pf("%d\n",i);
                primeFactor.clear();
                break;
            }
            primeFactor.clear();
        }


    }

    return 0;
}

UVA 541 - Error Correction

/***
Md. Nazmul Hasan
Shahjalal University of Science & Technology,Sylhet.
hasan08sust@gmail.com
***/
#include<iostream>
#include<cstdio>
#include<stack>
#include<queue>
#include<map>
#include<vector>
#include<algorithm>
#include<cstring>
#include<sstream>
#include<cmath>
#include <iomanip>
using namespace std ;
typedef long long ll ;
typedef int in ;
typedef unsigned long long ull ;
const double pi = 2*acos(0) ;
#define maxi 40000
#define pf printf
#define sc scanf
#define pb push_back
#define MEM(x,y) (memset((x),(y),sizeof(x)))
#define MIN(x,y) ((x) < (y) ? (x) : (y))
#define MAX(x,y) ((x) > (y) ? (x) : (y))
#define load(array,size)  for(int i=0 ; i<size ; i++) cin>>array[i]  ;
#define new_line  pf("\n")
#define clear_data(array) memset(array,0,sizeof(array))
#define highest_int 2147483647


int main()
{
    int n,x,y,num,row_odd,col_odd,r,c;
    int data[105][105],row[105],col[105];
    memset(row,0,sizeof(row));
    memset(col,0,sizeof(col));

    while(sc("%d",&n) &&n)
    {
        memset(row,0,sizeof(row));
        memset(col,0,sizeof(col));

      for(int i=0 ; i<n ; i++)
        for(int j=0 ; j<n ; j++)
        {
          sc("%d",&data[i][j]);
          row[i] = row[i]+data[i][j];
          col[j] = col[j] + data[i][j];
        }
        row_odd = col_odd = 0;
        for(int i=0 ; i<n ; i++)
        {
            if(row[i]%2)
                row_odd++;
            if(col[i]%2)
                col_odd++;
           for(int j=0 ; j<n ; j++)
            if(row[i]%2 && col[j]%2)
            {
               r=i+1;
               c = j+1;
            }

        }
        if(row_odd>1 || col_odd>1)
            pf("Corrupt\n");
        else if(row_odd==0 && col_odd ==0)
            pf("OK\n");
        else if(row_odd==1 && col_odd==1)
            pf("Change bit (%d,%d)\n",r,c);

    }

    return 0;
}

Codeforces 939 A Love Triangle

/***
Md. Nazmul Hasan
Shahjalal University of Science & Technology,Sylhet.
hasan08sust@gmail.com
***/
#include<iostream>
#include<cstdio>
#include<stack>
#include<queue>
#include<map>
#include<vector>
#include<algorithm>
#include<cstring>
#include<sstream>
#include<cmath>
#include <iomanip>
using namespace std ;
typedef long long ll ;
typedef int in ;
typedef unsigned long long ull ;
const double pi = 2*acos(0) ;
#define pf printf
#define sc scanf
#define pb push_back
#define MEM(x,y) (memset((x),(y),sizeof(x)))
#define MIN(x,y) ((x) < (y) ? (x) : (y))
#define MAX(x,y) ((x) > (y) ? (x) : (y))
#define load(array,size)  for(int i=0 ; i<size ; i++) cin>>array[i]  ;
#define new_line  pf("\n")
#define clear_data(array) memset(array,0,sizeof(array))
#define highest_int 2147483647
#define lowest_int -2147483647

int main()
{
    int n;
    int data[5010];
    sc("%d",&n);
    for(int i=0 ; i<n ; i++)
        sc("%d",&data[i+1]);
    bool notGet = false ;
    for(int i=1 ; i<n+1 ; i++)
    {
        if( i == data[data[data[i]]])
        {
            pf("YES");
            notGet = true;
            break;
        }
    }
    if(notGet == false)
        pf("NO");

    return 0;
}

Codeforces 940 A Points on the line

/***
Md. Nazmul Hasan
Shahjalal University of Science & Technology,Sylhet.
hasan08sust@gmail.com
***/
#include<iostream>
#include<cstdio>
#include<stack>
#include<queue>
#include<map>
#include<vector>
#include<algorithm>
#include<cstring>
#include<sstream>
#include<cmath>
#include <iomanip>
using namespace std ;
typedef long long ll ;
typedef int in ;
typedef unsigned long long ull ;
const double pi = 2*acos(0) ;
#define pf printf
#define sc scanf
#define pb push_back
#define MEM(x,y) (memset((x),(y),sizeof(x)))
#define MIN(x,y) ((x) < (y) ? (x) : (y))
#define MAX(x,y) ((x) > (y) ? (x) : (y))
#define load(array,size)  for(int i=0 ; i<size ; i++) cin>>array[i]  ;
#define new_line  pf("\n")
#define clear_data(array) memset(array,0,sizeof(array))
#define highest_int 2147483647
#define lowest_int -2147483647

int main()
{
    int n,d,p;
    vector<int>data;
    int ans=-1;

    sc("%d %d",&n,&d);
    for(int i=1 ; i<=n ; i++)
    {
        sc("%d",&p);
        data.pb(p);
    }
    sort(data.begin(),data.end());

    for(int i=0;i<n;i++)for(int j=i;data[j]-data[i]<=d&&j<n;j++)
if(j-i+1>ans)ans=j-i+1;
    pf("%d",n-ans);
    return 0;
}

UVA 12149 - Feynman

/***
Md. Nazmul Hasan
Shahjalal University of Science & Technology,Sylhet.
hasan08sust@gmail.com
***/
#include<iostream>
#include<cstdio>
#include<stack>
#include<queue>
#include<map>
#include<vector>
#include<algorithm>
#include<cstring>
#include<sstream>
#include<cmath>
#include <iomanip>
using namespace std ;
typedef long long ll ;
typedef int in ;
typedef unsigned long long ull ;
const double pi = 2*acos(0) ;
#define maxi 40000
#define pf printf
#define sc scanf
#define pb push_back
#define MEM(x,y) (memset((x),(y),sizeof(x)))
#define MIN(x,y) ((x) < (y) ? (x) : (y))
#define MAX(x,y) ((x) > (y) ? (x) : (y))
#define load(array,size)  for(int i=0 ; i<size ; i++) cin>>array[i]  ;
#define new_line  pf("\n")
#define clear_data(array) memset(array,0,sizeof(array))
#define highest_int 2147483647


int main()
{
    int n,sum;
    while(sc("%d",&n)&&n)
    {
       sum = (n*(n+1)*(2*n+1))/6;
       pf("%d\n",sum);
    }

    return 0;
}

UVA 924 - Spreading The News

/***
Md. Nazmul Hasan
Shahjalal University of Science & Technology,Sylhet.
hasan08sust@gmail.com
***/
#include<iostream>
#include<cstdio>
#include<stack>
#include<queue>
#include<map>
#include<vector>
#include<algorithm>
#include<cstring>
#include<sstream>
#include<cmath>
#include <iomanip>
using namespace std ;
typedef long long ll ;
typedef int in ;
typedef unsigned long long ull ;
const double pi = 2*acos(0) ;
#define pf printf
#define sc scanf
#define pb push_back
#define MEM(x,y) (memset((x),(y),sizeof(x)))
#define MIN(x,y) ((x) < (y) ? (x) : (y))
#define MAX(x,y) ((x) > (y) ? (x) : (y))
#define load(array,size)  for(int i=0 ; i<size ; i++) cin>>array[i]  ;
#define new_line  pf("\n")
#define clear_data(array) memset(array,0,sizeof(array))
#define highest_int 2147483647
#define lowest_int -2147483647

int visited[100001];
int parent[100001];
int headerInADay[100001];
vector<int>G[10001];

void bfs(int src)
{
    queue<int>q;
    memset(visited,0,sizeof(visited));
    memset(parent,0,sizeof(parent));

    q.push(src);
    visited[src]=1;
    headerInADay[src]=0;
    int u,v;
    while(!q.empty())
    {
        u = q.front();
        q.pop();
        for(int i=0; i<G[u].size() ; i++)
        {
            v = G[u][i];
            if(headerInADay[v] == lowest_int)
            {
                headerInADay[v] = headerInADay[u] +1;
                q.push(v);
            }
        }
    }
}


void print_path(int src)
{
    int occuer[2600];
    memset(occuer,0,sizeof(occuer));

    for(int i=0 ; i<2500 ; i++)
        if(headerInADay[i] != lowest_int)
        occuer[headerInADay[i]]++;

    int maxi = -1 ;
    int maxiDay;

    for(int i=1 ; i<2510 ; i++)
    {
       if(maxi < occuer[i])
       {
           maxi = occuer[i];
           maxiDay = i;
       }
    }
    if(G[src].size() ==0)
        pf("0\n");
    else
        pf("%d %d\n",maxi,maxiDay);


}

int main()
{
    int node,edge,test,src,n;
    sc("%d",&node);

    for(int i=0 ; i<node ; i++)
    {
        sc("%d",&edge);
        for(int j=0 ; j<edge ; j++)
        {
            sc("%d",&n);
            G[i].pb(n);
        }
    }

    sc("%d",&test);
    for(int i=1 ; i<=test ; i++)
    {
        for(int j=0 ; j<2510 ; j++)
           headerInADay[j] = lowest_int;
        sc("%d",&src);
        bfs(src);
        print_path(src);
    }
    return 0;
}

UVA 11824 - A Minimum Land Price

/***
Md. Nazmul Hasan
Shahjalal University of Science & Technology,Sylhet.
hasan08sust@gmail.com
***/
#include<iostream>
#include<cstdio>
#include<stack>
#include<queue>
#include<map>
#include<vector>
#include<algorithm>
#include<cstring>
#include<sstream>
#include<cmath>
#include <iomanip>
using namespace std ;
typedef long long ll ;
typedef int in ;
typedef unsigned long long ull ;
const double pi = 2*acos(0) ;
#define maxi 40000
#define pf printf
#define sc scanf
#define pb push_back
#define MEM(x,y) (memset((x),(y),sizeof(x)))
#define MIN(x,y) ((x) < (y) ? (x) : (y))
#define MAX(x,y) ((x) > (y) ? (x) : (y))
#define load(array,size)  for(int i=0 ; i<size ; i++) cin>>array[i]  ;
#define new_line  pf("\n")
#define clear_data(array) memset(array,0,sizeof(array))
#define highest_int 2147483647

int main()
{
    int test ,p;
    sc("%d",&test);
    vector<int> data ;
    bool tooExpensive;
    ll sum;
    while(test--)
    {
        tooExpensive = false;
        while(1)
        {
            sc("%d",&p);
            if(p==0)
                break;
            data.pb(p);
        }
        sum =0;
        sort(data.begin(),data.end());
        reverse(data.begin(),data.end());
        for(int i=0 ; i<data.size() ; i++)
        {
            p = data[i];
            //pf("%d ",pow(p,i+1));
            sum += (2*pow(p,i+1));
            if(sum > 5000000)
            {
                tooExpensive = true ;
                break;
            }
        }
        if(tooExpensive){
            pf("Too expensive\n");
        }else{
           pf("%lld\n",sum);
        }

        data.clear();
    }

    return 0;
}

UVA 10905 - Children's Game

/***
Md. Nazmul Hasan
Shahjalal University of Science & Technology,Sylhet.
hasan08sust@gmail.com
***/
#include<iostream>
#include<cstdio>
#include<stack>
#include<queue>
#include<map>
#include<vector>
#include<algorithm>
#include<cstring>
#include<sstream>
#include<cmath>
#include <iomanip>
using namespace std ;
typedef long long ll ;
typedef int in ;
typedef unsigned long long ull ;
const double pi = 2*acos(0) ;
#define maxi 40000
#define pf printf
#define sc scanf
#define pb push_back
#define MEM(x,y) (memset((x),(y),sizeof(x)))
#define MIN(x,y) ((x) < (y) ? (x) : (y))
#define MAX(x,y) ((x) > (y) ? (x) : (y))
#define load(array,size)  for(int i=0 ; i<size ; i++) cin>>array[i]  ;
#define new_line  pf("\n")
#define clear_data(array) memset(array,0,sizeof(array))
#define highest_int 2147483647


struct str{
  string str;
};

bool operator < (const str & a, const str & b)
{
    return a.str + b.str > b.str + a.str ;
}

int main()
{
   int n;
   while(sc("%d",&n))
   {
       if(n==0)
        break;
        str num[55];

       for(int i=0 ; i<n; i++)
       {
           cin>>num[i].str ;
       }

       sort(num, num+n);

       for(int i=0 ; i<n ; i++)
        cout<<num[i].str ;

       cout<<endl ;
   }
    return 0;
}

UVA 530 - Binomial Showdown

/***
Md. Nazmul Hasan
Shahjalal University of Science & Technology,Sylhet.
hasan08sust@gmail.com
***/
#include<iostream>
#include<cstdio>
#include<stack>
#include<queue>
#include<map>
#include<vector>
#include<algorithm>
#include<cstring>
#include<sstream>
#include<cmath>
#include <iomanip>
using namespace std ;
typedef long long ll ;
typedef int in ;
typedef unsigned long long ull ;
const double pi = 2*acos(0) ;
#define maxi 40000
#define pf printf
#define sc scanf
#define pb push_back
#define MEM(x,y) (memset((x),(y),sizeof(x)))
#define MIN(x,y) ((x) < (y) ? (x) : (y))
#define MAX(x,y) ((x) > (y) ? (x) : (y))
#define load(array,size)  for(int i=0 ; i<size ; i++) cin>>array[i]  ;
#define new_line  pf("\n")
#define clear_data(array) memset(array,0,sizeof(array))
#define highest_int 2147483647


int main()
{

    ll n,m,res,i,num,p ;
    while(sc("%lld %lld",&n,&m)==2)
    {
        if(n==0 && m==0)
            break;
        res = 1 ;
        if(n-m < m)
            p = n-m;
        else
            p = m;
        num = n;
        for(i=1 ; i<=p ; i++,num--)
        {
            res = res * num;
            res = res/i;
        }

        pf("%lld\n",res);
    }
    return 0;
}

UVA 369 - Combinations

/***
Md. Nazmul Hasan
Shahjalal University of Science & Technology,Sylhet.
hasan08sust@gmail.com
***/
#include<iostream>
#include<cstdio>
#include<stack>
#include<queue>
#include<map>
#include<vector>
#include<algorithm>
#include<cstring>
#include<sstream>
#include<cmath>
#include <iomanip>
using namespace std ;
typedef long long ll ;
typedef int in ;
typedef unsigned long long ull ;
const double pi = 2*acos(0) ;
#define maxi 40000
#define pf printf
#define sc scanf
#define pb push_back
#define MEM(x,y) (memset((x),(y),sizeof(x)))
#define MIN(x,y) ((x) < (y) ? (x) : (y))
#define MAX(x,y) ((x) > (y) ? (x) : (y))
#define load(array,size)  for(int i=0 ; i<size ; i++) cin>>array[i]  ;
#define new_line  pf("\n")
#define clear_data(array) memset(array,0,sizeof(array))
#define highest_int 2147483647


int main()
{

    ll n,m,res,i,num,p ;
    while(sc("%lld %lld",&n,&m)==2)
    {
        if(n==0 && m==0)
            break;
        res = 1 ;
        if(n-m < m)
            p = n-m;
        else
            p = m;
        num = n;
        for(i=1 ; i<=p ; i++,num--)
        {
            res = res * num;
            res = res/i;
        }

        pf("%lld things taken %lld at a time is %lld exactly.\n",n,m,res);
    }
    return 0;
}

UVA 11687 11687 - Digits

/***
Md. Nazmul Hasan
Shahjalal University of Science & Technology,Sylhet.
hasan08sust@gmail.com
***/
#include<iostream>
#include<cstdio>
#include<stack>
#include<queue>
#include<map>
#include<vector>
#include<algorithm>
#include<cstring>
#include<string>
#include<sstream>
#include<cmath>
#include <iomanip>
using namespace std ;
typedef long long ll ;
typedef int in ;
typedef unsigned long long ull ;
const double pi = 2*acos(0) ;
#define maxi 40000
#define pf printf
#define sc scanf
#define pb push_back
#define MEM(x,y) (memset((x),(y),sizeof(x)))
#define MIN(x,y) ((x) < (y) ? (x) : (y))
#define MAX(x,y) ((x) > (y) ? (x) : (y))
#define load(array,size)  for(int i=0 ; i<size ; i++) cin>>array[i]  ;
#define new_line  pf("\n")
#define clear_data(array) memset(array,0,sizeof(array))
#define highest_int 2147483647

int main()
{
   string str, str1 ;
   int prev,x,ln1;
   while(cin>>str)
   {
       if(str == "END")
        break;
       int ln = str.size();
       x = ln;
       if(ln==1 && str[0]=='1')
       {
           pf("1\n");
           continue;
       }
       int cnt =1 ;
       while(true)
       {
           str1 = to_string(x);
           ln1 = str1.size();
           if(ln1 == x)
           {
               pf("%d\n",cnt+1);
               break;
           }
           x = ln1 ;
           cnt++;
       }
   }
    return 0;
}

UVA 10324 Zeros and Ones

/***
Md. Nazmul Hasan
Shahjalal University of Science & Technology,Sylhet.
hasan08sust@gmail.com
***/
#include<iostream>
#include<cstdio>
#include<stack>
#include<queue>
#include<map>
#include<vector>
#include<algorithm>
#include<cstring>
#include<sstream>
#include<cmath>
#include <iomanip>
using namespace std ;
typedef long long ll ;
typedef int in ;
typedef unsigned long long ull ;
const double pi = 2*acos(0) ;
#define maxi 40000
#define pf printf
#define sc scanf
#define pb push_back
#define MEM(x,y) (memset((x),(y),sizeof(x)))
#define MIN(x,y) ((x) < (y) ? (x) : (y))
#define MAX(x,y) ((x) > (y) ? (x) : (y))
#define load(array,size)  for(int i=0 ; i<size ; i++) cin>>array[i]  ;
#define new_line  pf("\n")
#define clear_data(array) memset(array,0,sizeof(array))
#define highest_int 2147483647

int main()
{
   string str ;
   int i,j,test,minv, maxv ;
   int cnt=1 ;
   while(cin>>str)
   {
       if(str.size() == 0)
        break;
       sc("%d",&test);
       pf("Case %d:\n",cnt++);
       for(int k=1 ; k<=test; k++)
       {
           sc("%d %d",&i,&j);
           bool notSame = true ;
           minv = min(i,j);
           maxv = max(i,j);
           char ch = str[minv];
           for(int n = minv ; n<=maxv ; n++)
           {
             if(ch == str[n])
                continue ;
             else if(ch != str[n]){
                notSame = false;
                break;
             }
           }
           if(notSame)
            pf("Yes\n");
           else
            pf("No\n");
       }
   }
    return 0;
}

UVA 11661

/***
Md. Nazmul Hasan
Shahjalal University of Science & Technology,Sylhet.
hasan08sust@gmail.com
***/
#include<iostream>
#include<cstdio>
#include<stack>
#include<queue>
#include<map>
#include<vector>
#include<algorithm>
#include<cstring>
#include<sstream>
#include<cmath>
#include <iomanip>
using namespace std ;
typedef long long ll ;
typedef int in ;
typedef unsigned long long ull ;
const double pi = 2*acos(0) ;
#define maxi 40000
#define pf printf
#define sc scanf
#define pb push_back
#define MEM(x,y) (memset((x),(y),sizeof(x)))
#define MIN(x,y) ((x) < (y) ? (x) : (y))
#define MAX(x,y) ((x) > (y) ? (x) : (y))
#define load(array,size)  for(int i=0 ; i<size ; i++) cin>>array[i]  ;
#define new_line  pf("\n")
#define clear_data(array) memset(array,0,sizeof(array))
#define highest_int 2147483647

int main()
{
    int l ;
    string str ;
    while(sc("%d",&l))
    {
        if(l==0)
            break;
        cin>>str ;
        int lastD = -l;
        int lastR = -l;
        int minimumDistance = l;

        for(int i=0 ; i<l ; i++)
        {
            if(str[i] =='Z')
            {
                minimumDistance =0;
                break;
            }
            else if(str[i] == 'R')
            {
               minimumDistance = min(minimumDistance, i-lastD) ;
               lastR = i;
            }
            else if(str[i] == 'D')
            {
                minimumDistance = min(minimumDistance, i-lastR) ;
               lastD = i;
            }
        }
        pf("%d\n",minimumDistance);
    }
    return 0;
}

UVA 10014 - Simple calculations

/***
Md. Nazmul Hasan
Shahjalal University of Science & Technology,Sylhet.
hasan08sust@gmail.com
***/
#include<iostream>
#include<cstdio>
#include<stack>
#include<queue>
#include<map>
#include<vector>
#include<algorithm>
#include<cstring>
#include<sstream>
#include<cmath>
#include <iomanip>
using namespace std ;
typedef long long ll ;
typedef int in ;
typedef unsigned long long ull ;
const double pi = 2*acos(0) ;
#define maxi 40000
#define pf printf
#define sc scanf
#define pb push_back
#define MEM(x,y) (memset((x),(y),sizeof(x)))
#define MIN(x,y) ((x) < (y) ? (x) : (y))
#define MAX(x,y) ((x) > (y) ? (x) : (y))
#define load(array,size)  for(int i=0 ; i<size ; i++) cin>>array[i]  ;
#define new_line  pf("\n")
#define clear_data(array) memset(array,0,sizeof(array))
#define highest_int 2147483647


int main()
{
    int test,n,cnt;
    float a, an,ans,m,sum;
    sc("%d",&test);

    for(int i=1 ; i<=test ; i++)
    {
        sc("%d",&n);
        sc("%f %f",&a,&an);
        cnt = 2*n;
        sum = 0;
        for(int j=1 ; j<=n ; j++)
        {
            sc("%f",&m);
            sum = sum + (m*cnt);
            cnt = cnt -2;
        }
        ans = ((n*a) + an - sum)/(n+1);
        pf("%.2f\n",ans);
        if(i!=test)
            pf("\n");
    }

    return 0;
}

UVA 10170 - The Hotel with Infinite Rooms Python Solution

from sys import stdin
scan = lambda : stdin.readline()

while True:
    n,k = map(int, scan().split())
    k = k
    sum = 0
    while True:
        sum += n
        if(sum >= k):
            print(n)
            break
        n += 1
   
   

UVA 10170 - The Hotel with Infinite Rooms

/***
Md. Nazmul Hasan
Shahjalal University of Science & Technology,Sylhet.
hasan08sust@gmail.com
***/
#include<iostream>
#include<cstdio>
#include<stack>
#include<queue>
#include<map>
#include<vector>
#include<algorithm>
#include<cstring>
#include<sstream>
#include<cmath>
#include <iomanip>
using namespace std ;
typedef long long ll ;
typedef int in ;
typedef unsigned long long ull ;
const double pi = 2*acos(0) ;
#define maxi 40000
#define pf printf
#define sc scanf
#define pb push_back
#define MEM(x,y) (memset((x),(y),sizeof(x)))
#define MIN(x,y) ((x) < (y) ? (x) : (y))
#define MAX(x,y) ((x) > (y) ? (x) : (y))
#define load(array,size)  for(int i=0 ; i<size ; i++) cin>>array[i]  ;
#define new_line  pf("\n")
#define clear_data(array) memset(array,0,sizeof(array))
#define highest_int 2147483647


int main()
{
    long long s, d;
    while(scanf("%lld %lld", &s, &d) == 2)
    {
        long long i = s, sum = 0;
        while(1)
        {
            sum += i;
            if(sum >= d)
            {
                printf("%lld\n", i);
                break;
            }
            i++;
        }
    }
    return 0;
}

UVA 10940 - Throwing cards away II

/***
Md. Nazmul Hasan
Shahjalal University of Science & Technology,Sylhet.
hasan08sust@gmail.com
***/
#include<iostream>
#include<cstdio>
#include<stack>
#include<queue>
#include<map>
#include<vector>
#include<algorithm>
#include<cstring>
#include<sstream>
#include<cmath>
#include <iomanip>
using namespace std ;
typedef long long ll ;
typedef int in ;
typedef unsigned long long ull ;
const double pi = 2*acos(0) ;
#define maxi 40000
#define pf printf
#define sc scanf
#define pb push_back
#define MEM(x,y) (memset((x),(y),sizeof(x)))
#define MIN(x,y) ((x) < (y) ? (x) : (y))
#define MAX(x,y) ((x) > (y) ? (x) : (y))
#define load(array,size)  for(int i=0 ; i<size ; i++) cin>>array[i]  ;
#define new_line  pf("\n")
#define clear_data(array) memset(array,0,sizeof(array))
#define highest_int 2147483647


int main()
{
    int ans[500000 + 5];

        ans[1] = 1;
        ans[2] = 2;

        int next = 2;

        for(int i = 3; i <= 500000; i++ )
        {
            if ( i < next ) next = 2;
            ans [i] = next;
            next += 2;
        }

        int n;

        while( sc ("%d", &n) && n )
        {
            pf("%d\n", ans [n]);
        }

    return 0;
}

UVA 10499 - The Land of Justice

/***
Md. Nazmul Hasan
Shahjalal University of Science & Technology,Sylhet.
hasan08sust@gmail.com
***/
#include<iostream>
#include<cstdio>
#include<stack>
#include<queue>
#include<map>
#include<vector>
#include<algorithm>
#include<cstring>
#include<sstream>
#include<cmath>
#include <iomanip>
using namespace std ;
typedef long long ll ;
typedef int in ;
typedef unsigned long long ull ;
const double pi = 2*acos(0) ;
#define maxi 40000
#define pf printf
#define sc scanf
#define pb push_back
#define MEM(x,y) (memset((x),(y),sizeof(x)))
#define MIN(x,y) ((x) < (y) ? (x) : (y))
#define MAX(x,y) ((x) > (y) ? (x) : (y))
#define load(array,size)  for(int i=0 ; i<size ; i++) cin>>array[i]  ;
#define new_line  pf("\n")
#define clear_data(array) memset(array,0,sizeof(array))
#define highest_int 2147483647


int main()
{

   long long int n;
   char ch = '%';
   while(sc("%lld",&n)==1 && n>=0)
   {
       if(n==1)
        pf("0%%\n");
       else if(n>1)
        pf("%lld%%\n",(n*25));
   }
    return 0;
}

UVA 11503 - Virtual Friends

/***
Md. Nazmul Hasan
Shahjalal University of Science & Technology,Sylhet.
hasan08sust@gmail.com
***/
#include<iostream>
#include<cstdio>
#include<stack>
#include<queue>
#include<map>
#include<vector>
#include<algorithm>
#include<cstring>
#include<sstream>
#include<cmath>
#include <iomanip>
using namespace std ;
typedef long long ll ;
typedef int in ;
typedef unsigned long long ull ;
const double pi = 2*acos(0) ;
#define maxi 40000
#define pf printf
#define sc scanf
#define pb push_back
#define MEM(x,y) (memset((x),(y),sizeof(x)))
#define MIN(x,y) ((x) < (y) ? (x) : (y))
#define MAX(x,y) ((x) > (y) ? (x) : (y))
#define load(array,size)  for(int i=0 ; i<size ; i++) cin>>array[i]  ;
#define new_line  pf("\n")
#define clear_data(array) memset(array,0,sizeof(array))
#define highest_int 2147483647


int rx[1000001], p[1000001];
map<string,int> R;

int findF(int x)
{
   return p[x] == x ? x : (p[x]=findF(p[x]));
}

int makeFriend(int x, int y)
{
    int u = findF(x);
    int v = findF(y);
    if(u!=v)
    {
        if(rx[u] > rx[v])
        {
            rx[u] += rx[v];
            p[v]=u;
            return rx[u];
        }
        rx[v] += rx[u];
        p[u] = v;
        return rx[v];
    }

    return rx[u];
}


int main()
{

  int test,n,tx,ty;
  char x[30], y[30];

  sc("%d",&test);

  while(test--)
  {
      sc("%d",&n);
      int cnt =0;
      for(int i=0 ; i<=min(2*n,100000) ; i++)
      {
          p[i] =i;
          rx[i]=1;
      }

      while(n--)
      {
         sc("%s %s",&x,&y);
         tx = R[x];
         ty = R[y];
         if(tx==0)
         {
             R[x] = ++cnt;
             tx = cnt;
             //pf("#%d\n",cnt);
         }
         if(ty==0)
         {
             R[y] = ++cnt;
             ty = cnt;
              //pf("#%d\n",cnt);
         }

         pf("%d\n",makeFriend(tx,ty));

      }

      R.clear();
  }

    return 0;
}

UVA 10608 - Friends

/***
Md. Nazmul Hasan
Shahjalal University of Science & Technology,Sylhet.
hasan08sust@gmail.com
***/
#include<iostream>
#include<cstdio>
#include<stack>
#include<queue>
#include<map>
#include<vector>
#include<algorithm>
#include<cstring>
#include<sstream>
#include<cmath>
#include <iomanip>
using namespace std ;
typedef long long ll ;
typedef int in ;
typedef unsigned long long ull ;
const double pi = 2*acos(0) ;
#define maxi 40000
#define pf printf
#define sc scanf
#define pb push_back
#define MEM(x,y) (memset((x),(y),sizeof(x)))
#define MIN(x,y) ((x) < (y) ? (x) : (y))
#define MAX(x,y) ((x) > (y) ? (x) : (y))
#define load(array,size)  for(int i=0 ; i<size ; i++) cin>>array[i]  ;
#define new_line  pf("\n")
#define clear_data(array) memset(array,0,sizeof(array))
#define highest_int 2147483647

vector<int>data[30010];
int visited[30010],cnt;


void dfs(int u)
{
   visited[u]=1;
   cnt++;
   for(int i=0 ; i<data[u].size() ; i++)
   {
       int v = data[u][i];
       if(!visited[v])
       {
           dfs(v);
       }
   }
   return;
}


int main()
{

   int test,n,m,u,v;
   sc("%d",&test);

   for(int tc=1 ; tc<=test ; tc++)
   {
       sc("%d %d",&n,&m);

       memset(visited,0,sizeof(visited));
       for(int i=1 ; i<=m ; i++)
       {
           sc("%d %d",&u,&v);
           data[u].pb(v);
           data[v].pb(u);
       }
       int mx =0 ;

       for(int i=1 ; i<=n ; i++)
       {
           if(!visited[i])
           {
               cnt=0;
               dfs(i);
               mx = max(mx,cnt);
           }
       }
       pf("%d\n",mx);
       for(int i=1 ; i<=n ; i++)
        data[i].clear();
   }
    return 0;
}

793 - Network Connections

/***
Md. Nazmul Hasan
Shahjalal University of Science & Technology,Sylhet.
hasan08sust@gmail.com
***/
#include<iostream>
#include<cstdio>
#include<stack>
#include<queue>
#include<map>
#include<vector>
#include<algorithm>
#include<cstring>
#include<sstream>
#include<cmath>
#include <iomanip>
using namespace std ;
typedef long long ll ;
typedef int in ;
typedef unsigned long long ull ;
const double pi = 2*acos(0) ;
#define maxi 40000
#define pf printf
#define sc scanf
#define pb push_back
#define MEM(x,y) (memset((x),(y),sizeof(x)))
#define MIN(x,y) ((x) < (y) ? (x) : (y))
#define MAX(x,y) ((x) > (y) ? (x) : (y))
#define load(array,size)  for(int i=0 ; i<size ; i++) cin>>array[i]  ;
#define new_line  pf("\n")
#define clear_data(array) memset(array,0,sizeof(array))
#define highest_int 2147483647

int parent[100001], rank_n[100001];

void makePair(int x)
{
    parent[x] =x;
    rank_n[x] =0;
}

int find_n(int x)
{
    if(parent[x]!=x)
        parent[x] = find_n(parent[x]);
    return parent[x];
}

void makeUnion(int x, int y)
{
    int px = find_n(x);
    int py = find_n(y);

    if(px==py)
        return;
    if(rank_n[px] > rank_n[py])
        parent[py] = px;
    else
    {
        parent[px] = py;
        if(rank_n[px] == rank_n[py])
            rank_n[px]++;
    }
}


int main()
{
    int test,n,u,v,cnt1,cnt2;
    char ch, str[10001];
    sc("%d",&test);

   for(int tc=1 ; tc<=test ; tc++)
    {
        sc("%d",&n);
        memset(parent,0,sizeof(parent));

        for(int i=1 ; i<=n ; i++)
            makePair(i);
        getchar();
        cnt1 = cnt2 =0;
        while(1)
        {
           gets(str);
           if(strcmp(str,"")==0 || feof(stdin))
            break;
           sscanf(str,"%c %d %d",&ch,&u,&v);
           if(ch == 'c')
            makeUnion(u,v);
           else if(ch =='q')
             if(find_n(u) == find_n(v))
                cnt1++;
            else
                cnt2++;
        }
        if(tc!=1)
            pf("\n");
        pf("%d,%d\n",cnt1,cnt2);
    }

    return 0;
}

Making tooltip in GUI by python

import sys
from PyQt4 import QtGui

class Example(QtGui.QWidget):
   
     def __init__(self):
         super(Example,self).__init__()
         self.initUI()
 
     def initUI(self):
         QtGui.QToolTip.setFont(QtGui.QFont('SansSerif',10))
         self.setToolTip('This is a <b>QWidget</b> widget')
         
         btn = QtGui.QPushButton('Button',self)
         btn.setToolTip('This is a <b>QPushButton</b> widget')
         btn.resize(btn.sizeHint())
         btn.move(10,10)
         
         self.setGeometry(10,10,300,300)
         self.setWindowTitle('ToolTips')
         self.show()


def main():
    app = QtGui.QApplication(sys.argv)
    ex = Example()
    sys.exit(app.exec_())


if __name__ == '__main__':
   main()

Set Window Icon in Python Gui Programing

import sys
from PyQt4 import QtGui

class Example(QtGui.QWidget):
   
    def __init__(self):
       super(Example,self).__init__()
       self.initUi()

    def initUi(self):
       self.setGeometry(10,10,300,300)
       self.setWindowTitle('Windo ICON')
       self.setWindowIcon(QtGui.QIcon('icon.png'))
       self.show()



def main():
    app = QtGui.QApplication(sys.argv)
    ex = Example()
    sys.exit(app.exec_())


if __name__ == '__main__':
    main()

Python Basic Gui

#To make a simple gui follow the instructions. You need to at first install PyQt4 in your system. If you use linux run the code sudo apt-get install python3-pyqt4. For another system you just need to setup an application file. Google it for this. After installing pyqt4 modulo just write down the foling code. it will show you a simple gui.

import sys
from PyQt4 import QtGui


def main():
   
    app = QtGui.QApplication(sys.argv)

    w = QtGui.QWidget()
    #w.resize(250, 150)
    #w.move(300, 300)
    w.setGeometry(10,10,400,400)
    w.setWindowTitle('Simple GUI in Python')
    w.show()
   
    sys.exit(app.exec_())


if __name__ == '__main__':
    main()

UVA 755 - 487--3279

/***
Md. Nazmul Hasan
Shahjalal University of Science & Technology,Sylhet.
hasan08sust@gmail.com
***/
#include<iostream>
#include<cstdio>
#include<stack>
#include<queue>
#include<map>
#include<vector>
#include<algorithm>
#include<cstring>
#include<sstream>
#include<cmath>
#include <iomanip>
using namespace std ;
typedef long long ll ;
typedef int in ;
typedef unsigned long long ull ;
const double pi = 2*acos(0) ;
#define maxi 40000
#define pf printf
#define sc scanf
#define pb push_back
#define MEM(x,y) (memset((x),(y),sizeof(x)))
#define MIN(x,y) ((x) < (y) ? (x) : (y))
#define MAX(x,y) ((x) > (y) ? (x) : (y))
#define load(array,size)  for(int i=0 ; i<size ; i++) cin>>array[i]  ;
#define new_line  pf("\n")
#define clear_data(array) memset(array,0,sizeof(array))
#define highest_int 2147483647

map<string,int> my_map ;
map<string,int>::iterator it;


char getChar(char ch)
{
    if(ch=='A' || ch=='B' || ch=='C')
        return '2';
    else if(ch=='D' || ch=='E' || ch=='F')
        return '3';
    else if(ch=='G' || ch=='H' || ch=='I')
        return '4';
    else if(ch=='J' || ch=='K' || ch=='L')
        return '5';
    else if(ch=='M' || ch=='N' || ch=='O')
        return '6';
    else if(ch=='P' || ch=='R' || ch=='S')
        return '7';
    else if(ch=='T' || ch=='U' || ch=='V')
        return '8';
    else if(ch=='W' || ch=='X' || ch=='Y')
        return '9';
    else if(ch>='0' && ch<='9')
        return ch;
    return 'Q';
}


string convert_str(string s)
{
    string result,ans;

    for(int i=0 ; i<s.size() ; i++)
    {
        if(s[i]!='-')
        {
            result += getChar(s[i]);
        }
    }

    for(int i=0 ; i<result.size() ; i++)
    {
        if(i==3)
            ans += '-';
        ans += result[i];
    }
    return ans;
}


int main()
{
    int test,n;
    string str,s;
    sc("%d",&test);
    for(int cs=1 ; cs<=test ; cs++)
    {
        sc("%d",&n);

        while(n--)
        {
            cin>>str;
            s = convert_str(str);
            my_map[s]++;
        }
        if(cs>1)
            pf("\n");
        bool get = false ;
        for(it = my_map.begin() ; it!=my_map.end() ; it++)
        {
            if(it->second >1)
            {
                get = true;
                cout<<it->first<<" "<<it->second<<endl;
            }
        }
        if(!get)
            pf("No duplicates.\n");
        my_map.clear();
    }

    return 0;
}

UVA 10789 - Prime Frequency

/***
Md. Nazmul Hasan
Shahjalal University of Science & Technology,Sylhet.
hasan08sust@gmail.com
***/
#include<iostream>
#include<cstdio>
#include<stack>
#include<queue>
#include<map>
#include<vector>
#include<algorithm>
#include<cstring>
#include<sstream>
#include<cmath>
#include <iomanip>
using namespace std ;
typedef long long ll ;
typedef int in ;
typedef unsigned long long ull ;
const double pi = 2*acos(0) ;
#define maxi 40000
#define pf printf
#define sc scanf
#define pb push_back
#define MEM(x,y) (memset((x),(y),sizeof(x)))
#define MIN(x,y) ((x) < (y) ? (x) : (y))
#define MAX(x,y) ((x) > (y) ? (x) : (y))
#define load(array,size)  for(int i=0 ; i<size ; i++) cin>>array[i]  ;
#define new_line  pf("\n")
#define clear_data(array) memset(array,0,sizeof(array))
#define highest_int 2147483647

int isPrime(int n)
{
    int root;
    if(n ==0 || n==1)
        return 0;
    else if(n ==2 )
        return 1;
    else if(n%2==0)
        return 0;
    else
    {
        root = sqrt(n);
        for(int i=3 ; i<=root ; i+=2)
        {
            if(n%i ==0)
                return 0;
        }
        return 1;
    }
}

int main()
{
    char str[3001];
    int data[150];
    vector<int>value;
    int test,n,cs=0;

    sc("%d",&test);
    getchar();
    while(test--)
    {
        gets(str);
        memset(data,0,sizeof(data));
        for(int i=0 ; i<strlen(str) ; i++)
        {
            n = str[i];
            if(data[n]==0)
                value.pb(n);
            data[n]++;
            //pf("%d",data[n]);
        }

        sort(value.begin(),value.end());
        bool t = false ;
        pf("Case %d: ",++cs);
        for(int i=0 ; i<value.size() ; i++)
        {
            if(isPrime(data[value[i]]))
        {
            pf("%c",value[i]);
                t = true;
            }
        }

        if(t == false)
            pf("empty");
        value.clear();
        pf("\n");

    }

    return 0;
}

UVA 10921 - Find the Telephone

/***
Md. Nazmul Hasan
Shahjalal University of Science & Technology,Sylhet.
hasan08sust@gmail.com
***/
#include<iostream>
#include<cstdio>
#include<stack>
#include<queue>
#include<map>
#include<vector>
#include<algorithm>
#include<cstring>
#include<sstream>
#include<cmath>
#include <iomanip>
using namespace std ;
typedef long long ll ;
typedef int in ;
typedef unsigned long long ull ;
const double pi = 2*acos(0) ;
#define maxi 40000
#define pf printf
#define sc scanf
#define pb push_back
#define MEM(x,y) (memset((x),(y),sizeof(x)))
#define MIN(x,y) ((x) < (y) ? (x) : (y))
#define MAX(x,y) ((x) > (y) ? (x) : (y))
#define load(array,size)  for(int i=0 ; i<size ; i++) cin>>array[i]  ;
#define new_line  pf("\n")
#define clear_data(array) memset(array,0,sizeof(array))
#define highest_int 2147483647


int main()
{
   char str[10001];

   while(gets(str))
   {
       for(int i=0 ; i<strlen(str) ; i++)
       {
           if(str[i]=='1' || str[i]=='0' || str[i]=='-')
           {
               pf("%c",str[i]);
               continue;
           }
           else if(str[i]>='A' && str[i]<='C')
            pf("2");
           else if(str[i]>='D' && str[i]<='F')
            pf("3");
           else if(str[i]>='G' && str[i]<='I')
            pf("4");
           else if(str[i]>='J' && str[i]<='L')
            pf("5");
           else if(str[i]>='M' && str[i] <='O')
            pf("6");
           else if(str[i]>='P' && str[i]<='S')
            pf("7");
           else if(str[i]>='T' && str[i]<='V')
            pf("8");
           else if(str[i] >='W' && str[i]<='Z')
            pf("9");
       }
       pf("\n");
   }

    return 0;
}