UVA- 623 : 500!

//Problem  link >>http://uva.onlinejudge.org/external/6/623.html

//  very  familiar  string  problem  ... i've  seen  many  solution  in other  blogs  those  were  huge  code ... i've  learnt  this  from  somewhere ... this  string  and  integer  multiplication technic  is  very  effective ... that  makes  this  code  too  short  to  see ... beware  of  the  fact  that  the  carry  will  be  a  huge string .. so manage  it  rightly ...  i've  got  WA's  for  this ...

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

string  call (string a , int n)
{
    reverse(a.begin() , a.end()) ;
    string b ;
    int  i  , carry =0 ;
    for (i=0 ; i<a.size() ; i++)
    {
        int x=(a[i]-'0')*n+carry ;
        b+=(x%10)+'0' ;
        carry=x/10 ;

    }
    while (carry>0)
    {
        b+=(carry%10)+'0' ;
        carry/=10 ;
    }
    reverse(b.begin(),b.end()) ;

    return b ;
}

int main ()
 {
    string  a[1090] ;

       a[0]="1" ;
       a[1]="1" ;
        for (int  i =2 ; i<=1050 ; i++)
        {
            a[i]= call (a[i-1],i) ;
        }

        int sb ;
        while (cin>>sb)
        {
            cout<<sb<<"!\n"<<a[sb]<<endl ;
        }

     return 0 ;
 }

UVA- 100 : The 3n + 1 problem

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

/// nothing  to  say ...  our  most  honorable  UVA  problem  (as  stays  right  in  the  first  of  giant  uva-problem  list )...  i solved  that  very  lately ... ignoring  the first !!

#include <iostream>
#include <cstdio>
using namespace std ;
int main ()
{
        int a , b , i ;
        while (cin>>a>>b)
        {
            cout<<a<<" "<<b ;
            if (a>b) swap(a,b) ;

           long long int res=0 ;
            for (i=a ; i<=b ;i++)
            {
               long long  int x = i , cnt =1  ;
                while (x>1)
                {
                    if (x%2)  x=3*x+1 ;
                    else x=x/2 ;
                    cnt++ ;
                }

                res=max(res,cnt) ;
            }
           cout<<" "<<res<<endl ;
       }

    return 0 ;
}

UVA- 111 : History Grading

//Problem  link >>http://uva.onlinejudge.org/external/1/111.html

... here  u may  face  this  problem ...  how  to  take  input ... for  the  1st  student  that  is 3rd line  of input we  take  the  first  integer ... then  using  for  loop  take  the  rest ... and  here  we're  using  array  indexing  technic   to mange  input ...  then  simple  LCS ...

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

int  lcs[25][25]={0} ;

int main ()
{
     int n , j ,  i , a[50] , b[50] , x  ;

        cin>>n  ;
        for (i=1 ; i<=n ; i++)
        {
            cin>>x ;
            a[x]=i ;
        }

        while (cin>>x && x!= EOF)
        {
            b[x]=1 ;
            for (i=2 ; i<=n ;i++)
            {
                cin>>x ;
                b[x]=i ;
            }

            for (i=1 ; i<=n ; i++)
            {
                for (j=1 ; j<=n ; j++)
                {
                    if (a[i]==b[j]) lcs[i][j]=1+lcs[i-1][j-1] ;
                    else lcs[i][j]=max(lcs[i][j-1] , lcs[i-1][j]) ;
                }
            }
            cout<<lcs[n][n]<<endl ;
            memset(lcs,0,sizeof(lcs)) ;
            memset(b,0,sizeof(b)) ;

        }

    return 0 ;
}

sample input

4
4 2 3 1
1 3 2 4
3 2 1 4
2 3 4 1

sample output

1
2
3

UVA -10100 : Longest Match

//Problem  link >>http://uva.onlinejudge.org/external/101/10100.html

///  in  this  LCS  problem  u may find it  hard  to  manage  a  word  ... here  i've  used  file-stream  I/O ... see  the  header  file "sstream"  &  the  command  "stringstream" ... then  uor  string  will  be  separated  into  words ...  make  sure  u  hide  uor  words  in  the  form  of  a  character ... here  "check"  array  do  this  and  then  apply  lcs  to  "check"  array ... 

