UVA-12704 : Little Masters

//Problem link>>http://uva.onlinejudge.org/external/127/12704.html

#include <bits/stdc++.h>
using namespace std ;
int main ()
{
    int t , i , a ,b ;
    cin>>t ;
    for (i=1 ; i<=t ; i++)
    {
        double x ,r ;
        cin>>a>>b>>r ;
        x=sqrt(a*a+b*b) ;
     
        printf ("%.2lf %.2lf\n",r-x , r+x) ;
    }

    return 0 ;
}

UVA-10070 : Leap Year or Not Leap Year

//Problem link>>http://uva.onlinejudge.org/external/100/10070.html


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

string s="" ;
int len ;

int check ( int n)
{
    int i  , x=0 ;
    for (i=0 ; i<len ; i++) x= (x*10+(s[i]-'0') )%n ;
    if (x==0) return 0 ;
    else return 1 ;
}

int main ()
{
    int  i , t=0 ;
    while (cin>>s )
    {
        len=s.size() ;
         if (t!=0) cout<<endl ;
            t=1 ;

        int  a=0, b=0 ,c=0 ,d=0 , e=0 , lp=0 ,op=0 ;

        a = check (4) ;
        b = check (100) ;
        c = check (400) ;
        d = check (15) ;
        e = check (55) ;

        if ( (a==0 && b!=0) || c==0 )
        {
            cout<<"This is leap year."<<endl ;
            lp=1 ;
            op=1 ;
        }

        if (d==0)
        {
            cout<<"This is huluculu festival year."<<endl ;
            op=1 ;
        }
        if (e==0 && lp==1)  cout<<"This is bulukulu festival year."<<endl ;

        else if (op==0)  cout<<"This is an ordinary year."<<endl ;

    }

    return 0 ;
}

UVA-10633 - Rare Easy Problem

//Problem link>>http://uva.onlinejudge.org/external/106/10633.html

#include <bits/stdc++.h>
using namespace std ;
int main ()
{
   unsigned  long long d ,  n  ;
    while (cin>>d && d)
    {
        n=(d*10)/9 ;
        if (d%9==0) cout<<n-1<<" "<<n<<endl ;
        else cout<<n<<endl ;

    }

    return 0 ;
}

SPOJ-13208. In Love with Loops

//Problem link>>http://www.spoj.com/problems/KIDZEE1I/

#include <iostream>
using namespace std ;
int main ()
{
    int t , i  , j , k ,cas=1;
    cin>>t ;
    while (cas<=t)
    {
        int x ,y , z ;
        cin>>x>>y>>z ;

        cout<<"Case "<<cas++<<":"<<endl ;


        for (i=0 ; i<=x ;i++)
        {
            for (j=i+1 ; j<=y ; j++)
            {
                for (k=j+1 ; k<=z ; k++)
                {
                    cout<<i<<" "<<j<<" "<<k<<endl ;
                }
            }
        }
    }

    return 0;
}

TIMUS-1409 : Two Gangsters

//problem link>>http://acm.timus.ru/problem.aspx?space=1&num=1409

#include <iostream>
using namespace std ;
int main ()
{
    int a ,b , i ,x ;
    while (cin>>a>>b)
    {
        x=a+b ;
        if (x>10)
        {
            x=x-10 ;
            cout<<b-x<<" "<<a-x<<endl ;
        }
        else   cout<<b-1<<" "<<a-1<<endl ;


    }

    return 0 ;
}

UVA-11728 :: Alternate Task

//Problem link>>http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=2828

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

int go(int n)
{
     int x=1 , i ;
        for (i=n ; i>1 ; i--)
        {
            if (n%i==0)
            {
                x=x+i ;
            }
        }

        return x ;
}

int main ()
{
    int i , s ,n ,cas=1 ;
    while (cin>>s && s !=0)
    {
       for (i=s ; i>=0 ; i--)
       {
           if (go(i)==s) {cout<<"Case "<<cas++<<": "<<i<<endl ; break ;}
           else if (i==0) cout<<"Case "<<cas++<<": -1"<<endl ;
       }

    }

    return 0 ;
}

UVA-374 :: Big Mod

//Problem  link>>http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=310


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

long long int b , p ,m , i ,x ;
long long bigmod (long long b , long long p)
{
    if (p==1) return b ;
    if (p==0) return 1 ;

    if (p&1)
    {
       return( bigmod(b,p-1) * (b%m) ) %m ;
    }
    else
    {
        x=bigmod(b,p/2) % m ;
        return (x*x) % m ;
    }

}

