SPOJ CRSCNTRY - Cross-country

#include<bits/stdc++.h>
#define MAXC 5000
using namespace std;
typedef long long ll;
ll A[MAXC],B[MAXC];
ll lenA,lenB;
ll dp[MAXC][MAXC];
bool visited[MAXC][MAXC];
ll calcLCS(ll i,ll j)
{
if(A[i]==0||B[j]==0)
        return 0;
if(visited[i][j])
        return dp[i][j];
ll ans=0;
if(A[i]==B[j])
        ans=1+calcLCS(i+1,j+1);
else
{
ll val1=calcLCS(i+1,j);
ll val2=calcLCS(i,j+1);
ans=max(val1,val2);
}
visited[i][j]=1;
dp[i][j]=ans;
return dp[i][j];
}
int main()
{
    ll i,j,k,l,m,n,test;
    cin>>test;
    for(k=1;k<=test;k++)
{
   ll lenA=0;
   while(1)
        {
            cin>>A[lenA];
            lenA++;
            if(A[lenA-1]==0)
            {
                break;
            }
        }
        ll mx=-999999999;
        lenB=0;
        while(1)
        {
            cin>>B[lenB];
            if(lenB==0&&B[lenB]==0)
            {
                break;
            }
            else
            {
                lenB++;
                if(B[lenB-1]==0)
                {
                    memset(visited,0,sizeof(visited));
                    mx=max(mx,calcLCS(0,0));
                    lenB=0;
                }
            }
        }
        cout<<mx<<endl;
}
return 0;
}

SPOJ BYTESM2 - Philosophers Stone

#include<bits/stdc++.h>
#define inf 99999999999
using namespace std;
typedef long long ll;
ll arr[109][109];
ll dp[1009][109];
ll row,col;
ll solve(ll i,ll j)
{
    if (i>=0&&i<row&&j>=0&&j<col)
    {
        if (dp[i][j]!=-1)
            return dp[i][j];
        ll ret=-inf;
        ret=max(ret,solve(i+1,j)+arr[i][j]);
        ret=max(ret,solve(i+1,j-1)+arr[i][j]);
        ret=max(ret,solve(i+1,j+1)+arr[i][j]);
        return dp[i][j]=ret;
    }
    else
        return 0;
}
int main()
{
    ll i,j,k,l,m,n,test;
    cin>>test;
    for(k=1;k<=test;k++)
    {
        cin>>row>>col;
        for(i=0;i<row;i++)
        {
            for(j=0;j<col;j++)
            {
                cin>>arr[i][j];
            }
        }
        ll mx=-99999999;
        for(i=0;i<col;i++)
        {
            memset(dp,-1,sizeof(dp));
            mx=max(mx,solve(0,i));
        }
        cout<<mx<<endl;
    }
    return 0;
}

SPOJ CPCRC1C - Sum of Digits

//To understand the proceedings please visit http://www.geeksforgeeks.org/count-sum-of-digits-in-numbers-from-1-to-n/
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll sumOfDigitsFrom1ToN(ll n)
{
    if (n<10)
      return n*(n+1)/2;
    ll d=log10(n);
    ll *a=new ll[d+1];
    a[0]=0,a[1]=45;
    for (ll i=2;i<=d;i++)
        a[i]=a[i-1]*10+45*ceil(pow(10,i-1));
    ll p=ceil(pow(10,d));
    int msd = n/p;
    return msd*a[d]+(msd*(msd-1)/2)*p+
           msd*(1+n%p)+sumOfDigitsFrom1ToN(n%p);
}
int main()
{
    ll i,j,k,l,m,n;
    while(cin>>n>>m)
    {
        if(n==-1&&m==-1)
            break;
        else
        {
            ll ans=sumOfDigitsFrom1ToN(max(n,m))-sumOfDigitsFrom1ToN(min(n,m)-1);
            cout<<ans<<endl;
        }
    }
    return 0;
}

SPOJ COINS - Bytelandian gold coins

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
map<ll,ll>mp;
ll n;
ll solve(ll n)
{
    if(n==0)
        return 0;
    else
    {
        if(mp[n])
            return mp[n];
        else
        {
            ll t=max(n,solve(n/2)+solve(n/3)+solve(n/4));
            mp[n]=t;
            return mp[n];
        }
    }
}
int main()
{
    ll i,j,k,l,m,n;
    while(cin>>n)
    {
        mp.clear();
        cout<<solve(n)<<endl;
    }
    return 0;
}