#include <iostream>
#include <vector>
#include <sstream>
#include <cstring>
#include <string>
#include <cstdio>
using namespace std ;

int lcs[1002][1002] ,check [1002][1002] ;

int main ()
{
    string s1 , s2 , s ;
    int cas=0 ;
    vector<string>v1 ;
    vector<string>v2 ;

    while (getline(cin,s1))
    {
        getline(cin,s2) ;
        for (int i=0 ; i<s1.size() ; i++)
        {
            if (s1[i]>='a'&&s1[i]<='z' || s1[i]>='A' &&s1[i]<='Z' || s1[i]>='0'&&s1[i]<='9') continue ;
            else s1[i]=' ' ;
        }

        for (int i=0 ; i<s2.size() ; i++)
        {
            if (s2[i]>='a'&&s2[i]<='z' || s2[i]>='A' &&s2[i]<='Z' || s2[i]>='0'&&s2[i]<='9') continue ;
            else s2[i]=' ' ;
        }

        v1.clear() ;
        v2.clear() ;

        stringstream sx(s1) ;
        stringstream sy(s2) ;

        while(sx>>s) v1.push_back(s) ;
        while(sy>>s) v2.push_back(s) ;

        int x=v1.size() ;
        int y=v2.size() ;

        for (int i=0 ; i<x ; i++)
        {
            for (int j=0 ; j<y ; j++)
            {
                if (v1[i]==v2[j]) check[i][j]=1 ;
                else check[i][j]=0 ;
            }
        }

        for (int i=x ; i>=0 ; i--)
        {
            for (int j=y ; j>=0 ; j--)
            {
                if (i==x||j==y)
                {
                    lcs[i][j]=0 ;
                    continue ;
                }
                if (check[i][j]==1) lcs[i][j]=1+lcs[i+1][j+1] ;
                else lcs[i][j]=max(lcs[i+1][j],lcs[i][j+1]) ;
            }
        }

        printf("%2d.",++cas) ;
        if (x==0||y==0) cout<<" Blank!"<<endl ;
        else  cout<<" Length of longest match: "<<lcs[0][0]<<endl ;

    }
    return 0 ;
}

Sample Input

This is a test.
test
Hello!

The document provides late-breaking information
late breaking.

Sample Output

 1. Length of longest match: 1
 2. Blank!
 3. Length of longest match: 2

UVA - 10405 - Longest Common Subsequence

//Problem  link >>http://uva.onlinejudge.org/external/104/10405.html

.... my  first  LCS  problem ... very  easy ...

///// LCS  using  DP....

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

int  dp[1002][1002] , x , y ;
 string s1 , s2 ;

int lcs(int i , int j)
{
    if (i==x || j==y) return 0 ;

    int  &rez=dp[i][j] ;
    if (rez !=-1) return rez ;

    if (s1[i]==s2[j])
    {
        return rez=1+lcs(i+1 , j+1) ;
    }
   return rez= max(lcs(i , j+1) , lcs(i+1 , j) ) ;
}

int main ()
{
    while (getline(cin,s1))
    {
        getline(cin,s2) ;
         x=s1.size() ;
         y=s2.size() ;

        memset(dp,-1,sizeof (dp)) ;
       cout<<lcs(0,0)<<endl ;
    }
    return 0;
}

///////  Iterative  LCS ..........

#include<iostream>
#include <string>
#include <vector>
#include <cstdio>
using namespace std ;

int lcs[1002][1002] ;

int main ()
{
    string s1 , s2 ;
    while (getline(cin,s1))
    {
        getline(cin,s2) ;
        int x=s1.size() ;
        int y=s2.size() ;

        for (int i=1 ; i<=x ; i++)
        {
            for (int j=1 ; j<=y ; j++)
            {
                if (s1[i-1]==s2[j-1]) lcs[i][j]=1+lcs[i-1][j-1] ;
                else lcs[i][j]=max(lcs[i][j-1],lcs[i-1][j]) ;
            }
        }
        cout<<lcs[x][y]<<endl ;
    }
    return 0;
}

