UVA 10311 - Goldbach and Euler

/***
Md. Namzul Hasan
Shahjalal University of Science & Technology,Sylhet.
hasan08sust@gmail.com
***/
#include<bits/stdc++.h>
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

#define maxi  100000005
bool prime[maxi] ;

void isPrime()
{
    prime[0] = prime[1] =true ;
    prime[2] = false ;
    int i,j ;
    for(i=3 ; i<=sqrt(maxi) ; i+=2)
    {
        if(prime[i]==false)
        {
            for(j=i*i ; j<=maxi ; j+=(2*i))
            {
                prime[j] = true ;
            }
        }
    }
}


int main()
{
    int n ,i,k;
    isPrime() ;
    while(sc("%d",&n)==1)
    {
        int f =0 ;
        if(n%2)
        {
            k = n-2 ;
            if(k>2 && prime[k]==false)
                pf("%d is the sum of %d and %d.\n",n,2,k) ;
            else
                pf("%d is not the sum of two primes!\n",n) ;
        }
        else
        {
            for(i= n/2+1 ; i<n ; i++)
            {
                if(prime[i]==false && prime[n-i]==false && (n-i)%2!=0)
                {
                    pf("%d is the sum of %d and %d.\n",n,n-i,i) ;
                    f =1 ;
                    break ;
                }

            }
            if(!f)
            {
                pf("%d is not the sum of two primes!\n",n) ;
            }
        }
    }
    return 0;
}

UVA 914 - Jumping Champion

/***
Md. Namzul Hasan
Shahjalal University of Science & Technology,Sylhet.
hasan08sust@gmail.com
***/
#include<bits/stdc++.h>
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 data[1000005] ;
int prime[80000] ;
int cnt ;

void isPrime()
{
    int i,j ;
    memset(data,0,sizeof(data)) ;
    cnt =0 ;
    for(i=2 ; i<1000005 ; i++)
    {
        if(!data[i])
        {
            prime[cnt++] =i ;
            for(j= i+i ; j<1000005 ; j+=i)
                data[j] =1 ;
        }
    }
}


int main()
{
    //pf("Hello\n") ;
    isPrime() ;
    int save[5000] ;

    int test,mx,i,cont ;
    sc("%d",&test) ;
    while(test--)
    {
        int U , L ;
        sc("%d %d",&L,&U) ;
        memset(save,0,sizeof(save)) ;

        for(i=0 ; i<cnt ; i++)
        {
            if(prime[i+1]>U)
                break ;
            if(prime[i]>=L && prime[i+1]<=U)
            {
                save[prime[i+1]-prime[i]]++ ;
            }
        }

        mx =0 ;

        for(i=1 ; i<120 ; i++)
        {
            if(save[mx]<save[i])
                mx =i ;
        }
        cont =0 ;
        for(i=1 ; i<120 ; i++)
        {
            if(save[mx]==save[i])
                cont++ ;
        }

        if(mx<1 || cont>1)
            pf("No jumping champion\n") ;
        else
            pf("The jumping champion is %d\n",mx) ;
    }
    return 0;
}

UVA 10140 - Prime Distance

/***
Md. Namzul Hasan
Shahjalal University of Science & Technology,Sylhet.
hasan08sust@gmail.com
***/
#include<bits/stdc++.h>
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

ll prime[1000000] ;
ll data[1000000] ;
ll pl ;

void isPrime()
{
    ll l,k ;

    prime[0] = prime[1] =1 ;
    for(l=2 ; l<=1000000 ; l++)
    {
        if(!prime[l])
        {
            data[pl++] = l ;
            for(k =l*2 ; k<=1000000 ; k+=l)
            {
                prime[k] =1 ;
            }
        }
    }
}

bool primeCheck(ll n)
{
    if(n<=1000000)
    {
        if(prime[n]==0)
            return true ;
        else
            return false ;
    }
    else
    {
        int k ;
        for(k=0 ; k<pl && data[k]<=sqrt(n) ; k++)
        {
            if(n%data[k]==0)
            {
                return false ;
            }
        }
        return true ;
    }
}


int main()
{
    ll n ,m ,pr1,pr2,pr3,pr4,i,p1,p2,dis;

    isPrime() ;

    while(sc("%lld %lld",&n,&m)==2)
    {
        ll flag =0 ,mn =100000000 , mx =-1 ;
        ll cnt =0 ;
        for(i = n ; i<=m ; i++)
        {
            if(primeCheck(i))
            {
                if(!flag)
                {
                    p1 = i ;
                    flag =1 ;
                }
                else
                {
                    p2 = i ;
                    dis = p2 -p1 ;
                    if(dis<mn)
                    {
                        mn =dis ;
                        pr1 = p1 ;
                        pr2 = p2 ;
                        cnt++ ;
                    }
                    if(dis>mx)
                    {
                        mx =dis ;
                        pr3 =p1 ;
                        pr4 = p2 ;
                        cnt++ ;
                    }
                    p1 =p2 ;
                }
            }
        }
        if(cnt==0)
        {
            pf("There are no adjacent primes.\n") ;
        }
        else
            pf("%lld,%lld are closest, %d,%d are most distant.\n",pr1,pr2,pr3,pr4) ;
    }
}

