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