Sample input

a1b2c3d4e
zz1yy2xx3ww4vv
abcdgh
aedfhr
abcdefghijklmnopqrstuvwxyz
a0b0c0d0e0f0g0h0i0j0k0l0m0n0o0p0q0r0s0t0u0v0w0x0y0z0
abcdefghijklmnzyxwvutsrqpo
opqrstuvwxyzabcdefghijklmn

Sample output

4
3
26
14

UVA- 10066 : The Twin Towers

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

.. simple  DP  problem  ... implementing   straight  LCS ....

#include <iostream>
#include <vector>
using namespace std ;
int main ()
{
    int x , y  ,a , b , cas=0 ;
    int  lcs[103][103] ;

       vector<int>v1 ;
    vector<int>v2 ;

    while (cin>>x>>y && x||y)
    {

        v1.clear() ;
        v2.clear() ;

        for (int i=0 ; i<x ; i++)
        {
            cin>>a ;
            v1.push_back(a) ;
        }
        for (int i=0 ; i<y ; i++)
        {
            cin>>a ;
            v2.push_back(a) ;
        }

        for (int i=0 ; i<x ; i++) lcs[i][0]=0 ;
        for (int i=0 ; i<y ; i++) lcs[0][i]=0 ;

            for (int i=1 ; i<=x ; i++)
            {
                for (int j=1 ; j<=y ; j++)
                {
                    if (v1[i-1]==v2[j-1]) lcs[i][j]=1+lcs[i-1][j-1] ;
                    else  lcs[i][j]=max(lcs[i][j-1] , lcs[i-1][j]) ;
                }
            }

            cout<<"Twin Towers #"<<++cas<<endl ;
            cout<<"Number of Tiles : "<<lcs[x][y]<<endl<<endl ;

    }

    return 0 ;
}

Sample Input

7 6
20 15 10 15 25 20 15
15 25 10 20 15 20
8 9
10 20 20 10 20 10 20 10
20 10 20 10 10 20 10 10 20

Sample Output

Twin Towers #1
Number of Tiles : 4

Twin Towers #2
Number of Tiles : 6

UVA- 10192 : Vacation

//Problem link >>http://uva.onlinejudge.org/external/101/10192.html

...DP  problem  ...  LCS ...

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

 string s1 , s2 ;
 int x , y  , dp[103][103] ;

 int lcs(int i , int j)
 {
     if (i==x|| j==y) return 0 ;
     int  &bus=dp[i][j] ;

     if (bus !=-1) return bus ;

     if (s1[i]==s2[j])  return  bus=1+lcs(i+1 , j+1) ;

     return bus= max(lcs(i , j+1) , lcs(i+1 , j) ) ;

 }

int main ()
{
    int cas=0 ;
    while (getline(cin,s1) && s1!="#")
    {
        getline(cin,s2) ;
        x=s1.size() ;
        y=s2.size() ;

        memset(dp,-1,sizeof (dp)) ;

        cout<<"Case #"<<++cas<<": ";
       cout<<"you can visit at most "<<lcs(0,0)<<" cities."<<endl ;

     }
    return 0 ;
}

sample  input::

abcd
acdb
abcd
dacb
#

sample output:

Case #1: you can visit at most 3 cities.
Case #2: you can visit at most 2 cities.

UVA- 694 : The Collatz Sequence

//Problem  link >>http://uva.onlinejudge.org/external/6/694.html

... Simple  Adhoc problem ....

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

int main ()
{
    long long int a , b ,cas=0 ,x ,y  ;
    while (cin>>a>>b )
    {
        if (a==-1 && b==-1) break ;
        int  cnt =0 ;
         x=a  ; y= b ;
        while (x<=y && x!=1)
        {
            if (x%2) x=x*3+1 ;
            else  x=x/2 ;cnt++ ;
             if (x==1)cnt++ ;
         
        }
        cout<<"Case "<<++cas<<": "<<"A = "<<a<<", limit = "<<b<<", number of terms = " ;
        cout<<cnt<<endl ;
    }

    return 0 ;
}

UVA- 10684 : The jackpot

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