UVA 10852 - Less Prime

/***
Md. Namzul Hasan
Shahjalal University of Science & Technology,Sylhet.
hasan08sust@gmail.com
***/
#include<bits/stdc++.h>
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 ;

bool isPrime(int n)
{
    int i ;
    if(n<2)
        return false ;
    else if(n==2)
        return true ;
    else if(n%2==0)
        return false ;
    else
    {
        for(i=3 ; i<=sqrt(n) ; i++)
        {
            if(n%i==0)
            {
                return false ;
            }
        }
        return true ;
    }

}


int main()
{
    int i,value ;
    for(i=2 ; i<=10000 ; i++)
    {
        if(isPrime(i))
            data.pb(i) ;
    }

    int test,n ,prime,x,p,mx;
    sc("%d",&test) ;
    while(test--)
    {
       sc("%d",&n) ;
       mx =0 ;
       for(i=0 ;i<data.size() ; i++)
       {
           x = data[i] ;
           if(x>n)
            break ;
           p = n/x ;
           value = n - (p*x) ;
            if(value>mx)
            {
                prime = x ;
                mx = value ;
            }
       }
       pf("%d\n",prime) ;
    }
    return 0;
}

UVA 10948 - The primary problem

/***
Md. Namzul Hasan
Shahjalal University of Science & Technology,Sylhet.
hasan08sust@gmail.com
***/
#include<bits/stdc++.h>
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 ;

bool isPrime(int n)
{
    int i ;

    if(n==2)
        return true ;
    else if(n==0 || n%2==0 || n==1)
        return false ;
    else
    {
        for(i=3 ; i<=sqrt(n) ; i++)
        {
            if(n%i==0)
            {
                //flag = false ;
                return false ;
            }
        }
        return true ;
    }
}


int main()
{
    int n ,i,l,a,p;
    for(i=2 ; i<=1000000 ;i++)
    {
        if(isPrime(i))
        {
            data.pb(i) ;
        }
    }

    while(sc("%d",&n)==1 &&n)
    {
        l =0 ;
        pf("%d:\n",n) ;
        for(i=0 ;i<data.size() ;i++)
        {
            a = data[i] ;
            p = n -a ;
            if(isPrime(p))
            {
               pf("%d+%d\n",a,p) ;
               l=1 ;
               break ;
            }
            if(a>(n/2+1))
                break ;
        }
        if(l==0)
            pf("NO WAY!\n") ;

    }
    return 0;
}

UVA 530 - Binomial Showdown

/***
Md. Namzul Hasan
Shahjalal University of Science & Technology,Sylhet.
hasan08sust@gmail.com
***/
#include<bits/stdc++.h>
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 ,r,i ;
    while(sc("%d %d",&n,&r)==2 && (n|r))
    {
        if(n!=0 && r==0)
        {
            pf("1\n") ;
            continue ;
        }

        if(r>n/2)
            r= n-r ;
          ll ans =1  ;
          for(i=0 ;i<r ;i++)
          {
              ans*=(n-i) ;
              ans = ans/ (i+1) ;
          }
          pf("%lld\n",ans) ;
    }
    return 0;
}

UVA 10338 - Mischievous Children

/***
Md. Namzul Hasan
Shahjalal University of Science & Technology,Sylhet.
hasan08sust@gmail.com
***/
#include<bits/stdc++.h>
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

string str ;
ll cnt[50] ;

ll findFactorial(ll n)
{
    if(n==0)
        return 1 ;

    ll i ;
    ll fact =1 ;

    for(i=1 ; i<=n ; i++)
        fact = fact*i ;
    return fact ;
}


int main()
{
    ll test;
    ll cs =1 ;
    ll i,k,t,ln1 ;
    ll total,p ;
    sc("%lld",&test) ;

    while(test--)
    {
        memset(cnt,0,sizeof(cnt)) ;
        cin>>str ;
        ln1 = str.size() ;
        p = findFactorial(ln1) ;
        for(i=0 ; i<str.size() ; i++)
        {
            k = str[i] - 'A' ;
            cnt[k]++ ;
        }
        total =1 ;

        for(i=0 ; i<26 ; i++)
        {
            if(cnt[i]>0)
            {
                t = findFactorial(cnt[i]) ;
                total*=t ;
            }
        }

        pf("Data set %lld: %lld\n",cs++,(p/total)) ;
    }
    return 0;
}



/*
 worst case
ABCDDAAABFFGHIJKLLML

*/

UVA 623 - 500!

/***
Md. Namzul Hasan
Shahjalal University of Science & Technology,Sylhet.
hasan08sust@gmail.com
***/
#include<bits/stdc++.h>
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 ,jak;
int n,i,a,j,c,k,p ;

void  producePrime()
{
    data.pb(1) ;

    for(i=2 ; i<=n ; i++)
    {
        c =0 ,k =0 ;
        for(j=0 ; j<data.size() ; j++)
        {
            p = data[j]*i + c ;
            //t = p%10 ;
            jak.pb(p%10) ;
            c = p/10 ;
        }
        while(c!=0)
        {
            jak.pb(c%10) ;
            c/=10 ;
        }
        data.clear() ;
        data = jak ;
        jak.clear() ;
    }

}

