LightOj 1047:Neighbor House

Problem Link:
[http://www.lightoj.com/volume_showproblem.php?problem=1047]

Catagory: 2D Dynamic Programming,Greedy.
Reading Materials: [http://www.geeksforgeeks.org/dynamic-programming-set-6-min-cost-path/]

Code:

#include <bits/stdc++.h>
#define ll   long long int
#define mem(x,y) memset(x,y,sizeof(x))
#define M   10000
#define inf (1<<30)
using namespace std;

int dp[25][4];
vector<int>a[25];
  int n,v,sum;
    int p;
    int m3(int x,int y, int z)
    {
          return min(min(x,y),z);
    }
int call(int i, int j)
{     if(i>=0 && i<n && j>=0 && j<3)
      {
            if(dp[i][j]!=-1)
            return dp[i][j];




             int p=inf;
             for(int k=0; k<3; k++)
             {
                   if(k!=j)

                  p=min(p,call(i+1,k)+a[i][j]);
             }



            return dp[i][j]=p;
}

      else
      return 0;

}

int main()
{    int m;
     scanf("%d",&m);
     int q=1;
     while(m--)
    {mem(dp,-1);

           scanf("%d",&n);

       for(int i=0; i<n; i++)
       {   a[i].clear();
             for(int j=0; j<3; j++)
             {scanf("%d", &v);
             a[i].push_back(v);}
       }



      printf("Case %d: %d\n",q,m3(call(0,0),call(0,1),call(0,2)));
      q++;




       }

}

Light Oj 1004:Monkey Banana Problem

Problem Link:
[http://www.lightoj.com/volume_showproblem.php?problem=1004]

Catagory: Dynamic Programming (DP)

I used DP process. Just ensure is it approachable to the column of the next row at every point.

Code:

#include <bits/stdc++.h>
#define ll   long long int
#define mem(x,y) memset(x,y,sizeof(x))
#define M   10000
using namespace std;

int dp[201][201];
vector<int>a[201];
  int n,v;
int call(int i, int j)
{     if(i>=0 && i<2*n-1 && j>=0 && j<a[i].size())
      {    //cout<<a[i].size();
            if(dp[i][j]!=-1)
            return dp[i][j];

         int p=-1;
         p=max(p,call(i+1,j)+a[i][j]);
        if(i<n-1)
        p=max(p,call(i+1,j+1)+a[i][j]);
        else if(i>=n-1)
        p=max(p,call(i+1,j-1)+a[i][j]);



            return dp[i][j]=p;
}

      else
      return 0;

}

int main()
{    int m;
     scanf("%d",&m);
     for(int q=1; q<=m; q++)
    {mem(dp,-1);
           scanf("%d",&n);

       for(int i=0; i<n; i++)
       {    a[i].clear();
             for(int j=0; j<=i; j++)
       {

              scanf("%d",&v);
       a[i].push_back(v);
       }}
       int l=n-1;
       for( int i=n; i<2*n-1; i++)
       {        a[i].clear();
             for(int j=0; j<l; j++)
             {
                       scanf("%d",&v);
                   a[i].push_back(v);
             }
             l--;
       }
      printf("Case %d: %d\n",q,call(0,0));


       }

}

UVA 729 - The Hamming Distance Problem

Problem Link:
[http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=670]

Catagory: Backtracking,Permutation,Bruteforce.

I took simple approach. First ,write string according to the number of bit and hamming bit. Then generate permuted values of it.

Code:

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

int main()
{    int n,h,t;
       cin>>t;

      while(t--)
         {string a;

   cin>>n>>h;
  for(int i=0;i<n; i++)
      {        if(i<n-h)
            a.push_back('0');

     else
      a.push_back('1');}

     do
     {
           cout<<a<<endl;


     }while(next_permutation(a.begin(),a.end()));
     a.clear();
  if(t)cout<<"\n";
     }

}

Uva 424:Integer Inquiry

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

Catagory:Adhoc,String Processing.

Just store the integer as a string. Then just use the same algorithms as we learned in elementary school – Addition: Add digit-by-digit, and maintain the carry.




#include <bits/stdc++.h>
#define ll unsigned long long int
#define M   10000000

using namespace std;

int main()
{
      string s[105],sum2,temp;
      int n=0;

      int i=0;
      int mx=0;
      while(cin>>s[n])
            {if(s[n]=="0")
              break;

            mx=max(mx,(int)s[n].length());
            n++;
            }

           for(int i=0; i<n; i++)
           {
                 if(mx!=(int)s[i].length())
                 {

                        for(int j=s[i].length()-1;j>=0; j--)
                        {
                             temp.push_back(s[i][j]);

                        }

                        for(int j=0; j<mx-s[i].length(); j++)
                              temp.push_back('0');
                              s[i].clear();
                               reverse(temp.begin(),temp.end());
                 for(int j=0; j<mx; j++)
                   s[i].push_back(temp[j]);
                 }


           }

          int sum=0,c=0;
      for(int i=s[0].length()-1; i>=0; i--)
      {     sum=0;
            for(int j=0; j<n; j++)
            {
                sum+=s[j][i]- '0';


            }
            sum+=c;

            sum2+=char((sum%10) +'0');
            c=sum/10;

      }
      if(c)     //if there's any carry
            sum2+=c+'0';
      reverse(sum2.begin(),sum2.end());
     // if(c)
      //cout<<c;
      cout<<sum2<<endl;
}

Uva 11530: Sms Typing.cpp

Problem link: https://www.google.com/url?sa=t&rct=j&q=&esrc=s&source=web&cd=1&cad=rja&uact=8&ved=0ahUKEwjXjp_StrTNAhWIro8KHauXBssQFggcMAA&url=https%3A%2F%2Fuva.onlinejudge.org%2Findex.php%3Foption%3Dcom_onlinejudge%26Itemid%3D8%26page%3Dshow_problem%26problem%3D2525&usg=AFQjCNGDCAdSikS28s2QwAUOJaRX_P3F3Q&sig2=U5v6MqcnrBRJiCBGidoQmw&bvm=bv.124817099,d.c2I

It is a problem of Adhoc catagory.I just used simple  implementation process. 

#include <bits/stdc++.h>
#define ll unsigned long long int
#define M 10000000

using namespace std;
int main()
{
ll c,cn;
string k[9]={"abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"," "};
cin>>cn;
string s;
getline(cin,s);
ll i=1;
while(cn--)
{ getline(cin,s);
c=0;
for(ll i=0; i<s.length(); i++)
{
for(ll j=0; j<9; j++)
{
for(ll l=0; l<k[j].length(); l++)
{
if(s[i]==k[j][l])
{c+=l+1;
//cout<<l+1<<endl;
}
}
}
}

cout<<"Case #"<<i<<": "<<c<<"\n";
i++;
}
}