int main ()
{
    while (cin>>b>>p>>m)
    {
        cout<<bigmod(b,p)<<endl<<endl ;
    }

    return 0 ;
}

UVA-11804 :: Argentina

//Problem link>>http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=2904


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

typedef struct
{
    string name ;
    int ap , dp ;
} team ;

team player[11] ;

int main ()
{
    int t , i ,j ,it=1 ;
    cin>>t ;
    while (t--)
    {
        for (i=0 ; i<10 ; i++) cin>>player[i].name>>player[i].ap>>player[i].dp ;

        for (i=0 ; i<9 ; i++)
        {
            for (j=i+1; j<10 ; j++ )
            {
                if (player[i].ap<player[j].ap) swap(player[i] , player[j]) ;

                else if (player[i].ap==player[j].ap)
                {
                    if (player[i].dp>player[j].dp)  swap(player[i] , player[j]) ;

                    else if (player[i].dp==player[j].dp)
                    {
                        if (player[i].name>player[j].name)  swap(player[i] , player[j] ) ;

                    }
                }
            }
        }

          for (i=0 ; i<4 ; i++)
        {
            for (j=i+1 ; j<5 ; j++ )
                if (player[i].name>player[j].name) swap (player[i] , player[j]) ;
        }

        for (i=5 ; i<9 ; i++)
        {
            for (j=i+1 ; j<10 ; j++ )
                if (player[i].name>player[j].name) swap (player[i] , player[j]) ;
        }


        cout<<"Case "<<it<<":"<<endl ;
        it++ ;
        for (i=0 ; i<5 ; i++)
        {
            if (i==0) cout<<"("<<player[i].name<<"," ;
            else if (i==4) cout<<" "<<player[i].name<<")" ;
            else cout<<" "<<player[i].name<<"," ;
        }
            cout<<endl ;
        for (i=5 ; i<10 ; i++)
        {
             if (i==5) cout<<"("<<player[i].name<<"," ;
            else if (i==9) cout<<" "<<player[i].name<<")" ;
            else cout<<" "<<player[i].name<<"," ;
        }
          cout<<endl ;

    }

    return 0 ;
}

UVA-12114 :: Bachelor Arithmetic

//Problem link>>http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=3266

//probability  greater  than  1  is impossible ... so  increase  event  is  impossible ...

#include <bits/stdc++.h>
using namespace std ;
int main ()
{
    long long int b ,s ,cas=1 ;

    while (cin>>b>>s && b||s)
    {
            b=b-1 ;
            s=s-1 ;
        if (b==0 ) cout<<"Case "<<cas<<": "<<":-\\"<<endl ;
        else if (s==b || s>b ) cout<<"Case "<<cas<<": "<<":-|"<<endl ;
        else if (s<b) cout<<"Case "<<cas<<": "<<":-("<<endl ;

        cas++ ;
    }

    return 0 ;
}

UVA-12696 :: Cabin Baggage

//Problem link>>http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=4434


#include <bits/stdc++.h>
using namespace std ;
int main ()
{
    double l, w , h , d , wgt  ;
    int t ,cnt=0 ;
    cin>>t ;
    while (t--)
    {
        d=0.0 ;
        cin>>l>>w>>h>>wgt ;
        d=l+w+h ;

        if (l<=56.0 && w<=45.0 && h<=25.0)
        {
            if (d<=126.0 && wgt<=7.0)
            {
                cout<<"1"<<endl ;
                cnt++ ;
            }
            else cout<<"0"<<endl ;

        }

        else
        {
            if (d<=125.0 && wgt<=7.0)
            {
                cout<<"1"<<endl ;
                cnt++ ;
            }
            else cout<<"0"<<endl ;
        }

    }
cout<<cnt<<endl ;

    return  0 ;
}

UVA-12541 :: Birthdates

//Problem link>>http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=3986


#include <bits/stdc++.h>
using namespace std ;
int main ()
{
    int n , i ,j , d ,m , y ,x ,a[150] ,pos[150];
    string s[150] ;
    cin>>n ;
    for (i=0 ; i<n ; i++)
    {
        cin>>s[i]>>d>>m>>y ;
        x=(y*365)+(m*30)+d ;
        a[i]=x ;
        pos[i]=i ;
    }

     for (i=0 ; i<n-1 ; i++)
     {
         for (j=i+1 ; j<n ; j++)
         {
             if (a[i]>a[j])
             {
                 swap(a[i],a[j]) ;
                swap(pos[j],pos[i]) ;
             }
         }
     }

        cout<<s[pos[n-1] ]<<endl<<s[pos[0] ]<<endl ;

    return 0 ;
}

