AIBOHP-Aibohphobia

Aibohphobia

Given below code is for AIBHOP spoj or aibohphobia spoj.

/*
===================================================
Name :- Nishant Raj
Email :- raj.nishant360@gmail.com
College :- Indian School of Mines
Branch :- Computer Science and Engineering
Time :- 27 September 2015 (Sunday) 22:47
===================================================*/
#include <bits/stdc++.h>
using namespace std;
int dp[6101][6101];
char s[6109];
int rec( int i , int j){
    if(i > j)
        return INT_MAX;
    if(i == j)
        return 0;
    if(i == j -1 )
        return s[i] == s[j] ? 0 : 1;
    if(dp[i][j] != -1)
        return dp[i][j];
    if(s[i] == s[j]){
        return dp[i][j] = rec(i+1 , j-1);
    }
    else {
        return dp[i][j] = min(rec(i+1 , j) , rec(i , j-1)) + 1;
    }
}
int main(){
 
    int t;
    scanf("%d", &t);
    while(t--){
        memset(dp , -1 , sizeof dp);
        scanf("%s",s);
        int len = strlen(s);
        printf("%d\n",rec(0 , len-1));
    }
    return 0;
} 

BVAAN-Balika Vadhu and Alok Nath

Balika Vadhu and Alok Nath

given below c++14 code is for BVAAN spoj or balika vadhu and alok nath spoj.

hint :- 3D Dynamic programming problem .

#include <bits/stdc++.h>
using namespace std;
#define pb push_back
int sol(map<tuple<int ,int ,int > , int > &mp , int i , int j , int k , string &a , string &b){
    if(k == 0)
        return 0;
    if(i == -1 || j == -1)
        return -1;
    auto it = mp.find(make_tuple(i , j , k));
    if(it!=mp.end())
        return it->second;
    int first = -1;
    if(a[i] == b[j]){
        first = sol(mp , i-1 , j-1 , k-1 , a , b);
        if(first != -1)
            first += a[i];
    }
    int sec = -1 , thd = -1;
    sec = sol(mp , i-1 , j , k , a , b);
    thd = sol(mp , i , j-1 , k , a , b);
    mp[make_tuple(i , j , k)] = max(first , max(sec , thd));
    return max(first , max(sec , thd));
}
int main(){

    int t;
    cin>>t;
    while(t--){
        string a , b ;
        int k;
        cin>>a>>b>>k;
        map<tuple<int , int , int > , int > mp;
        int res = sol(mp , a.size() -1 , b.size()-1 , k , a , b);
        if(res == -1)
            cout<<0<<endl;
        else
            cout<<res<<endl;
    }
    return 0;
}

SMILEY1807-1807

1807

Given below c++ code is for smiley1807 spoj or 1807 spoj.

Hint :- This is a basic Dynamic Programming problem , Just use pen and paper you will get the solution.

/*
===================================================
Name :- Nishant Raj
Email :- raj.nishant360@gmail.com
College :- Indian School of Mines
Branch :- Computer Science and Engineering
Time :- 11 September 2015 (Friday) 19:56
===================================================*/
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair < int , int >
#define pb push_back
#define mp make_pair
#define mod 1000000009

int main(){
    
    char s[1000009];
    cin>>s;
    int n = strlen(s);
    int arr[4];
    memset(arr , 0 , sizeof arr);
    if(n <=3){
        cout<<0<<endl;
        return 0;
    }
    if(s[0] == '1'){
        arr[0] = 1;
    }
    for(int i = 1 ; i < n ; i++){
        if(s[i] == '1'){
            arr[0] = arr[0] + 1;
        }
        else if(s[i] == '8'){
            if(arr[0] > 0 || arr[1] > 0){
                arr[1] = max(arr[0] , arr[1]) + 1;
            }
        } else if(s[i] == '0'){
            if(arr[1] > 0 || arr[2] > 0){
                arr[2] = max(arr[1] , arr[2]) + 1;
            }
        } else if(s[i] == '7'){
            if(arr[2] > 0 || arr[3] > 0){
                arr[3] = max(arr[2] , arr[3])+1;
            }
        }
    }
    cout<<arr[3]<<endl;
    return 0;
}

DSUBSEQ-Distinct Subsequences

Distinct Subsequences

Given below c++ code is for DSUBSEQ spoj or Distinct Subsequences spoj.

Hint:- This is one of basic DP problem you can read about solution here -

 how to find the number of distinct subsequences of a string?

