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 - Street Parade Problem Solution (Using Stack)

SPOJ - Street Parade Problem Solution (Using Stack)

Solution:-

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

int arr[1010];
bool flag;

int main()
{
    int n,prev,index;
    while(1)
    {
        stack<int> s;
        cin>>n;
        if(n==0)
            break;

        for(int i=0;i<n;i++)
            cin>>arr[i];

        prev=index=0;
        flag=false;
        while(index<n)
        {
            if(arr[index]==prev+1)
            {
                prev=arr[index];
                index++;
            }
            else if(s.size() && s.top()==prev+1)
            {
                prev=s.top();
                s.pop();
            }
            else
            {
                s.push(arr[index]);
                index++;
            }
        }
        while(s.size() && s.top()==prev+1)
        {
            prev=s.top();
            s.pop();
        }
        if(!s.size())
            flag=true;

        if(flag)
            cout<<"yes\n";
        else
            cout<<"no\n";

    }
    return 0;

}

SPOJ- Army Strength Problem Solution

SPOJ- Army Strength Problem Solution #ad-hoc problem

Solution:-

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

int main()
{
    int tc;
    string ex;
    cin>>tc;
    getline(cin,ex);
    while(tc--)
    {
        int NG,NM,num;
        int max_NG=-1,max_NM=-1;

        cin>>NG>>NM;

        for(int i=0;i<NG;i++)
        {
            cin>>num;
            max_NG=max_NG>num?max_NG:num;
        }

        for(int i=0;i<NM;i++)
        {
            cin>>num;
            max_NM=max_NM>num?max_NM:num;
        }

        if(max_NM<=max_NG)
            cout<<"Godzilla\n";
        else
            cout<<"MechaGodzilla\n";
        getline(cin,ex);
    }
    return 0;

}

SPOJ- Ambiguous Permutations Problem Solution

SPOJ- Ambiguous Permutations Problem Solution

Solution:-

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

int arr[MAX];

bool cal_per(int n)
{
    for(int i=1;i<=n;i++)
    {
        if(i!=arr[arr[i]])
            return false;
    }
    return true;
}

int main()
{
    int n;
    while(1)
    {
        cin>>n;
        if(n==0)
            break;

        for(int i=1;i<=n;i++)
            cin>>arr[i];

        if(cal_per(n))
            cout<<"ambiguous\n";
        else
            cout<<"not ambiguous\n";
    }
    return 0;

}

SPOJ - Bytelandian Gold Coins Problem Solution

SPOJ - BYTELANDIAN GOLD COINS (Famous DP Problem) solution

Solution:-

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define MAX 100010
ll arr[MAX+5],i,N;

ll cal_max(int N)
{
    if(N<MAX)
        return arr[N];

    else if(N/2+N/3+N/4<=N)
        return N;
    else
        return cal_max(N/2)+cal_max(N/3)+cal_max(N/4);
}

int main()
{
    arr[0]=0;
    arr[1]=1;
    arr[2]=2;
    arr[3]=3;
    for(i=4;i<=MAX;i++)
        arr[i]=max(i,arr[i/2]+arr[i/3]+arr[i/4]);

    while(scanf("%lld",&N)==1)
    cout<<cal_max(N)<<endl;
    return 0;

}

SPOJ- Will It Ever Stop (WILLITST) Problem Solution

SPOJ- Will It Ever Stop (WILLITST) Problem O(1) Solution

Solution:-

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

int main()
{
    long long int num;
    cin>>num;

    if(num<=1 || !(num&num-1))
        cout<<"TAK";
    else
        cout<<"NIE";

    return 0;

}

SPOJ - Count on Cantor Problem Solution

SPOJ - Count on Cantor (CANTON) Problem Solution

Solution:-

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

ll arr[MAX];

void init()
{
    int i=1;
    while(1)
    {
        arr[i]=i+arr[i-1];
        if(arr[i]>=lim)
            break;
        i++;
    }
}

int main()
{
    init();
    ll tc,num;
    cin>>tc;
    while(tc--)
    {
        cin>>num;
        int i=0;
        while(arr[i]<num)
            i++;

        ll diff=num-arr[i-1];

        cout<<"TERM "<<num<<" IS ";

        if(i%2==0)
            cout<<diff<<"/"<<i+1-diff;
        else
            cout<<i+1-diff<<"/"<<diff;

        cout<<endl;
    }
    return 0;

}

SPOJ - STAMPS Problem Solution

SPOJ - STAMPS Problem Solution

Solution:-

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

int arr[MAX];
int num_stamps,num_friends;

bool wayToSort(int i, int j) { return i > j; }

int main()
{
    int tc,i,j=0;
    cin>>tc;
    while(tc--)
    {
        j++;
        int index;
        cin>>num_stamps>>num_friends;

        for(i=0;i<num_friends;i++)
            cin>>arr[i];

        sort(arr,arr+num_friends,wayToSort);

        long long int sum=0;
        bool flag=false;

        for(i=0;i<num_friends;i++)
        {
            if(sum>=num_stamps)
            {
                flag=true;
                index=i;
                break;
            }
            sum+=arr[i];
        }

        if(sum>=num_stamps)
        {
            flag=true;
            index=i;
        }

        cout<<"Scenario #"<<j<<":\n";

        if(flag)
            cout<<index<<endl<<endl;
        else
            cout<<"impossible"<<endl<<endl;
    }
    return 0;

}