... Adhoc  problem .... Tricky ...

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

 vector<int>v ;
 int n ;

int main ()
{
    int  i , x , a ,mx ;

    while (cin>>n && n!=0)
    {
        mx=0 ;a=0 ;
        for (i=1 ; i<=n ; i++)
        {
            cin>>x ;
            a=a+x ;
            if (a<0) a=0 ;
            mx=max(a,mx) ;

        }

     if (mx==0) cout<<"Losing streak."<<endl ;
     else cout<<"The maximum winning streak is "<<mx<<".\n" ;

    }

    return 0 ;
}

UVA- 567 : Risk

//Problem  link >>http://uva.onlinejudge.org/external/5/567.html

Graph  problem  using  floyd-warshall ...

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

int con[24][24] ;

int main ()
{
    int n ,cas=1 , line ,m ;
    while ( cin>>n && n!=EOF )
    {
        int i , j ;
        for (i=0; i<=20 ; i++)
        {
            for (j=0; j<=20 ; j++)
            {
                if (i==j) con[i][j]=0 ;
                else con[i][j]=inf ;
            }
        }

            line=1 ;
            for (int i=1 ; i<=n ; i++)
            {
                  cin>>m ;
                 con[m][line]=con[line][m]=1 ;

            }
          line++ ;

        while (line<20)
        {
            cin>>n ;
            for (int j=1 ; j<=n ; j++)
            {
                int m ;
                cin>>m ;
                con[m][line]=con[line][m]=1 ;

            }
             line++ ;
        }

        int q , k ;
        for (k=1 ; k<=20 ; k++)
        {
             for (i=1; i<=20 ; i++)
            {
               for (j=1 ; j<=20 ; j++)
                {
                    con[i][j]=min(con[i][j],con[i][k]+con[k][j]) ;
                }
            }
        }

        cin>>q ;
        cout<<"Test Set #"<<cas++<<endl ;

        for (i=1 ; i<=q ; i++)
        {
            int a , b ;
            cin>>a>>b ;
              printf ("%2d to %2d: %d\n",a,b,con[a][b]) ;

        }
        cout<<endl ;

    }

    return 0 ;
}

UVA- 10171 >> Meeting Prof. Miguel

// Problem  link >>http://uva.onlinejudge.org/external/101/10171.html

... Graph problem  ...  u  have to  use  Floyd-warshall  algo ...

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

int main ()
{
    int n , i ;
    while (cin>>n && n!=0)
    {

            int ar1[150][150] ;
            int ar2[150][150] ;

            for (int i='A' ; i<='Z' ; i++)
            {
                for (int j='A' ; j<='Z' ; j++)
                {
                    if (i==j)
                    {
                        ar1[i][j]=0 ;
                        ar2[i][j]=0 ;
                    }
                    else
                    {
                        ar1[i][j]=inf ;
                        ar2[i][j]=inf ;
                    }
                }
            }

        while (n--)
        {
            char c1 ,c2 , c3 , c4 ;
            int x ;

          cin>>c1>>c2>>c3>>c4>>x ;

           if (c1=='Y')
            {
                if (c2=='U') ar1[c3][c4]=min (x,ar1[c3][c4]) ;
                else
                {
                    ar1[c3][c4]=min(x,ar1[c3][c4]) ;
                    ar1[c4][c3]=min(x,ar1[c4][c3]) ;
                }
            }

         else if (c1=='M')
         {
             if (c2=='U') ar2[c3][c4]=min(x,ar2[c3][c4]) ;
             else
             {
                 ar2[c3][c4]=min(x,ar2[c3][c4]) ;
                 ar2[c4][c3]=min(x,ar2[c4][c3]);
             }
         }

        }

///////////////////////////// // floyd  warshalll
        for (int k='A' ; k<='Z' ; k++)
         {
              for (int i='A' ; i<='Z' ; i++)
             {
                 for (int j='A' ; j<='Z' ; j++)
                 {
                     ar1[i][j]=min(ar1[i][j],ar1[i][k]+ar1[k][j]) ;
                     ar2[i][j]=min(ar2[i][j],ar2[i][k]+ar2[k][j]) ;
                 }
             }
         }

            vector<int>v ;
         char a , b ;
         cin>>a>>b ;
       int mn=inf  ;
       v.clear() ;

       for (int i='A' ; i<='Z' ; i++)
       {
           if (ar1[a][i]+ar2[b][i]<mn)
           {
               v.clear() ;
               v.push_back(i) ;
               mn=ar1[a][i]+ar2[b][i] ;
           }
           else if (mn==ar1[a][i]+ar2[b][i]) v.push_back(i) ;

       }

       if (mn==inf) cout<<"You will never meet."<<endl ;
        else
        {
            sort(v.begin() , v.end()) ;
            cout<<mn ;
            int sz=v.size();
             for (int i=0; i<sz ; i++)
             {
                     printf(" %c",v[i]);
            }
             cout<<endl ;
        }

    }

    return 0 ;
}