int main()
{

    while(sc("%d",&n)==1)
    {
        producePrime() ;
            reverse(data.begin(),data.end()) ;
            pf("%d!\n",n) ;
        for(i=0 ; i<data.size() ; i++)
        {
            //if(i%80==0)
                //pf("\n") ;
            pf("%d",data[i]) ;
        }
        pf("\n") ;
        data.clear() ;
    }
    return 0;
}

UVA 10323 - Factorial! You Must be Kidding!!!

/***
Md. Namzul Hasan
Shahjalal University of Science & Technology,Sylhet.
hasan08sust@gmail.com
***/
#include<bits/stdc++.h>
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 ,jak;
int n,i,a,j,c,k,p ;

void getFactorial()
{
    data.pb(1) ;

    for(i=2 ; i<=n ; i++)
    {
        c =0 ,k =0 ;
        for(j=0 ; j<data.size() ; j++)
        {
            p = data[j]*i + c ;
            //t = p%10 ;
            jak.pb(p%10) ;
            c = p/10 ;
        }
        while(c!=0)
        {
            jak.pb(c%10) ;
            c/=10 ;
        }
        data.clear() ;
        data = jak ;
        jak.clear() ;
    }

    reverse(data.begin(),data.end()) ;
    for(i=0 ; i<data.size() ; i++)
        pf("%d",data[i]) ;
    pf("\n") ;
    data.clear() ;
}

int main()
{

    while(sc("%d",&n)==1)
    {

        if(n<8)
        {
            if(n<0 && n%2==0)
                pf("Underflow!\n") ;
            else if(n<0 && n%2!=0)
                pf("Overflow!\n") ;
            else if(n==0 || n<=7)
                pf("Underflow!\n") ;
            continue ;
        }
        if(n>13)
        {
            pf("Overflow!\n") ;
            continue ;
        }
        getFactorial() ;

    }
    return 0;
}

UVA 10220 - I Love Big Numbers !

/***
Md. Namzul Hasan
Shahjalal University of Science & Technology,Sylhet.
hasan08sust@gmail.com
***/
#include<bits/stdc++.h>
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 ,jak;
int x[101] ;

int main()
{
    int n,i,a,j,c,k,p ;
    int sum ;
    while(sc("%d",&n)==1)
    {
        if(n==0)
        {
            pf("1\n") ;
            continue ;
        }
        data.pb(1) ;

        for(i=2 ; i<=n ; i++)
        {
            c =0 ,k =0 ;
            for(j=0 ; j<data.size() ; j++)
            {
                p = data[j]*i + c ;
                //t = p%10 ;
                jak.pb(p%10) ;
                c = p/10 ;
            }
            while(c!=0)
            {
                jak.pb(c%10) ;
                c/=10 ;
            }
            data.clear() ;
            data = jak ;
            jak.clear() ;
        }
        sum =0 ;
       for(i=0 ;i<data.size() ;i++)
        sum+=data[i] ;
       pf("%d\n",sum) ;
        data.clear() ;
    }
    return 0;
}

UVA 568 - Just the Facts

/***
Md. Namzul Hasan
Shahjalal University of Science & Technology,Sylhet.
hasan08sust@gmail.com
***/
#include<bits/stdc++.h>
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,m,i,k,p ;
    while(sc("%d",&n)==1)
    {
        if(n==0)
        {
            pf("%5d -> 1\n",n) ;
            continue ;
        }
        k =1 ;
        for(i=1 ; i<=n ; i++)
        {
            m = i ;
            while(m%10==0)
                m/=10 ;
            k = k*m ;
            while(k%10==0)
            k/=10 ;
            k%=100000 ;
        }
        //pf("\n") ;
        pf("%5d -> %d\n",n,k%10) ;
    }
    return 0;
}

UVA 324 - Factorial Frequencies

/***
Md. Namzul Hasan
Shahjalal University of Science & Technology,Sylhet.
hasan08sust@gmail.com
***/
#include<bits/stdc++.h>
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 ,jak;
int x[101] ;

int main()
{
    int n,i,a,j,c,k,p ;
    while(sc("%d",&n)==1 &&n)
    {
        data.pb(1) ;

        for(i=2 ; i<=n ; i++)
        {
            c =0 ,k =0 ;
            for(j=0 ; j<data.size() ; j++)
            {
                p = data[j]*i + c ;
                //t = p%10 ;
                jak.pb(p%10) ;
                c = p/10 ;
            }
            while(c!=0)
            {
                jak.pb(c%10) ;
                c/=10 ;
            }
            data.clear() ;
            data = jak ;
            jak.clear() ;
        }
        memset(x,0,sizeof(x)) ;
        for(i=0 ; i<data.size() ; i++)
        {
            x[data[i]]++ ;
        }
         pf("%d! --\n",n) ;
         for(i=0 ;i<=9 ;i++)
         {
             if(i==5)
                pf("\n") ;
             pf("   (%d)    %5d",i,x[i]) ;
         }
         pf("\n") ;
        data.clear() ;
    }
    return 0;
}