SPOJ ANARC09A - Seinfeld

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main()
{
    ll i,j,k,l,m,n;
    string s;
    k=1;
    while(1)
    {
        cin>>s;
        if(s[0]=='-')
            break;
        else
        {
            stack<char>st;
            for(i=0;i<s.size();i++)
            {
                if(st.empty())
                {
                    st.push(s[i]);
                    continue;
                }
                if(st.top()=='{'&&s[i]=='}')
                {
                    st.pop();
                    continue;
                }
                else
                {
                    st.push(s[i]);
                }
            }
            ll cnt1=0;
            ll cnt2=0;
            while(!st.empty())
            {
                if(st.top()=='{')
                {
                    cnt1++;
                }
                else
                {
                    cnt2++;
                }
                st.pop();
            }
            ll cnt;
            if(cnt1%2==0)
            {
                cnt1/=2;
            }
            else
            {
                cnt1=(cnt1/2)+1;
            }
            if(cnt2%2==0)
            {
                cnt2/=2;
            }
            else
            {
                cnt2=(cnt2/2)+1;
            }
            cnt=cnt1+cnt2;
            cout<<k<<". "<<cnt<<endl;
            k++;
        }
    }
    return 0;
}

SPOJ AIBOHP - Aibohphobia

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll dp[6109][6109];
int main()
{
    ll i,j,k,l,m,n,test;
    cin>>test;
    for(k=1;k<=test;k++)
    {
        string s1,s2;
        cin>>s1;
        s2=s1;
        reverse(s2.begin(),s2.end());
        memset(dp,0,sizeof(dp));
        for(i=s1.size()-1;i>=0;i--)
        {
            for(j=s2.size()-1;j>=0;j--)
            {
                if(s1[i]==s2[j])
                {
                    dp[i][j]=1+dp[i+1][j+1];
                }
                else
                {
                    dp[i][j]=max(dp[i+1][j],dp[i][j+1]);
                }
            }
        }
        cout<<s1.size()-dp[0][0]<<endl;
    }
    return 0;
}

SPOJ ANARC08E - Relax! It is just a game

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main()
{
    ll i,j,k,l,m,n;
    while(1)
    {
        cin>>n>>m;
        if(n==-1&&m==-1)
        {
            break;
        }
        else
        {
            if(n==0&&m==0)
            {
                cout<<"0+0!=0"<<endl;
                continue;
            }
            if(n==1||m==1)
            {
                cout<<n<<"+"<<m<<"="<<n+m<<endl;
            }
            else
            {
                cout<<n<<"+"<<m<<"!="<<n+m<<endl;
            }
        }
    }
}

Light OJ 1148 Mad Counting

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main()
{
    ll i,j,k,l,m,n,test;
    cin>>test;
    for(k=1;k<=test;k++)
    {
        map<ll,ll>mp;
        cin>>n;
        for(i=0;i<n;i++)
        {
            cin>>m;
            mp[m]++;
        }
        ll cnt=0;
        map<ll,ll>::iterator it;
        for(it=mp.begin();it!=mp.end();++it)
        {
            ll p=it->first;
            ll q=it->second;
            p++;
            if(q%p==0)
            {
                cnt+=(((q/p)*(p)));
            }
            else
            {
                cnt+=((q/p)*(p)+p);
            }
        }
        cout<<"Case "<<k<<": "<<cnt<<endl;
    }
    return 0;
}

Light Oj 1078 Integer Divisibility

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
string s;
ll divisor;
ll rem;
ll mod_chk(ll i)
{
    rem=(rem*10+s[i]-'0')%divisor;
    return rem;
}
int main()
{
    ll i,j,k,l,m,n,test;
    scanf("%lld",&test);
    for(k=1;k<=test;k++)
    {
        char c;
        scanf("%lld %c",&divisor,&c);
        s="";
        ll cnt=1;
        s+=c;
        ll in=0;
        rem=0;
        while(mod_chk(in)!=0)
        {
            s+=c;
            cnt++;
            in++;
        }
        printf("Case %lld: %lld\n",k,cnt);
    }
    return 0;
}

UVa 352 - The Seasonal War

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll cnt;
int dx[]={1,1,1,0,0,-1,-1,-1};
int dy[]={1,0,-1,1,-1,1,0,-1};
ll g[1000][1000];
bool visited[1009][1009];
ll n;
void dfs(ll i,ll j)
{
    visited[i][j]=1;
    for(ll m=0;m<8;m++)
    {
        ll p=i+dx[m];
        ll q=j+dy[m];
        if(p>=0&&p<n&&q>=0&&q<n&&visited[p][q]==0&&g[p][q]==1)
        {
            dfs(p,q);
        }
    }
    return;
}
int main()
{
    ll i,j,k=1,l,m;
    while(cin>>n)
    {
        memset(g,0,sizeof(g));
        memset(visited,0,sizeof(visited));
        for(i=0;i<n;i++)
        {
            string s;
            cin>>s;
            for(j=0;j<s.size();j++)
            {
                if(s[j]=='0')
                {
                    g[i][j]=0;
                }
                else
                {
                    g[i][j]=1;
                }
            }
        }
        cnt=0;
        for(i=0;i<n;i++)
        {
            for(j=0;j<n;j++)
            {
                if(visited[i][j]==0&&g[i][j]==1)
                {
                    cnt++;
                    dfs(i,j);
                }
            }
        }
        cout<<"Image number "<<k<<" contains "<<cnt<<" war eagles."<<endl;
        k++;
    }
    return 0;
}