UVA-11371 :: Number Theory for Newbies

//Problem link>>http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=2366


#include <bits/stdc++.h>
#define ll long long int
using namespace std ;
int main ()
{
     ll  n  , i ,mn ,mx ,d, x ,op ,q ,v ;
    char a[1000000]  ;
    while (cin>>n)
    {
        sprintf (a,"%lld",n) ;
        ll  len=strlen(a) ;
        sort(a,a+len) ;

           mx=0 ;
        for (i=len-1 ; i>=0 ; i--)
        {
            mx=mx*10+(a[i]-'0') ;
        }

        op=0 , q ,v ;
        for (i=0 ; i<len ; i++)
        {
            if (op==1) break ;
            if (a[i]=='0' && op==0) continue ;
            else
            {
                op=1 ;
                q=i ;
                v=a[i] ;
            }
        }

        if (a[0]=='0')
        {
            a[0]=v ;
            a[q]='0' ;
        }

        mn=0 ;
        for (i=0 ; i<len ; i++)
        {
            mn=mn*10+(a[i]-'0') ;
        }

        d =mx-mn ;
        x=d/9 ;

    cout<<mx<<" - "<<mn<<" = "<<d<<" = "<<"9 * "<<x<<endl ;

    }

    return 0 ;
}

UVA-10127 :: Ones

//Problem link>>http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=1068

#include <bits/stdc++.h>
using namespace std ;
int main ()
{
    long long  n , sum ,cnt ,i  ;
    while (cin>>n)
    {
        sum=0 ; cnt=0 ;
        for (i=0 ; ; i++)
        {
            sum=(sum*10+1)%n ;
            if (sum==0) break ;
            cnt++ ;
        }
        cout<<++cnt<<endl ;
    }

    return 0 ;
}

LOJ-1328 :: A Gift from the Setter

//Probelm link>>http://lightoj.com/volume_showproblem.php?problem=1328


#include <bits/stdc++.h>
#define ll long long int
#define mod 1000007
using namespace std ;

long long GetDiffSum(long long int a[], int n )
{
    long long int  sum=0 ,ans=0 ;
    int i, j;
    for (i=0 ; i<n ; i++) sum=sum+a[i] ;
    j=n-1 ;
    for (i=0 ; i<n ; i++)
    {
        sum=sum-a[i] ;
        ans=ans+ abs( (a[i]*j )-sum) ;
        j-- ;
    }
   return ans ;
}

int main ()
{
    ll k , c , n , t ,it=0 ,i , x  , a[100004];

    cin>>t ;
    while (it<t)
    {
        it++ ;
        memset(a,0,sizeof (a)) ;
        cin>>k>>c>>n>>a[0] ;

        for (i=1 ; i<n ; i++)
        {
            a[i]= ( (k*a[i-1] ) %mod + c) % mod ;

        }
         sort(a , a+n) ;
         x= GetDiffSum ( a , n ) ;
         cout<<"Case "<<it<<": "<<x<<endl ;

    }

    return 0 ;
}

LOJ-1072 :: Calm Down

//Problem link>>http://lightoj.com/volume_showproblem.php?problem=1072

#include <bits/stdc++.h>
#define pi 2.0*acos(0.0)
#define pre setprecision(10)

using namespace std ;
int main ()
{
    int t , i  ;
    cin>>t ;
    for (i=1 ; i<=t ; i++)
    {
        double x , n , R ,r ;
        cin>>R>>n ;
        x=sin(pi/n) ;
        r=(x*R)/(1+x) ;
        cout<<pre<<"Case "<<i<<": "<<r<<endl ;
    }

    return 0 ;
}

LOJ-1062 :: Crossed Ladders

//Problem link>>http://lightoj.com/volume_showproblem.php?problem=1062

#include <bits/stdc++.h>
#define eps 1e-7
using namespace std ;

 double x , y ,c ,low ,high ,mid ,p,q ,x1,x2 ;

double call (double n)
{
    p=sqrt(y*y-n*n) ;
    q=sqrt(x*x-n*n) ;

    x1=(n*c)/p ;
    x2=(n*c)/q ;

    return x1+x2 ;
}

int main ()
{
    int t , i ,it=0 ;
    cin>>t ;
    while (it<t)
    {
        it++ ;
        cin>>x>>y>>c ;
        low=0.0 ;
        high=min(x,y)*1.0 ;

         while (fabs(low-high)>eps)
         {
             mid=(low+high)/2.0 ;
             if (call(mid)<mid) low=mid;
             else if (call(mid)>mid) high=mid  ;
         }
         cout<<"Case "<<it<<": " ;
         cout<<setprecision(10)<<low<<endl ;
 
    }

    return 0 ;
}