UVA 10161 - Ant on a Chessboard

/***
Md. Namzul Hasan
Shahjalal University of Science & Technology,Sylhet.
hasan08sust@gmail.com
***/
#include<bits/stdc++.h>
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 ;
    ll cnt =1 ;
    ll s ;

    while(sc("%lld",&s)==1 && s)
    {
        ll n = ceil(sqrt(s)) ;
        ll m = n*n ;
        ll x ,y ;
        if(m&1)
        {
            ll k = m -n +1 ;
            if(k==s)
                x=y=n ;

            else if(s>k){
                x = n ;
                y = m -s +1 ;
            }

            else if(s<k){
                y =n ;
                ll a  = m - (2*n)+2 ;
                x = s- a +1 ;
            }

            cout<<y<<" "<<x<<endl ;        }
        else
        {
         ll k = m -n +1 ;
            if(k==s)
                x=y=n ;

                else if(s<k){
                    x =n ;
                    ll a = m - (2*n)+ 2 ;
                    y = s-a+1 ;
                }

                else if(s>k){
                    y =n ;
                    x =m-s+1 ;
                }
               cout<<y<<" "<<x<<endl ;
        }
    }
    return 0;
}

UVA 913 - Joana and the Odd Numbers

/***
Md. Namzul Hasan
Shahjalal University of Science & Technology,Sylhet.
hasan08sust@gmail.com
***/
#include<bits/stdc++.h>
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 ,first_element,last_element,sum,n;
    while(sc("%lld",&N)==1)
    {
        sum =0 ;
        n = (N-3)/2 ;
        first_element = (N*n) + (n+3) ;
        last_element = ((N-1)*2) + first_element ;
        sum = (3*last_element) -6 ;
        pf("%lld\n",sum) ;
    }
    return 0;
}

UVA 10970 - Big Chocolate

/***
Md. Namzul Hasan
Shahjalal University of Science & Technology,Sylhet.
hasan08sust@gmail.com
***/
#include<bits/stdc++.h>
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 ,m ;
    while(sc("%d %d",&n,&m)==2)
    {
        pf("%d\n",(n*m)-1) ;
    }
    return 0;
}

UVA 11060 - Beverages

/***
Md. Namzul Hasan
Shahjalal University of Science & Technology,Sylhet.
hasan08sust@gmail.com
***/
#include<bits/stdc++.h>
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

string str1, str2 ;
map<string,int> mp ;
map<int,string> mp_s ;
vector<int> G[110] ;
vector<string> data ;
int edge[110] ;
int visited[110] ;

void reset(int n)
{
    memset(edge,0,sizeof(edge)) ;
    memset(visited,0,sizeof(visited)) ;
    data.clear() ;
    mp.clear() ;
    mp_s.clear() ;
    int i;
    for(i=1 ; i<=n ; i++)
        G[i].clear() ;
}

int main()
{
    int n,m,i ;
    int u,v,cnt =1  ;
    int j,k ;

    while(sc("%d\n",&n)==1)
    {
        reset(n) ;

        for(i=1 ; i<=n ; i++)
        {
            cin>>str1 ;
            mp[str1] =i ;
            mp_s[i] = str1 ;
        }

        sc("%d\n",&m) ;
        for(i =1 ; i<=m ; i++)
        {
            cin>>str1>>str2 ;
            u = mp[str1] ;
            v  = mp[str2] ;
            G[u].pb(v) ;
            edge[v]++ ;
        }
        pf("Case #%d: Dilbert should drink beverages in this order:",cnt++) ;

        for(i =1 ; i<=n ; i++)
        {
            for(j =1 ; j<=n ; j++)
            {
                if(!visited[j] && edge[j]==0)
                {
                    str1 = mp_s[j] ;
                    data.pb(str1) ;
                    visited[j]=1 ;
                    for(k =0 ; k<G[j].size(); k++)
                    {
                        v= G[j][k] ;
                        edge[v]--;
                    }
                    break ;
                }
            }
        }

        for(i=0 ; i<data.size(); i++)
        {
           cout<<" "<<data[i] ;
        }
        pf(".\n\n") ;
    }
    return 0;
}

UVA 10305 - Ordering Tasks :: Topological sort

/***
Md. Namzul Hasan
Shahjalal University of Science & Technology,Sylhet.
hasan08sust@gmail.com
***/
#include<bits/stdc++.h>
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 graph[110][110] ;
    int edge[110] ;
    int n ,m ,a,b,i,j;
    while(sc("%d %d",&n,&m) &&(n||m))
    {
        memset(graph,0,sizeof(graph)) ;
        memset(edge,0,sizeof(edge)) ;

        for(i=1 ; i<=m ; i++)
        {
            sc("%d %d",&a,&b)  ;
            graph[a][b] =1 ;
            edge[b]++ ;
        }

        for(i=1 ; i<=n ; i++)
        {
            int pos=1 ;
            while(pos<=n && edge[pos]!=0)
                pos++ ;
            edge[pos] = -1 ;
            if(pos == n+1)
                break ;
            pf("%d ",pos) ;
            for(j=1 ; j<=n ; j++)
            {
                if(graph[pos][j])
                {
                    edge[j]-- ;
                }
            }

        }
        pf("\n") ;
    }
    return 0;
}

