Saturday, 10 October 2015

MORENA

Standard


Morenas Candy Shop ( Easy )

Link to the question : MORENA

HINT :

Think of dp solution. We check if a[i] is > or < or = a[i-1] and store its relative sign in another array, b[i]. Now just count the number of times the sign alternates.

RECOMMENDED QUESTION :

Try solving this dp question .

SOURCE CODE :

#include<stdio.h>
long long int a[1000010];
int b[1000010];
int main()
{
    int n,i;
    scanf("%d",&n);
    b[0] = 0;
    for(i=0;i<n;i++)
    {
        scanf("%lld",&a[i]);
        if(i>0)
        {
            if(a[i]>a[i-1])
                b[i] = 1;
            else if(a[i] < a[i-1])
                b[i] = -1;
            else
                b[i] = 0;
        }
    }
    int c=1,sign=0;
    for(i=1;i<n;i++)
    {
        if((sign == 0) && (b[i] != 0))
        {
               c++;
               sign = b[i];
        }
        else if((sign ==1) && (b[i]== -1))
        {
            c++;
            sign = b[i];
        }
        else if((sign == -1) && (b[i] == 1))
        {
            c++;
            sign = b[i];
        }
    }
    printf("%d\n",c);
    return 0;
}

Monday, 5 October 2015

TWOSQRS

Standard

Two squares or not two squares

Link to the question : TWOSQRS

HINT :

Logic seems very clear. Just we need check if the number can be represented as a sum of two squares or not. A little bit optimisation may be preferrable.

RECOMMENDED QUESTION :

Try solving this  question .

SOURCE CODE :

#include<stdio.h>

#include<math.h>

void twosq(long long int x)

{

    long long int i,j=0;

    i= sqrt(x);

    while(i>0) {

    if(j*j>x)

      {



        printf("No\n");

         break;

      }

    else if(i*i + j*j == x)

        {



         printf("Yes\n");

         break;

        }

    else if(i*i + j*j <x)

         j++;

    else

        i--;

    }





}

int main()

{

    int t;

    scanf("%d",&t);

    while(t--)

    {

        long long int n;

        scanf("%lld",&n);

        twosq(n);

    }

    return 0;



}