LOJ-1138 :: Trailing Zeroes (III)

//Problem link>>http://lightoj.com/volume_showproblem.php?problem=1138


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

int rez (int x)
{
    int sum=0 ;
    while (x!=0)
    {
        x=x/5 ;
        sum+=x  ;
    }
    return sum ;
}

int n ;
int go ()
{
    int low=0 ,high=1000000000 ,mid ,ans=0 ;
    while (low<=high)
    {
        mid=(low+high)/2 ;
        if (rez(mid) < n) low=mid+1 ;
        else if (rez(mid) > n) high = mid-1 ;
        else
        {
            ans =mid ;
            high=mid-1;
        }
    }
    return ans ;
}

int main ()
{
    int cas, i ,ret ;
    cin>>cas ;
    for (i=1 ;i <=cas ; i++)
    {
        cin>>n ;
         ret=go () ;

        if (ret==0) cout<<"Case "<<i<<": "<<"impossible"<<endl ;
        else cout<<"Case "<<i<<": "<<ret<<endl ;
    }

    return 0 ;
}

LOJ-1088 :: Points in Segments

//Problem link>>http://lightoj.com/volume_showproblem.php?problem=1088


#include <bits/stdc++.h>
using namespace std ;
int main ()
{
    int t , it , i ,n ,q ,a[100005] ,x ,y ,low ,up ;

     scanf ("%d",&t) ;
    for (it=1 ; it<=t ; it++)
    {
       scanf ("%d %d",&n , &q) ;
        for (i=0 ; i<n ; i++) scanf ("%d",&a[i]) ;

       printf ("Case %d:\n",it) ;
        for (i=1 ; i<=q ; i++)
        {
            scanf ("%d %d",&x,&y) ;
            low=lower_bound(a, a+n ,x)-a ;
            up=upper_bound(a, a+n ,y)-a ;
            int ans=up-low ;

           printf ("%d\n",ans) ;

        }

    }

    return 0 ;
}

LOJ-1189 :: Sum of Factorials

//Problem link>>http://www.lightoj.com/volume_showproblem.php?problem=1189


#include <bits/stdc++.h>
#define mx 1000000000000000000

  long long int  a[100] , i ,fact=1 , n ;

using namespace std ;
int main ()
{
      map<long long int , long long int> mp ;

      int t , it=0 , y ;

    for (i=1 ; fact<=mx ; i++)
    {
        fact=fact*i ;
        a[i]=i ;
        mp[i]=fact ;
        y=i ;
    }
    mp[0]=1 ;
    a[0]=0 ;

    cin>>t ;
    while (it<t)
    {
        it++ ;
        cin>>n ;
        vector<long long int>v ;

        int p=0 , ny=y ;
        while (n)
        {
           int k =0 ;
            for (i=0 ; i<ny ; i++)
            {
                if (mp[i]>n)  break  ;
                k=i ;
            }
             v.push_back(k) ;
             ny=k ;
             n=n-mp[k] ;

             if (n>mp[k])
             {
                 p=1 ; break ;
             }
        }
        reverse (v.begin() , v.end()) ;

        cout<<"Case "<<it<<": " ;
       if (p==0)
       {
            for (i=0 ; i<v.size() ; i++)
            {
                if (i==0) printf ("%lld!",v[i]) ;
                else printf ("+%lld!",v[i]) ;
            }
            cout<<endl ;
       }

        else cout<<"impossible"<<endl ;

    }

    return 0 ;
}

UVA-562 :: Dividing coins

//Problem link>>http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=503

#include <bits/stdc++.h>
#define mx 501*101
using namespace std ;

int coin [105] , n , dp[105][mx] ;
int call (int pos , int tot)
{
    if (pos>n) return 0 ;
    int  &rez=dp[pos][tot] ;
    if (rez != -1) return rez ;
    int ret1=0 , ret2=0 ;

    if (tot-coin[pos]==0) return rez=tot ;
    else if (tot-coin[pos]>0)
    {
        ret1=coin[pos]+call (pos+1 , tot-coin[pos]) ;
        ret2=call(pos+1 , tot) ;
        rez=max(ret1,ret2) ;
        return rez ;
    }
    return rez= call (pos+1,tot) ;
}

