Wednesday, 26 August 2015

MAXLN

Standard

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;

}

 

Tuesday, 25 August 2015

CRNVALEN

Standard

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;
}

Wednesday, 12 August 2015

MANGOES

Standard

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

Standard

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 11 (8,3). 
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;
}

Friday, 7 August 2015

LENGFACT

Standard

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

Standard

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

Standard

GENIE SEQUENCE

Link to the question : KURUK14 

HINT :

In order for a sequence to be a genie sequence, the numbers given as input shall either describe the number of elements before it or number of elements after it. So for checking this we create an array a[] of size n and initialize all its elements with 0. Now, we take the input for genie sequence, let's say c. For every input c, we change a[c] = 1 and if its already 1 we change a[n-1-c] =1. This way we will come to know the index  whose  number of elements before or after it has been given or not. For that index a[i] = 0.

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;
}
 

Thursday, 6 August 2015

IITKWPCB

Standard

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

Standard
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

Standard

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;


}