MAXLN

THE MAX LINES

Link to the question : MAXLN 

HINT :

Very simple calculus problem. You can find the maximum value of s by taking s as a function of AB and AC, where AB can be x and AC dependent on x and r. Do the derivation and get the answer.

SOURCE CODE :

#include<iostream>
using namespace std;
int main()
{
    int t,i=1;
    long long  s,r;
    cin>>t;
    while(t--)
    {
           cin>>r;

           s = 4*r*r;
           cout<<"Case "<<i<<": "<<s<<".25"<<endl;
           i++;
    }
    return 0;

}

 

CRNVALEN

The Valentine Confession

Link to the question :  CRNVALEN

HINTS :

The question asks us to find out the number of girls who are double dating. First we take the input a[ ] of all the girls, say, n. Then we sort it. Now, if all the elements of a[ ] are equal and and equal to n-1, then all the girls are double dating. This can be very easily imagined.

If the last element of the array  is greater than or equal to n, then the output is -1 as this is not possible.

Now if both the cases are not true, then the answer will be the last element of the array or the maximum number. But we need to check again if the girls are fooling. So for that we can keep a counter such that if c is the number of girls double dating then, c girls will say c-1 as their response and n-c girls will give c girls as their answer. Hence, c is the output.

SOURCE CODE :

/* The Valentine Confession */

/* Sushant Gupta */







#include<stdio.h>

#include<algorithm>

using namespace std;

int main()

{

     int t;

     scanf("%d",&t);

     while(t--)

     {





    int n,f=0;

    scanf("%d",&n);

    long long int  i,ans,a[n],c1=0,c2=0;

    for(i=0;i<n;i++)

        scanf("%lld",&a[i]);

    sort(a,a+n);

    if(a[n-1] > n-1)

    {



          //printf("-1");

            f= 0;

    }

    else if(a[n-1] == a[0] && a[0]== n-1)

    {

        //printf("%d",n);

        ans = n;

        f = 1;

    }

    else {

            ans = a[n-1];

            c1 = ans;

            c2 = n - ans;

          for(i=n-1;i>=0;i--)

          {

                         if(a[i] == ans)

                            c2--;

                         else if(a[i] == ans-1)

                            c1--;

          }

          if(c1 ==c2  && c2 == 0 )

          {

              // printf("%d",ans);

              f = 1;

          }

          else

          {

              //printf("-1");

              f =0;

          }

    }

    if(f==0)

        printf("-1\n");

    else

        printf("%lld\n",ans);

     }

    return 0;

}

MANGOES

Real Mangoes for Ranjith

Link to the question : MANGOES 

HINT :

The question might look lengthy and you may think implementing the algorithm will  be a tough task, but a little careful observation may make this question look very simple. As per the question mangoes are real if GCD of each pair of the  set  {mi, mi+1, mi+2} equals 1. Now this is only possible when mi and (mi + 2) are odd else if they are even, they will have at least 2 as their GCD. Hence all you need to is find the sum of the odd terms.

SOURCE CODE :

 #include<stdio.h>
int main()
{
    int t;
    long long int n,x,s;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%lld",&n);
        x=n;
        if(n%2==0)
            n=(n-2)/2;
        else
            n=(n-1)/2;

        s=(n*n)%x;
        printf("%lld\n",s);

    }
    return 0;
}
  

MAIN74

Euclids algorithm revisited

Link to the question : MAIN74 

HINT :

The numbers form the fibonacci sequence if you try solving it for some test cases.

Example for n= 2 loops the answer will be 5 (3,2).

              for n= 3 loops, result is 8 (5,3).

              for n=4 loops, output will be 13 (8,5). 

And so on...

Hence it is obivious that for n >=2 output is (n + 3)th fibonacci term.

Now to solve the problem in O(logn) time you should use the optimized matrix multiplication method to generate the fibonacci term.

SOURCE CODE :

#include<stdio.h>

long long MAX=1000000007;

void multiply(long long F[2][2],long long M[2][2]);
void power(long long F[2][2],long long n);
long long fib(long long n);

long long fib(long long n)
{
    long long F[2][2]={{1,1},{1,0}};
    if(n==0)
        return 0;
    power(F,n-1);
    return F[0][0];
}

void multiply(long long F[2][2],long long M[2][2])
{

    long long x = ((F[0][0]*M[0][0])%MAX + (F[0][1]*M[1][0])%MAX)%MAX;
    long long y =  ((F[0][0]*M[0][1])%MAX + (F[0][1]*M[1][1])%MAX)%MAX;
    long long z =  ((F[1][0]*M[0][0])%MAX + (F[1][1]*M[1][0])%MAX)%MAX;
    long long w =  ((F[1][0]*M[0][1])%MAX + (F[1][1]*M[1][1])%MAX)%MAX;

    F[0][0] = x;
    F[0][1] = y;
    F[1][0] = z;
    F[1][1] = w;

}

void power(long long F[2][2], long long n)
{
    if( n == 0 || n == 1)
        return;
    long long M[2][2] = {{1,1},{1,0}};

    power(F, n/2);
    multiply(F, F);

    if( n&1)
    multiply(F, M);
}