UVA 599 - The Forrest for the Trees

/***
Md. Namzul Hasan
Shahjalal University of Science & Technology,Sylhet.
hasan08sust@gmail.com
***/
#include<bits/stdc++.h>
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>G[100] ;
int visited[1001] ;
vector<int>data ;
int point,tree ;
map<char,int>mp ;

void BFS(int src)
{
    int cnt =0 ;
    queue<int>q ;
    q.push(src) ;
    visited[src] =1 ;
    cnt++ ;
    int u ,v ,i;
    while(!q.empty())
    {
        u = q.front() ;
        q.pop() ;
        for(i=0 ; i<G[u].size() ; i++)
        {
            v = G[u][i] ;
            if(!visited[v])
            {
                visited[v] =1 ;
                q.push(v) ;
                cnt++ ;
            }
        }
    }
    if(cnt==1)
        point++ ;
    else if(cnt>1)
        tree++ ;
}


int main()
{
    int test,i,u,v ;
    sc("%d",&test) ;
    while(test--)
    {
        string str ;
        int k =1 ;
        point =0 ;
        tree =0 ;

        while(cin>>str)
        {
            if(str[0]=='*')
                break ;
            if(mp[str[1]]==0)
            {
                mp[str[1]] =k ;
                k++ ;
            }
            if(mp[str[3]]==0)
            {
                mp[str[3]] =k ;
                k++ ;
            }
            int u = mp[str[1]] ;
            int v = mp[str[3]] ;
            G[u].pb(v) ;
            G[v].pb(u) ;
        }
        cin>>str ;

        for(i=0 ; i<str.size() ; i++)
        {
            if(str[i]>='A' && str[i]<='Z')
            {
                if(mp[str[i]]==0)
                {
                    mp[str[i]] =k ;
                    k++ ;
                }
                u = mp[str[i]] ;
                data.pb(u) ;

            }
        }

        sort(data.begin(),data.end()) ;

        for(i=0 ; i<data.size() ; i++)
        {
            u = data[i] ;
            if(!visited[u])
            {
                BFS(u) ;
            }
        }

        pf("There are %d tree(s) and %d acorn(s).\n",tree,point) ;

        data.clear() ;
        mp.clear() ;
        for(i=1 ; i<k ; i++)
            G[i].clear() ;
        memset(visited,0,sizeof(visited)) ;

    }


    return 0;
}

UVA 10227 - Forests (Disjoint sets)

/***
Md. Namzul Hasan
Shahjalal University of Science & Technology,Sylhet.
hasan08sust@gmail.com
***/
#include<bits/stdc++.h>
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

set<int> G[1001] ;
int visited[1001] ;

int main()
{
    int test ,cnt,i,j;
    sc("%d",&test) ;
    char ch[51] ;
   getchar() ;
    while(test--)
    {
        int p,t ,x,y;
        sc("%d %d",&p,&t) ;

        memset(visited,0,sizeof(visited)) ;
        for(i=1 ; i<=p ; i++)
            G[i].clear() ;

        getchar() ;
        while(gets(ch))
        {
            if(strlen(ch)==0)
                break ;
            stringstream str (ch) ;
            str>>x>>y ;
            G[x].insert(y) ;
        }

        cnt =0 ;
        for(i=1 ; i<=p ; i++)
        {
            if(!visited[i])
            {
                cnt++ ;
                for(j= i+1 ; j<=p ; j++)
                {
                    if(G[i]==G[j])
                    {
                        visited[j] =1 ;
                    }
                }
            }

        }
        pf("%d\n",cnt) ;
        if(test)
            pf("\n") ;
    }


    return 0;
}

UVA 10685 - Nature (Disjoint sets)

/***
Md. Namzul Hasan
Shahjalal University of Science & Technology,Sylhet.
hasan08sust@gmail.com
***/
#include<bits/stdc++.h>
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> mp ;
int pr[6005] ;
int value[6005] ;

void reset(int n)
{
    int i ;
    for(i=1 ; i<=n ; i++)
    {
        pr[i]=i ;
        value[i] =1 ;
    }
    mp.clear() ;

}

int find_root(int r)
{
    if(pr[r]==r)
        return r ;
    else
    {
        return (pr[r] = find_root(pr[r])) ;
    }
}

void isConnected(int u, int v)
{
    int a = find_root(u) ;
    int b = find_root(v) ;
    if(a!=b)
    {
        pr[b] =a ;
        value[a]+=value[b] ;
    }
}