/*
===================================================
Name :- Nishant Raj
Email :- raj.nishant360@gmail.com
College :- Indian School of Mines
Branch :- Computer Science and Engineering
Time :- 19 August 2015 (Wednesday) 00:53
===================================================*/
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair < int , int >
#define pb push_back
#define mp make_pair
#define mod 1000000007
ll dp[100009];
int last[500];
int main(){
    
    int t;
    scanf("%d ",&t);
    while(t--){
        char s[100009];
        scanf("%s", s);
        ll total = 0;
        int len = strlen(s);
        memset(dp , 0 , sizeof dp);
        memset(last , 0 , sizeof last);
        dp[0] = 1;
        for(int i = 1 ; i<= len ; i++){
            dp[i] = (dp[i-1] * 2)%mod;
            if(last[s[i-1]]!=0 ) 
                dp[i] = (dp[i] - dp[last[s[i-1]] - 1] + mod)%mod;
            last[s[i-1]] = i;
        }
        cout<<dp[len]<<endl;
    }
    
    return 0;
}

TRT-Treats for the Cows

Treats for the Cows

Given below code is for TRT spoj or trears for the cows spoj.

It an easy problem based on DP.If you want to read about this you can read from HERE.

#include <bits/stdc++.h>
using namespace std;
int dp[2001][2001];
int arr[2009];
int calculate(int start , int end , int year)
{
    if(start > end)
        return 0;
    if(dp[start][end] != -1)
        return dp[start][end];
    return (dp[start][end] = max(calculate(start + 1 , end , year+1) + year * arr[start] , calculate(start, end - 1 , year+1) + arr[end]*year));
}
int main()
{
    int n;
    scanf("%d",&n);
    memset(dp , -1 , sizeof dp);
    for(int i = 0 ; i < n ; i++)
        scanf("%d",&arr[i]);
    printf("%d\n",calculate(0 , n-1 , 1));
    return 0;
}

NUMPLAY-Fun with numbers

Fun with numbers

given below python 2.7 code is for numplay spoj or fun with numbers.

This is an easy DP problem

import sys
arr = []
arr.append(0)
arr.append(4)
def pre():
    arr1 = []; arr3 = []; arr5 = []; arr7 = [];
    arr1.append(0), arr3.append(0), arr5.append(0), arr7.append(0)
    arr1.append(1), arr3.append(1), arr5.append(1), arr7.append(1)
    for i in range(2,10001):
        arr1.append(arr3[i-1])
        arr3.append(arr1[i-1] + arr7[i-1])
        arr5.append(arr3[i-1] + arr7[i-1])
        arr7.append(arr5[i-1])
        arr.append(arr1[i] + arr3[i] + arr5[i] + arr7[i])

t = int(sys.stdin.readline())
pre()
while t:
    n = int(sys.stdin.readline())
    print arr[n]
    t = t-1;

BYTESM2-Philosophers Stone

Philosophers Stone

Given below code is for BYTESM2 spoj or Philosophers Stone spoj

Hint:- Simple DP 

#include <iostream>
#include <cstdlib>
#include <algorithm>
using namespace std;
int main()
{
    int t;
    cin>>t;
    while(t--)
    {
        int h , m;
        cin>>h>>m;
        int arr[h+9][m+9];
        for(int i = 0 ; i < h ; i++)
            for(int j = 0 ; j < m ; j++)
                cin>>arr[i][j];
        int ma = -1;
        for(int i = 0 ; i < m ; i++)
            ma = max(ma , arr[0][i]);
        for(int i = 1 ; i < h ; i++)
        {
            ma = -1;
            for(int j = 0 ; j < m ; j++)
            {
                if(j>0 && j<m-1)
                    arr[i][j] = max(arr[i-1][j] + arr[i][j] , max(arr[i-1][j-1]+arr[i][j] , arr[i-1][j+1]+arr[i][j]));
                else if(j>0)
                    arr[i][j] = max(arr[i-1][j]+arr[i][j] ,arr[i-1][j-1]+arr[i][j]);
                else if(j<m-1)
                    arr[i][j] = max(arr[i-1][j]+arr[i][j],arr[i-1][j+1]+arr[i][j]);
                ma = max(arr[i][j] , ma);
            }
        }
        cout<<ma<<endl;
    }
    return 0;
}

MFISH-Catch Fish

Below given c++ code is for MFISH spoj or Catch Fish spoj

Hint:- Think Dynamic,

