ZSUM

Just Add It

Link to the question : ZSUM 

HINTS :

When trying to find  (Z_n+Z_n-1-2Z_n-2) you will notice that most of the terms of S_n and P cancel out and the terms left can be easily calculated by modular exponention.   

  You can find the code for modular exponention in my previous post YAPP .

SOURCE CODE :

/* Just Add */
/* Sushant Gupta */

#include<stdio.h>
#define mod 10000007

long long int mult(long long int x,long long int y)
{
    long long int ans =1;
    while(y>0)
    {
        if(y%2)
            ans = (ans * x) % mod;
        x = (x * x) % mod;
        y=y>>1;

    }
    return ans;
}

int main()
{
    long long int n,k;
    while(1)
    {
        scanf("%lld%lld",&n,&k);
        if(n==0 && k==0 )
            return 0;
        else
        {
            long long int s1, s2,s3,s4;
            s1 = (2 * mult(n-1,n-1) ) % mod;
            s2 = (2 * mult(n-1,k) ) % mod;
            s3 = mult(n,k);
            s4 = mult(n,n);
            long long int res = (s1 + s2 +s3 + s4) % mod;
            printf("%lld\n",res);
        }
    }

}

MOHIB

Mohib and series

 Link to the question : MOHIB

HINT :

Given x and the avg as input, the number of elements in the sequence, n, and the sum of the sequence can be very easily calculated by using the formula - sum of seq. / n = avg. 

Now, to find the largest possible number, lets say M, (sum of sequence - M) should be minimum. Hence in order for that to be minimum, the sequence excluding M should be 1,2,3,...n-1 such that its sum is minimum.

RECOMMENDED QUESTION :

After getting AC in this one, try getting AC in this question .

SOURCE CODE :

#include<stdio.h>


int main()

{

    int t;

    scanf("%d",&t);  

    while(t--)

    {

         int x,avg,n;

         scanf("%d%d",&x,&avg);

         n = avg - x;

         int sum = n * (avg + 1);

         sum = sum - (n*(n-1)/2) ;

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

    }

    return 0;

}              

MKEQUAL

Make them equal !

Link to the question : MKEQUAL 

HINTS :

Very simple problem. Pen paper work. Try out with any n numbers such tha sum of n numbers is not divisible ny n and again with n numbers such that this time its divisible. You will definitely get the logic.

SOURCE CODE :

#include<iostream>

using namespace std;

int main()

{

    int t;

    cin>>t;

    while(t--)

    {

        int n;

        cin>>n;

        int a[n],i;

        long long int s=0;

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

        {

            cin>>a[i];

            s=s+a[i];

        }

        if(s%n==0)

            cout<<n<<endl;

        else

            cout<<n-1<<endl;



    }



    return 0;

}

YAPP

Yet Another Permutations Problem

Link to the question : YAPP 

HINT : 

All you need to find is 2 ^ (n-1). Use modular exponention to calculate this. You can read articles  on modular exponention from wikipedia or if possible can understand from my blog.

 SOURCE  CODE :

/* Yet Another Permutation Problem */
/* Sushant Gupta */

#include<stdio.h>


int main()
{
    int t;
    scanf("%d",&t);
    while(t--)
    {
        long long int n,ans=1,mod =  1000000007,a=2;
        scanf("%lld",&n);
        n=n-1;
        if(n==0)
            printf("1\n");
        else
        {
            while(n>0)
            {
                if(n&1)
                    ans = ans * a % mod;
                a = a*a % mod;
                n= n>>1;

            }
            printf("%lld\n",ans);
        }
    }
    return 0;
}

 

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;

}