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