#include <bits/stdc++.h>
using namespace std;
int main()
{
    int n,m,b,d,flag=0,flag1=0,pre=0;
    scanf("%d",&n);
    int array[n],pos[n],dp[n];
    for (int i=0; i<n; i++)
        pos[i]=0,dp[i]=0;
    for (int i=0; i<n; i++)
        scanf("%d",&array[i]);
    scanf("%d",&m);
    for (int i=0; i<m; i++)
    {
        scanf("%d %d",&b,&d);
        pos[b-1]=d;
    }
    for (int i=0; i<n; i++)
    {
        if (pos[i]!=0)
        {
            int sum=0,j,l=max(pre,i-pos[i]+1);
            for (j=l; j<min(l+pos[i],n); j++)
                sum+=array[j];
            int k=j;
            if (!flag)
            {
                dp[min(l+pos[i]-1,n-1)]=sum;
                flag=1;
            }
            else
                dp[min(l+pos[i]-1,n-1)]=sum+dp[l-1];
            for (j=min(l+pos[i],n); j<min(n,i+pos[i]); j++)
            {
                sum=(sum+array[j]-array[j-pos[i]]);
                dp[j]=max(dp[j-1],dp[j-pos[i]]+sum);
            }
            pre=k;
        }
        else if (i>0)
            dp[i]=max(dp[i],dp[i-1]);
    }
    printf("%d\n",dp[n-1]);
    return 0;
}

LARSUBP-Large subsequence Problem

Large subsequence Problem

Given below code is for larsubp spoj or Large subsequence Problem spoj. 

Here the problem is simple we have to use DP .

Let given string be S then the number subsequence for any integer s[i] will be sum of all indices less then 'i' which are having integer less then s[i] + 1 (for s[i] )

let take an example s = 7598 

for 7 ans will be one because no character before it.

for 5 ans will be one because character before it is not less then 5;

for 9 ans is '3' because before it there are two character less then '9' so solution will be (ans for 7 + ans for 5 + 1)

similarly for 8 ans will be '3' two character before it are less then '8';

We can implement the above logic using hash table ;

See the python code for understanding .

If you found difficulty you can mail me @ raj.nishant360@gmail.com
Below given c++ code;

#include <bits/stdc++.h> 
using namespace std;
#define MOD 1000000007
int main() { 
    int t;
    scanf("%d ",&t); 
    for(int p=1;p<=t;p++) 
    { 
        char s[10009]; 
        scanf("%s",s);
        int prev[11];
        for(int i=0;i<10;i++) 
            prev[i] =0; 
        int sum = 0; 
        int j=-1,k,temp;
        while(s[++j]!='\0') 
        {
            k = s[j] - 48; 
            temp = k; 
            while(k--)
                prev[temp] = (prev[temp]+ prev[k])%MOD;
            prev[temp]++;
        }
        for(int i=0;i<=9;i++)
            sum = (sum + prev[i])%MOD;
        printf("Case %d: %d\n",p,sum);
    } 
    return 0; 
}

Below given python code;

import sys
t=int(sys.stdin.readline())
for p in xrange(1,t+1):
    s=raw_input()
    pre=[]
    for i in xrange(0,10):
        pre.append(0)
    su=0
    for i in xrange(0,len(s)):
        k = int(s[i])
        temp = k;
        k-=1
        while k>=0:
            pre[temp] = pre[temp] + pre[k]
            k-=1
        pre[temp]+=1
    for i in xrange(0,10):
        su = su+pre[i]
    res =""
    su = su%1000000007
    res=res + "Case "+str(p)+": "+str(su)
    print(res)

INS14E-Glorious Gamblers

Glorious Gamblers

below given code is for ins14e spoj or Glorious Gamblers spoj. This is simple problem of DP(as of LCS)

#include <bits/stdc++.h>
using namespace std;
#define MAX 510
#define gc getchar_unlocked    //scan function is for fast input;
inline void scan(int &x)
{
    register int c = gc();
    x = 0;
    int neg = 0;
    for(;((c<48 || c>57) && c != '-');c = gc());
    if(c=='-') {neg=1;c=gc();}
    for(;c>47 && c<58;c = gc()) {x = (x<<1) + (x<<3) + c - 48;}
    if(neg) x=-x;
}
template <class T>
T mi(T a, T b)
{
 return a<b?a:b;
}
template <class T>
inline T min_o(T a,T b,T c)
{
 return mi(a,mi(b,c));
}
template <class T>
T m(T a, T b)
{
 return a<b?b:a;
}
template <class T>
inline T max_o(T a,T b,T c)
{
 return m(a,m(b,c));
}
int main()
{
 int t;
 scan(t);
 while(t--)
 {
  double a[MAX][MAX];
  int n,m,temp,i,j;
  scan(m);scan(n);
  for(i=1;i<=m;i++)
   for(j=1;j<=n;j++){
    scan(temp);
    a[i][j] = temp;
   }
  for(i=m-1;i>=1;i--)
   a[i][n] += a[i+1][n];
  for(j=n-1;j>=1;j--)
   a[m][j] += a[m][j+1];
  for(i=m-1;i>=1;i--)
  {
   for(j=n-1;j>=1;j--)
    a[i][j] += 0.5*(min_o(a[i+1][j],a[i][j+1],a[i+1][j+1]) + max_o(a[i+1][j],a[i][j+1],a[i+1][j+1]));
  }
  printf("%0.6lf\n",a[1][1]);
 }
 return 0;
}