some  critical  case ::::
3
Y U X Y 5
M B A Y 10
Y B X Y 10
X A
AC  output : 15 Y

2
Y U B D 0
M U B D 0
B B
AC  output : 0 B D

2
Y U X Z 1
Y U X Z 10
X Z
AC  output : 1 Z

UVA - 11244 :: Counting Stars

//Problem  link >>http://uva.onlinejudge.org/external/112/11244.html

#include <bits/stdc++.h>
using namespace std ;
int main ()
{
    int c ,r , i , j ;
    while (cin>>r>>c && r||c)
    {
        char s[1000][105] ;

        int cnt=0 ;

        for (i=0 ; i<r ; i++)
        {
            for (j=0 ; j<c ; j++)
            {
                cin>>s[i][j] ;

            }
        }
            int op=0 ;
            for (i=0 ; i<r ; i++)
            {
                for (j=0 ; j<c ; j++)
                {
                    if (s[i][j]=='*')
                    {
                        if (s[i-1][j-1]=='*' && i-1>=0 && j-1>=0) op++ ;
                        if (s[i-1][j]=='*' && i-1>=0 ) op++ ;
                        if (s[i-1][j+1]=='*' && i-1>=0 && j+1<c ) op++ ;
                        if (s[i][j-1]=='*'  && j-1>=0 ) op++ ;
                        if (s[i][j+1]=='*'  && j+1<c ) op++ ;
                        if (s[i+1][j-1]=='*' && i+1<r && j-1>=0 ) op++ ;
                        if (s[i+1][j]=='*' && i+1<r ) op++ ;
                        if (s[i+1][j+1]=='*' && i+1<r && j+1<c) op++ ;
                           if (op==0) cnt++ ;
                     else op=0 ;

                    }

                }
            }
            cout<<cnt<<endl ;

    }

    return 0 ;
}

UVA - 424 :: Integer Inquiry

//Problem link >>http://uva.onlinejudge.org/external/4/424.html

#include <bits/stdc++.h>
#include <string.h>
using namespace std ;
int main ()
{
    string a="" , b="" ;
    int i , j ,cn =0 ;
    while (getline(cin,a))
    {
        if (a=="0") break ;

        if (cn==0)
        {
            for (i=0 ; i<a.size() ; i++) b+=a[i] ;
        }

        if (cn==1)
        {
             int l1=a.size() ;
        int l2=b.size() ;

         if (l1>l2) b.insert(0,l1-l2,'0') ;
         else a.insert(0,l2-l1,'0') ;

            reverse(a.begin() , a.end()) ;
            reverse(b.begin() , b.end()) ;
            l1=a.size() ;

              int sum=0 , carry=0 ,p ;
              string res="" ;
            for (i=0 ,p=0; i<l1 ; i++)
            {
                sum=(a[i]-'0') + (b[i]-'0') + carry ;
                if (sum>9)
                {
                    carry=1 ;
                   sum=sum%10 ;
                }
                else carry=0 ;
               res+=(sum+'0') ;
            }
            if (carry) res+='1' ;

           b="" ;
            for (i=res.size()-1 ; i>=0 ; i--) b+=res[i] ;

        }
         cn=1 ;

    }
     cout<<b<<endl ;

    return 0 ;
}

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 ;
}