int main()
{
    int n,m,i ;
    string str1, str2 ;

    while(sc("%d %d",&n,&m)&&(n|m))
    {
        reset(n) ;
        for(i=1 ; i<=n ; i++)
        {
            cin>>str1 ;
            mp[str1] =i ;
        }

        for(i=1 ; i<=m ; i++)
        {
            cin>>str1>>str2 ;
            int u = mp[str1] ;
            int v =mp[str2] ;

            isConnected(u,v) ;
        }

        int mx =0 ;

        for(i=1 ; i<=n ; i++)
        {
            if(pr[i]==i && value[i]>mx)
                mx =value[i] ;
        }

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

UVA 10583 - Ubiquitous Religions (Disjoint sets)

/***
Md. Namzul Hasan
Shahjalal University of Science & Technology,Sylhet.
hasan08sust@gmail.com
***/
#include<bits/stdc++.h>
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> G[50001] ;
queue<int> q ;
int visited[500001] ;

void reset(int n)
{
    int i ;
    for(i=1 ; i<=n ; i++)
    {
        G[i].clear() ;
        visited[i] =0 ;
    }

}

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


int main()
{
    int cnt =1 ;
    int u,v,n,m ,p=0,i;
    while(sc("%d %d",&n,&m) &&n &&m)
    {
        reset(n) ;

        for(i=1 ; i<=m ; i++)
        {
            sc("%d %d",&u,&v) ;
            G[u].pb(v) ;
            G[v].pb(u) ;
        }

        p =0 ;
        for(i=1 ; i<=n; i++)
        {
            if(!visited[i])
            {
                BFS(i) ;
                p++ ;
            }
        }
        pf("Case %d: %d\n",cnt++,p) ;

    }

    return 0;
}

/*
3 2
1 2
2 3

*/

UVA 10608 - Friends (Disjoint sets)

/***
Md. Namzul Hasan
Shahjalal University of Science & Technology,Sylhet.
hasan08sust@gmail.com
***/
#include<bits/stdc++.h>
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> G[30005] ;
int visited[30005] ;
queue<int> q ;

void reset(int n)
{
    int i ;
    for(i=1; i<=n ; i++)
    {
        G[i].clear() ;
        visited[i] =0 ;
    }

}

int BFS(int src)
{
    int cnt=0,i,v,u;
    cnt++ ;
    q.push(src) ;
    visited[src] =1 ;
     //pf("%d\n",cnt) ;
    while(!q.empty())
    {
        u = q.front() ;
        q.pop() ;
        for(i=0 ; i<G[u].size() ; i++)
        {
            v = G[u][i] ;
            if(!visited[v])
            {
                cnt++ ;
                visited[v] =1 ;
                q.push(v) ;
            }
        }
    }
    //pf("%d\n",cnt) ;
    return cnt ;
}


int main()
{
    int test ,n, i,m,u,v ;
    sc("%d",&test) ;
    while(test--)
    {
        sc("%d %d",&n,&m) ;
        reset(n) ;
        for(i=1 ; i<=m ; i++)
        {
            sc("%d %d",&u,&v) ;
            G[u].pb(v) ;
            G[v].pb(u) ;
        }
       //pf("Hello\n") ;
        int mx =0 ;
        for(i=1 ; i<=n ; i++)
        {
            if(!visited[i])
            {
                 //pf("Hello\n") ;
                int k =  BFS(i) ;
                if(k>mx)
                    mx =k ;
            }
        }

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

UVA 793 - Network Connections (Disjoint sets)

/***
Md. Namzul Hasan
Shahjalal University of Science & Technology,Sylhet.
hasan08sust@gmail.com
***/
#include<bits/stdc++.h>
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 pr[100001] ;
int suc,unsuc ;

int find_r(int r)
{

    if(pr[r]==r)
        return r ;
    return (pr[r]=find_r(pr[r])) ;

}


void disjoint_set(int u, int v)
{
    int a = find_r(u) ;
    int b = find_r(v) ;
    if(a==b)
       return ;
    else
    {
        pr[a]=b ;
    }
}


int main()
{
    int test ,n,u,v,i ;
    sc("%d",&test) ;
    char ch ;
    char str[10001] ;
    bool l =false ;
    while(test--)
    {
        if(l)
            pf("\n") ;
        l =true ;

        suc =0 ;
        unsuc =0 ;

        sc("%d\n",&n) ;
        //getchar() ;
        for(i=1 ; i<=n ; i++)
            pr[i] =i ;

        while(gets(str) && strlen(str))
        {
            sscanf(str,"%c %d %d",&ch,&u,&v) ;
            if(ch=='c')
            {
             disjoint_set(u,v) ;
            }
            else
               {
                 int a = find_r(u) ;
                  int b = find_r(v) ;
                  if(a==b)
                    suc++ ;
                  else
                    unsuc++ ;
               }
        }
        pf("%d,%d\n",suc,unsuc) ;
    }
    return 0;
}

UVA 11503 - Virtual Friends (Disjoint sets)

/***
Md. Namzul Hasan
Shahjalal University of Science & Technology,Sylhet.
hasan08sust@gmail.com
***/
#include<bits/stdc++.h>
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,long int> mp ;
long int cnt =0 ;
long int pr[100005] ;
long int frnd[100005] ;
string str1, str2 ;

long int find_r(long int r)
{
    if(pr[r]==r)
        return r ;
    return pr[r]=find_r(pr[r]) ;
}

void disjoint_set(long int n1, long int n2)
{

    long int u = find_r(n1) ;
    long int v = find_r(n2) ;
    if(u!=v)
    {
        pr[u]=v;
        frnd[v]+=frnd[u] ;
        pf("%ld\n",frnd[v]) ;
    }
    else
        pf("%ld\n",frnd[v]) ;

}


int main()
{
    long int test,n ;
    sc("%ld",&test) ;

    while(test--)
    {
        sc("%ld",&n) ;
        mp.clear() ;

        cnt =0 ;
        while(n--)
        {
            cin>>str1>>str2 ;
            if(mp.find(str1)==mp.end())
            {
                mp[str1] =++cnt ;
                pr[cnt] =cnt ;
                frnd[cnt] =1 ;
            }
            if(mp.find(str2)==mp.end())
            {
                mp[str2] = ++cnt ;
                pr[cnt] =cnt ;
                frnd[cnt] =1 ;
            }
            long int n1,n2 ;
            n1 =mp[str1] ;
            n2 =mp[str2] ;
            disjoint_set(n1,n2) ;
        }
    }
    return 0;
}

Binary GCD code

There are many algorithm to find GCD of any two number. Here is an algorithm . For details visit  https://en.wikipedia.org/wiki/Binary_GCD_algorithm

/***
Md. Namzul Hasan
Shahjalal University of Science & Technology,Sylhet.
hasan08sust@gmail.com
***/
#include<bits/stdc++.h>
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 g ,d ;

int binaryGcd(int num1, int num2)
{

    int cnt =0 , tmp ;
    while(!(num1&1) && !(num2&1))
    {
        num1>>=1 ;
        num2>>=1 ;
        cnt++ ;
    }

    do
    {

        while(!(num1&1))
        {
            num1>>=1 ;
        }
        while(!(num2&1))
        {
            num2>>=1 ;
        }

        if(num1>num2)
        {
            num1 = (num1-num2)>>1 ;
        }
        else
        {
            tmp = num1 ;
            num1 = (num2 -num1)>>1 ;
            num2 =tmp ;
        }
    }
    while(!(num1==num2 || num1==0)) ;

    return num2<<cnt ;

}


int main()
{
    int num1, num2 ;
    while(true)
    {

        sc("%d %d",&num1,&num2) ;
        int gcd = binaryGcd(num1,num2) ;
        pf("GCD of %d %d is: %d\n",num1,num2,gcd) ;
    }


    return 0;
}

UVA 490 - Rotating Sentences

/***
Md. Namzul Hasan
Shahjalal University of Science & Technology,Sylhet.
hasan08sust@gmail.com
***/
#include<bits/stdc++.h>
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 ch[101][101] ;
    int cnt =0 ;
    int mx =0 ;
    int ln[101] ;

    while(gets(ch[++cnt]))
    {
        ln[cnt] = strlen(ch[cnt]) ;
        if(ln[cnt]>mx)
            mx =ln[cnt] ;
        if(ln[cnt]==0)
            break ;
    }

    int i,j,l ;
    //char str[101] ;
    string str ;
    for(i=0 ; i<mx ; i++)
    {
        for(j=cnt-1; j>=1 ; j--)
        {
            if(ln[j]>i)
                pf("%c",ch[j][i]) ;
            else
                pf(" ") ;
        }
        pf("\n") ;

    }


    return 0;
}

UVA 341 - Non-Stop Travel

/***
Md. Namzul Hasan
Shahjalal University of Science & Technology,Sylhet.
hasan08sust@gmail.com
***/
#include<bits/stdc++.h>
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
#define inf 1<<29

int data[100][100],path[100][100];
int n,e;

void inil()
{
    int i,j;

    for(i=1; i<=n; i++)
    {
        for(j=1; j<=n; j++)
        {
            path[i][j]=0;
            data[i][j]=inf;
            if(i==j)data[i][j]=0;
        }
    }
}
void warshal()
{
    int i,j,k;
    for(k=1; k<=n; k++)
    {
        for(i=1; i<=n; i++)
        {
            for(j=1; j<=n; j++)
            {
                if(data[i][j]>data[i][k]+data[k][j])
                {
                    data[i][j]=data[i][k]+data[k][j];
                    path[i][j]=path[k][j];
                }

            }
        }
    }
}

void print_path(int s,int e)
{
    if(path[s][e]==s)
    {
        printf("%d",path[s][e]);
        return;
    }

    else
    {
        print_path(s,path[s][e]);
        printf(" %d",path[s][e]);
    }
}

int main()
{
    int i,j,u,v,w,s,e,cs=1;
    while(scanf("%d",&n) && n)
    {
        inil();
        for(i=1; i<=n; i++)
        {
            scanf("%d",&s);
            for(j=1; j<=s; j++)
            {
                scanf("%d %d",&v,&w);
                data[i][v]=w;
            }
        }
        for(i=1; i<=n; i++)
        {
            for(j=1; j<=n; j++)
            {
                if(data[i][j]!=inf && i!=j)
                    path[i][j]=i;
            }
        }
        warshal();
        scanf("%d %d",&s,&e);
        printf("Case %d: Path = ",cs++);
        print_path(s,e);
        printf(" %d; ",e);
        printf("%d second delay\n",data[s][e]);
    }
    return 0;
}

UVA 11455 - Behold my quadrangle

/***
Md. Namzul Hasan
Shahjalal University of Science & Technology,Sylhet.
hasan08sust@gmail.com
***/
#include<bits/stdc++.h>
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 ;
    sc("%d",&test) ;
    int a ;
    vector<int>data ;
    while(test--)
    {
        int mx =0 ;
        data.clear() ;
        for(int i=1 ; i<=4 ; i++)
        {
            scanf("%d",&a) ;
            if(a>mx)
                mx =a ;
            data.pb(a) ;
        }
        int sum =0,l=0 ;
        for(int i=0 ; i<data.size() ; i++)
        {
            if(l==0)
            {
                if(mx==data[i])
                {
                    l=1 ;
                    continue ;
                }
            }

            sum+=data[i] ;
        }

        if(data[0]==data[1]&& data[1]==data[2]&&data[2]==data[3]&&data[3]==data[0])
            pf("square\n") ;

        else
        {
            sort(data.begin(),data.end()) ;
            if(data[0]==data[1] && data[2]==data[3]&& data[1]!=data[2] && data[0]!=data[3])
                pf("rectangle\n") ;
            else
            {
                if(mx<sum)
                    pf("quadrangle\n") ;
                else
                    pf("banana\n") ;
            }
        }


    }
    return 0;
}

UVA 155 - All Squares

/***
Md. Namzul Hasan
Shahjalal University of Science & Technology,Sylhet.
hasan08sust@gmail.com
***/
#include<bits/stdc++.h>
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 n,m ;
int ans =0 ;

void count_squre(int x,int y,int k)
{
    if(k==0)
        return  ;
    if(x-k<=n && x+k>=n && y-k<=m && y+k>=m)
        ans++ ;
    count_squre(x+k,y+k,k/2) ;
    count_squre(x-k,y+k,k/2) ;
    count_squre(x-k,y-k,k/2) ;
    count_squre(x+k,y-k,k/2) ;
}

int main()
{
    int k ;
    while(sc("%d %d %d",&k,&n,&m))
    {
        if(k==0 && n==0 && m==0)
            break ;
        ans =0 ;
        count_squre(1024,1024,k) ;
        pf("%3d\n",ans) ;

    }
    return 0;
}

UVA 10466 - How Far?

/***
Md. Namzul Hasan
Shahjalal University of Science & Technology,Sylhet.
hasan08sust@gmail.com
***/
#include<bits/stdc++.h>
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 ,T ;
    while(cin>>n>>T)
    {
         double r=0 ,t=0 ;
         double x =0 ,y=0 ;

        for(int i =0 ;i<n ;i++)
        {
            sc("%lf %lf",&r,&t) ;
            double angle =  2* pi * (T/t) ;
             x += r * cos(angle) ;
             y += r*sin(angle) ;
             if(i)
                pf(" ") ;
             pf("%.4lf",hypot(x,y)) ;
        }
        pf("\n") ;
    }
    return 0;
}

UVA 11068 - An Easy Task

/***
Md. Namzul Hasan
Shahjalal University of Science & Technology,Sylhet.
hasan08sust@gmail.com
***/
#include<bits/stdc++.h>
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 a1,b1,c1,a2,b2,c2 ;

    while(sc("%d %d %d %d %d %d",&a1,&b1,&c1,&a2,&b2,&c2))
    {
        if(a1==0 && b1==0 &&c1==0 && a2==0 && b2==0 && c2==0)
            break ;

        int divisor = a1*b2 - a2*b1 ;
        if(divisor)
        {
            double x, y ;
            int z = b2*c1 -b1*c2 ;

            if(z)
                x = z/(double)divisor  ;
            else
                x =0.0 ;
            z = c2*a1- c1*a2 ;
            if(z)
                y = z/(double)divisor  ;
            else
                y = 0.0 ;

            pf("The fixed point is at %.2lf %.2lf.\n",x,y) ;
        }
        else
            pf("No fixed point exists.\n") ;

    }
    return 0;
}

UVA 10250 - The Other Two Trees

/***
Md. Namzul Hasan
Shahjalal University of Science & Technology,Sylhet.
hasan08sust@gmail.com
***/
#include<bits/stdc++.h>
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


double mx, my ;

void midValue(double x1, double y1, double x2, double y2)
{
    mx = (x1 + x2)/2 ;
    my = (y1 + y2)/2 ;
}

double dis(double x1, double y1, double x2, double y2)
{
    double d = sqrt((x2-x1)*(x2-x1) + (y2-y1)*(y2-y1)) ;
    return d ;
}

int main()
{
    double x1, y1, x2,y2 ;
    while(cin>>x1>>y1>>x2>>y2)
    {

        midValue(x1, y1, x2,y2) ;
        double dx = x1 -mx ;
        double dy = y1 - my;
        double x3 = mx +dy ;
        double y3 = my - dx ;
        double x4 = mx - dy ;
        double y4 = my + dx ;

            pf("%.10lf %.10lf %.10lf %.10lf\n",x3,y3,x4,y4) ;

    }
    return 0;
}