int main ()
{
    cout<<mx<<endl ;
    int t ,x ,i ;
    cin>>t;
    while (t--)
    {
        memset(dp,-1,sizeof (dp)) ;
        cin>>n ;
        int sum=0 ;
        for (i=1 ; i<=n ; i++)
        {
            cin>>coin[i] ;
            sum=sum+coin[i] ;
        }
         x = call (1,sum/2) ;

        int res=sum-x*2 ;
        cout<<res<<endl ;
    }

    return 0 ;
}

UVA-10943 :: How do you add?

//Problem link>>http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=1884

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

int dp[106][106] ;

int call (int n, int k)
{
    if (n<0 || k<0) return 0 ;
    int rez=0 ,i ;

    int  &dos=dp[n][k] ;
    if (dos != -1) return dos ;

    for (i=0 ; i<=n ; i++)
    {
        rez= (rez + call(n-i , k-1) )% mod ;
    }
    dos = rez ;
    return dos ;
}

int main ()
{
    int n , k  ;
    while (cin>>n>>k && n || k )
    {
        memset(dp,-1,sizeof (dp)) ;
        dp[0][0]=1 ;
        cout<<call(n,k) <<endl ;
    }

    return 0 ;
}

UVA-11413 :: Fill the Containers

//Problem link>>http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=2408

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

int ves ,con , i , a[10000]  ;

int call (int n)
{
    int i=1 , k=1 , now=0 ;
    while (k <= con)
    {
        if (i > ves) return 1 ;
        if (now+a[i]<=n)
        {
            now+=a[i] ;
            i++ ;
        }
        else
        {
            now=0 ;
            k++ ;
        }
    }

    return  0 ;
}

int main ()
{
    while (cin>>ves>>con)
    {
        int sum=0 ;
        for (i=1 ; i<=ves ; i++)
        {
            cin>>a[i] ;
            sum=sum+a[i] ;
        }
        int  low=0 , high=sum ,ans=0 ;

        while (low<=high)
        {
           int mid=(low+high)/2 ;

            if (call(mid) == 0) low=mid+1 ;
            else
            {
                ans=mid ;
                high=mid-1 ;
            }
        }
        cout<<ans<<endl ;
    }

    return 0 ;
}

UVA-11389 :: The Bus Driver Problem

//Problem link>>http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=2384

#include <bits/stdc++.h>
using namespace std ;
int main ()
{
    int n , d , r , i ,mor[105] , ev[105] ,x ,sum ;
    while (cin>>n>>d>>r  && n || d || r )
    {
        for (i=0 ; i<n ; i++) cin>>mor[i] ;
        for (i=0 ; i<n ; i++) cin>>ev[i] ;

        sort(mor , mor+n) ;
        sort(ev , ev+n) ;
        reverse (ev,ev+n) ;

         sum =0 ;
        for (i=0; i<n ; i++)
        {
            if (mor[i]+ev[i]>d) sum+= (mor[i]+ev[i]) - d ;
        }

        cout<<sum*r<<endl ;
    }

    return 0 ;
}

UVA-10041 :: Vito's Family

//Problem link>>http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=982

#include <bits/stdc++.h>

using namespace std ;
int main ()
{
    int t , i ,r , a[1000] ,mid ;
    cin>>t ;
    while (t--)
    {
        cin>>r ;
        for (i=0 ; i< r ; i++) cin>>a[i] ;
        sort (a , a+r) ;

        if (r%2==1) mid =a[r/2] ; //  as  array  starts  with 0
        else mid = a[r/2-1] ;

        int sum=0 ;
       for (i=0 ; i<r ; i++) sum=sum+ abs(mid-a[i]) ;
       cout<<sum<<endl ;

    }

    return 0 ;
}

UVA-460 :: Overlapping Rectangles

//Problem link >>http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=401


#include <bits/stdc++.h>
using namespace std ;
int main ()
{
    int t , i=0 , a1,a2,b1,b2,c1,c2,d1,d2 ;
    cin>>t ;
    while(i<t)
    {
        i++ ;
        if (i>1) cout<<endl ;
        cin>>a1>>a2>>b1>>b2 ;
        cin>>c1>>c2>>d1>>d2 ;
        int mx1= max(a1,c1) ;
        int mx2= max(a2,c2) ;
        int mn1=min(b1,d1) ;
        int mn2=min(b2,d2) ;

        if (mx1>=mn1 || mx2>=mn2) cout<<"No Overlap"<<endl ;
        else cout<<mx1<<" "<<mx2<<" "<<mn1<<" "<<mn2<<endl ;
    }

    return 0 ;
}