int main()
{
    int t;
    long long int n;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%lld", &n);
        if(n==0)printf("0\n");
        else if(n==1)printf("2\n");
        else printf("%lld\n",(fib(n+3))%MAX);
    }

    return 0;
}

LENGFACT

Factorial length

Link to the question : LENGFACT 

HINT :

Apply the kamenetsky formula.

SOURCE CODE :

#include<stdio.h>

#include<math.h>

int main()

{

int t;

long long int  ans,n;

scanf("%d",&t);

while(t--)

{

ans=0;

scanf("%lld",&n);

if(n<3)

printf("1\n");

else{

ans=ceil(log10(2*3.141592653589793*n)/2 + n*log10(n/2.7182818284590452353));

printf("%lld\n",ans);

}

}

return 0;

}

LASTDIG

The last digit

Link to the question : LASTDIG 

HINT :

No need to worry about the constraints. Take out a pen and paper and notice the pattern of last digit for the powers of number 1 to 9. And then derive a general formula to shorten your code as the source limit is very small.

SOURCE CODE :

#include <stdio.h>

  int main(void) {

long long int a,p,q,b;

int t;

scanf("%d",&t);

while(t--)   {

scanf("%lld %lld",&a,&b);

p=a%10;

q=b%4;

if(b==0)

    printf("1\n");

else if(p==1||p==0||p==5||p==6)

printf("%d\n",p);

else if(q==1)

    printf("%d\n",p);

else if(q==2)

    printf("%d\n",((p*p)%10));

else if(q==3)

    printf("%d\n",((p*p*p)%10));

else if(q==0)

    printf("%d\n",((p*p*p*p)%10));

}

return 0;

}

KURUK14

GENIE SEQUENCE

Link to the question : KURUK14 

HINT :

It is said that a genie sequence is a sequence of numbers which can be arranged in such a way that they either tell the number of elements behind or number of elements in front of them. In order for a n elements sequence to follow the rule, if it contains c then it should also contain n-c or c, because if at the (c+1)th position we say there are c elements behind it, then at (n-c + 1)th we can say there are n-c elements behind it or c elements in front of it. So either 2 c's or 2 (n-c)'s  or 1 c and 1 (n-c) must be present. So in the case of 2 c's or 2 (n-c)'s we make them 1 c and 1 (n-c) then we will get all numbers from 0 to n-1 in the genie sequence. So we just need to check all 0 to n-1 numbers are present or not after converting repeating numbers to n-x form. 

SOURCE CODE :

/* Genie Sequence - (KURUK 14) */
/* Sushant Gupta */

#include<stdio.h>
int main()
{
    int t;
    scanf("%d",&t);
    while(t--)
    {
        int n,i,f=0,c;
        scanf("%d",&n);
        int a[n];
        for(i=0;i<n;i++)
            a[i]= 0;
        for(i=0;i<n;i++)
        {
             scanf("%d",&c);
             if(c<n)
             {
                 if(a[c]==0)
                    a[c]=1;
                 else
                    a[n-1-c]=1;
             }

        }
        for(i=0;i<n;i++)
        {
            if(a[i]==0)
                f=1;
        }
        if(f==0)
            printf("YES\n");
        else
            printf("NO\n");
    }
    return 0;
}
 

IITKWPCB

Check the coprimeness

Link to the question : IITKWPCB 

HINT :

Observe the test cases and derive the formula.

SOURCE CODE :

#include <stdio.h>
int main()
{
int t;
scanf("%d",&t);
while(t--)
{
    long long int n,c;
    scanf("%lld",&n);
    if(n%2==0)
    {
        c=n/2 - 1;
        if(c%2==0)
            printf("%lld\n",c-1);
        else
            printf("%lld\n",c);
    }
    else
    {
        printf("%lld\n",n/2);
    }
}
return 0;
}
 

HUBULLU

Link to the question : HUBULLU

HINT :

Observe carefully. Try some simple cases by taking n a  small number and then you will get the answer.

SOURCE CODE :

/* Hubulullu */
/* sushant gupta */

#include<iostream>

using namespace std;
int main()
{
     int t,s;
     long long int n;
     cin>>t;
     while(t--)
     {
         cin>>n>>s;
         if(s==0)
            cout<<"Airborne wins."<<endl;
         else
            cout<<"Pagfloyd wins."<<endl;
     }
     return 0;
}

HPYNOS

Happy Numbers I

Link to the question : HPYNOS 

HINT :

Just simple brute force. Keep on breaking the number untill you get a single digit. If its 1 then its a happy number else not a happy number.

SOURCE CODE :

#include<stdio.h>



int main()
{
    char a[10];int i=0,b=0,x,c=1;
    gets(a);

    while(a[i]!='\0')
    {
            b= b + (a[i] - 48) * (a[i]-48);

            i++;
    }



    while(b>9)
    {     x=0;
        while(b>0)
        {    x=(b%10) * (b%10) +x;
             b=b/10;

        }
        b=x;
        c++;

    }
    if(b==1)
        printf("%d",c);
    else
        printf("-1");

    return 0;


}