SPOJ - Philosophers Stone solution using DP

SPOJ - Philosophers Stone solution using DP

Solution:-

#include<bits/stdc++.h>
using namespace std;
#define MAX 200

int arr[MAX][MAX];

int max_val(int a,int b,int c)
{
    int p=INT_MIN;
    p=p>a?p:a;
    p=p>b?p:b;
    p=p>c?p:c;

    return p;
}

int main()
{
    int tc;
    int a,b;
    cin>>tc;
    while(tc--)
    {
        int h,w;
        cin>>h>>w;
        int max_stones=0;

        for(int i=0;i<h;i++)
            for(int j=0;j<w;j++)
            {
                cin>>arr[i][j];
                if(i>0)
                {
                    a=b=INT_MIN;
                    if(j>0)
                        a=arr[i-1][j-1];
                    if(j<w-1)
                        b=arr[i-1][j+1];
                    arr[i][j]+=max_val(arr[i-1][j],a,b);
                }
                max_stones=max_stones>arr[i][j]?max_stones:arr[i][j];
            }

        cout<<max_stones<<endl;
    }
    return 0;

}

SPOJ - AP-Complete The Series Easy Problem Solution

SPOJ - AP-Complete The Series Easy Problem Solution

Solution:-

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

int main()
{
    int tc;
    ll third,last_third,sum;
    int n,first,common_diff;
    cin>>tc;
    while(tc--)
    {
        cin>>third>>last_third>>sum;

        n=(2*sum)/(third+last_third);

        common_diff=(last_third-third)/(n-5);

        first=third-(2*common_diff);
        cout<<n<<"\n";
        for(ll i=0;i<n;i++)
            cout<<first+i*common_diff<<" ";
        cout<<"\n";
    }
    return 0;

}

SPOJ- Counting Triangles Solution

SPOJ - Counting Triangles Problem Solution

Solution:-

#include<bits/stdc++.h>
using namespace std;
#define MAX 1000010

long long up[MAX],down[MAX];

void init()
{
    up[1]=1;
    up[2]=4;
    down[2]=1;

    for(int i=3;i<=MAX;i++)
    {
        up[i]=2*up[i-1]+i-up[i-2];
        down[i]=up[i-1]-down[i-1];
    }
}

int main()
{
    init();
    int tc,num;;
    cin>>tc;
    while(tc--)
    {
        cin>>num;
        cout<<up[num]+down[num]<<endl;
    }
    return 0;
}