Saturday 10 October 2015

MORENA



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


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;



}

Wednesday 23 September 2015

BAT3


BATMAN3

Link to the question : BAT3 

HINT :

I would suggest you to try the longest increasing sub sequence problem first. You can also check the algorithm for LIS in geeksforgeeks.org. 
If you have idea of LIS, then the question must be easy for you. In this we need to find the longest decreasing subsequence but with a change that we can jump one big number if we are on the Robin's number (as given in the question). Hence, we just need to add  batman can go to next cliff its smaller than the present or batman is standing on the Robin's peak (then he can go to any peak). 

RECOMMENDED QUESTION :  

Try another dp question .

SOURCE CODE :

/* Batman3 */

/* Sushant Gupta */



#include<stdio.h>



int main()

{

    int t;

    scanf("%d",&t);

    while(t--)

    {

        int n,m;

        scanf("%d%d",&n,&m);

        int i,arr[n];

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

            scanf("%d",&arr[i]);

        int lis[n],j;

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

      lis[i] = 1;

         /* Compute optimized LIS values in bottom up manner */

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

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

         if ( (arr[i] < arr[j] || j==m )&& lis[i] < lis[j] + 1)

            lis[i] = lis[j] + 1;

    int max =0;

   /* Pick maximum of all LIS values */

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

      {if ( max < lis[i] )

         max = lis[i];

       // printf("li = %d\n",lis[i]); //check

         }



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

    }

    return 0;

}

Friday 11 September 2015

YELBRICK



The Yellow Brick Road

Link to the question : YELBRICK 

HINTS :

Very simple ad-hoc question. Just find the gcd of the length, breadth and height of the stones, and then find the number of stones that can be produced.

RECOMMENDED  QUESTION :

Try solving this question as even this requires some application of gcd.

SOURCE CODE :

#include <iostream>
using namespace std;
int gcd(int x,int y)
{
    while(x!=y){
          if(x>y)
              return gcd(x-y,y);
          else
             return gcd(x,y-x);
     }
     return x;
}
int main() 
{
    int n,i;
    while(1)
    {
        cin>>n;
        if(n==0)
        break;
        int a[n][3];
        long long vol=0;
        for(i=0;i<n;i++)
        {
            cin>>a[i][0]>>a[i][1]>>a[i][2];
        }
        int hcf =a[0][0];
        for(i=0;i<n;i++)
        {
            hcf = gcd(hcf,a[i][0]);
            hcf = gcd(hcf,a[i][1]);
            hcf = gcd(hcf,a[i][2]);
        }
        for(i=0;i<n;i++)
        {
            vol+=(long long)((a[i][0]/hcf)*(a[i][1]/hcf)*(a[i][2]/hcf));
        }
        cout<<vol<<"\n";
    }
    return 0;
}

Thursday 10 September 2015

ZSUM

Just Add It

Link to the question : ZSUM 

HINTS :

When trying to find  (Zn+Zn-1-2Zn-2) you will notice that most of the terms of Sn 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);
        }
    }

}

Tuesday 8 September 2015

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

Saturday 5 September 2015

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

Tuesday 1 September 2015

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



Wednesday 26 August 2015

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;

}

 

Tuesday 25 August 2015

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

Wednesday 12 August 2015

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

Friday 7 August 2015

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

Thursday 6 August 2015

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;


}
 

Thursday 30 July 2015

HOTELS


Hotels Along the Croatian Coast

Link to the question :  HOTELS

HINT :

We apply the sliding concept. We start calculating the sum from index 0 of the array. If the sum exceeds the maximum amount given, we start subtracting  from sum from the beginning of the array, untill the sum becomes less than or equal to maximum amount.

SOURCE  CODE :


#include<stdio.h>
int main()
{
    int i, l;
    long long n, m, sum, max_sum;

    scanf("%lld%lld",&n, &m);

         int a[n];
        for(i=1; i<=n; i++)
        {
             scanf("%d", &a[i]);
        }
        l=1;
        max_sum = 0;
        sum = 0;
        for(i=1; i<=n; i++)
        {
            sum = sum + a[i];
            while(sum>m)
            {
                sum = sum - a[l];
                l++;
                if(max_sum<=sum && sum<=m)
                {
                    max_sum = sum;

                    break;
                }

            }
            if(max_sum<=sum && sum<=m)
            {
                max_sum = sum;

            }
        }
        printf("%lld\n", max_sum);

    return 0;
}

HLP_RAMS


Topper Rama Rao

Link to the question : HLP_RAMS 

HINT :

To find whether nCr is odd or even we use the lucas theorem. 
Lucas theorem states that nCr % m, where, m is a prime number = (n0 C r0 % m) * (n1 C r1 % m)*........
(nk C rk % m), where n<0n1...nk and r0r1...rk are the representation of n and r in base m respectively. Hence, in base 2 representation, the digits will be either 0 or 1. 
So,according to lucas theorem,  nCr % 2 will give us the cases 1C1, 1C0, 0C0, 0C1. Now, 0C1  = 0. Hence, if nCr has the case 0C1 then its always even else odd. 
Now for counting the number of odd terms we count the number of 1's in n' s binary representation. We can assign either 0 or 1 to the 1's of n in nCr. Hence, number off odd terms = 2^(no of 1's).

SOURCE CODE :

/* Topper Rama Rao */
/* Sushant Gupta */
#include<stdio.h>
#include<math.h>
int main()
{
    int t;
    scanf("%d",&t);
    while(t--)
    {
        long long int n,i,odd,x,c=0;;
        scanf("%lld",&n);
        x=n;
        if(n==0)
            printf("0 1\n");
        else
        {
            while(n>0) {
                if(n&1==1)
                    c++;
               n=  n>>1;
            }
            odd = pow(2,c);
            printf("%lld %lld\n",x+1-odd,odd);


        }


    }
    return 0;
}

Wednesday 29 July 2015

HEADSHOT

Headshot

Link to the question : HEADSHOT 

HINT :

The question requires a bit of your probability skills. Use the greedy approach. And if still not able to derive the formula, try to grasp it up with the source code.

SOURCE CODE :

/* Headshot */
/* Sushant Gupta */
#include<stdio.h>
#include<string.h>
int main()
{
    char a[150];
    int i,n,w=0,b=0;
    float rot,sht;
    scanf("%s",a);
    n = strlen(a);
    for(i=0;i<n;i++)
    {
        if(a[i]=='0')
            w++;


    }
    rot = (float)w/n;
    for(i=0;i<n-1;i++)
    {
        if(a[i]=='0' && a[i+1]=='0')
            b++;
    }
    if(a[0]=='0' && a[n-1]=='0')
        b++;
    sht = (float)b/w;

    if(rot == sht)
        printf("EQUAL\n");
    else if(rot>sht)
        printf("ROTATE\n");
    else
        printf("SHOOT\n");
    return 0;
}

HC


Happy Coins

Link to the question : HC

HINT :

You can ignore the word consecutive. Though I wont say it misleading, but not taking that into consideration will make the problem solving a bit more simple. Try some cases and even if you cant check the source code.

SOURCE CODE :


#include<stdio.h>

#include<string.h>

int main()

{

long int t,i,n,count=0;

char s[4],a[]="lxh";

scanf("%ld",&t);

while(t--)

{

    count=0;

    scanf("%ld",&n);

    while(n--)

    {

        scanf("%s",s);

        if(strcmp(s,a)==0)

            count++;

    }

    if(count%2==0)

        printf("hhb\n");

    else

        printf("lxh\n");



}

return 0;



}

RECOMMENDED QUESTION :

After solving this question, I would like you to try your hands out in this question . 

Monday 27 July 2015

HANGOVER

Hangover

 Link to the question : HANGOVER

HINT :

Just simply find the sum of the series given in the question : 1/2 + 1/3 +...1/k. till the sum is less than equal to the input, n. Keep a count  of the k.

RECOMMENDED QUESTION :

Try solving this question after completing this.

SOURCE CODE :

#include<stdio.h>
int main()
{
    float s,n,x=1,i;
    while(x!=0)
    {
        scanf("%f",&n);
        x=n;
        if(x!=0)
        {
            s=0;i=2;
            while(s<=n)
            {
                s=s+1/i;

                i++;
            }
            printf("%1.0f card(s)\n",i-2);
        }
    }
    return 0;
}

GUESSTHE

Guess the Number

Link to the question : GUESSTHE 

HINT :

We need to find the LCM of the numbers which are given a Y, and then check for the numbers which are given N, whether they divide the LCM.

RECOMMENNDED QUESTION:

You would surely love solving this question  after  trying your hands in this one.

SOURCE CODE :

#include<stdio.h>
long long int gcd(long long int a,long long int b)
{
    if(b>a)
        return gcd(b,a);
    else if(b==0)
        return a;
    else
        return gcd(b,a%b);
}
long long int lcm(long long int a,long long int b)
{
    return a*b/gcd(a,b);
}
int main()
{
    char c,a[22];

    while(1) {
            int i=1,j=0;
            long long int k=1;
            scanf("%c",&c);
            while(c!='\n'&&c!='*')
           {



                      if(c=='Y')
                          k= lcm(k,i);
                     else if(c=='N')
                           a[j++]= i;
                     i++;
                     scanf("%c",&c);


           }
           if(c=='*')
            return 0;
            else {
           for(i=0;i<j;i++)
           {
               if(k%a[i]==0)
               {
                   k=-1;
                   break;
               }
           }
           printf("%lld\n",k);
            }
    }

}
 

Sunday 26 July 2015

GSHOP


Rama and Friends

Link to the question : GSHOP 

HINT :

We must keep in find the following cases and then solve.
  • If number of times we can execute the operation, k, is lesser than the number of negative numbers then we simply multiply the larger negative numbers with -1 and add.
  • Else, we multiply all negative numbers with -1 and :
                     1. If number of times we execute the operation is even, simply add all the numbers.
                     2. Else multiply the smallest number with -1 and the add.

RECOMMENDED QUESTION :

I would like the reader to solve this question after getting an AC in this one !!

SOURCE CODE :

#include <stdio.h>


int main()
{
 int t;
 scanf("%d",&t);
 while(t--)
 {
  int n,k;
  scanf("%d%d",&n,&k);
  int count_n=0,count_z=0,count_p=0,i;
  long long sum=0,min=9999999,temp;
  int a[n+9];
  for(i=0;i<n;i++){
   scanf("%d",&a[i]);
   temp=a[i]>0?a[i]:-1*a[i];
   if(temp<min)
    min=temp;
   if(a[i]<0)
    count_n++;
  }
  if(k<=count_n)
  {
   int j=0;
   for(i=0;i<n;i++)
    if(a[i]<0 && j<k)
    {
     a[i]=-a[i];
     j++;
    }
   for(i=0;i<n;i++)
    sum+=a[i];
   printf("%lld\n",sum);
  }
  else
  {
   for(i=0;i<count_n;i++)
    a[i]=-a[i];
   for(i=0;i<n;i++){
    sum+=a[i];
   }
   if((k-count_n)%2!=0)
    sum+=-(2*min);
   printf("%lld\n",sum);
  }
 }
 return 0;
}

GIRLSNBS

Girls and Boys

Link to the question : GIRLSNBS 

HINT :

Let g be the number of girls and b be the number of boys and let b>g. Now, if * represents the girls and let their arrangement be like :
      *     *      *      *        *   , then think how many boys will you fill on those spaces so that you get the minimum gender regularity.There are g+1 spaces. So first we fit all the spaces with equal number of boys and then distribute the remaining boys to one boy per space.

RECOMMENDED QUESTION :

I would like my readers to solve this question after trying this one.

SOURCE  CODE :

#include<stdio.h>

int main()

{

    int g,b,x=1,y=1;

    while(x!= -1 && y!=-1)

    {

                scanf("%d%d",&g,&b);

                x=g; y=b;

                if(x!=-1 && y!=-1)

                {

                    if(g==b){

                            if(g==0)

                               printf("0\n");

                       else

                        printf("1\n");

                    }

                    else

                    {

                        if(g>b)

                        {

                            x=g; y=b;

                        }

                        else{ x=b; y=g;}

                        if((x%(y+1))==0)

                            printf("%d\n",(x/(y+1)));



                        else

                            printf("%d\n",(x/(y+1))+1);

                    }

                }

    }

    return 0;

}
    

Saturday 25 July 2015

FUNPROB

Yanu in Movie theatre

Link to the question : FUNPROB 

RECOMMENDED QUESTION :

Try solving this question after solving this.

SOURCE CODE :

#include<stdio.h>
int main()
{
     int m=1,n=1;
     double x,y;
     while(m!=0 && n!=0)
     {
         scanf("%d%d",&n,&m);
         if(n!=0 && m!=0)
         {
             if(n>m || m==0)
                printf("0.000000\n");
             else if(n==0)
                printf("1.000000\n");
             else
             {
                 x=m;
                 y=n;
                 printf("%.6lf\n",(x-y+1.0)/(x+1.0));
             }

         }
     }
     return 0;
}

FENCE1

Build a Fence

Link to the question : FENCE1 

HINT : 

Imagine a very long straight ruler and a piece of smallish rope. The rope is tied to the ruler at one end and loose at the other. Now connect the other end of the rope to the ruler and you'd get a shape with a straight bottom (made of the ruler itself) and a curvy top (made by the rope). This shape has an area, what is its maximum area given the length of the rope?

RECOMMENDED QUESTION:

Try your hands in this question after getting an AC in this.

SOURCE CODE :

#include<stdio.h>

int main()
{
    int l,x=1;
    double s;
    while(x!=0)
    {
        scanf("%d",&l);
        x=l;
        if(x!=0)
        {
            s= (float)(l*l/(2*3.1415926 ));
            printf("%.2f\n",s);
        }
    }



    return 0;
}

FCTRL2

Small factorials

Link to the quesstion : FCTRL2 

HINT :

Since factorials of numbers like 100 will be very long, almost 160 digits. So we need to store the result in an array. Check the code on how to implement it or you can also read its tutorial in codechef.

RECOMMENDED QUESTION :

Try solving this question .

SOURCE CODE :


#include<stdio.h>

#include<stdlib.h>



void fact(int num,int a[],int n)

{

     int temp=0,x=0,i=0,j,k;

     for(j=num-1;j>0;j--)

     {    i=0;

         for(k=n;k>0;k--)

        {



              x= a[i]*j + temp;

              a[i]= x%10;

              temp= x/10;



               i++;





        }



        while(temp!=0)

        {

           a[i]=temp%10;

          temp=temp/10;



           i++;

           n=i;

        }



     }



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

        printf("%d",a[j]);

        printf("\n");



}



int main()

{

    int t;

    scanf("%d",&t);

    while(t--)

   {   int a[200]={0};

       int n;

       scanf("%d",&n);

       int n2=n; int i=0;

       while(n>0)

       {

           a[i]=n%10;

           n=n/10;



           i=i+1;

       }

       int k=i;



       fact(n2,a,k);

   }

   return 0;





}

FCTRL


Factorial

Link to the question : FCTRL 

HINT :

For finding the number of trailing zeroes, we need to find how many factors of 10 are present. Since 10 = 2 *5 , we basically need to find the number of factors of 5, since its obvious that factors of 2 will be greater in number.

RECOMMENDED QUESTION :

Try this question afer completing this.

SOURCE CODE :


#include<stdio.h>

    #include<math.h>



    int main()

    {

      int t,c,i;

      long n;

      scanf("%d",&t);

      while(t--)

      {

          c=0;i=1;

          scanf("%ld",&n);

          while(n/pow(5,i)>=1)

          {

              c=c+(int)(n/pow(5,i));

              i=i+1;

          }

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

      }

       return 0;

    }

Friday 24 July 2015

FAVDICE


Favorite Dice

Link to the question : FAVDICE 

HINT :

Read some articels on : Expected value. Understand it properly and then implement the formula.

SOURCE CODE :

#include<stdio.h>

int main()
{
    int t,n,i;
    float s;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d",&n);
        s=0;
        for(i=1;i<=n;i++)
            s= s+ (float)1/(i);
        s=(float)(s*n);
        printf("%.2f\n",s);
    }



    return 0;
}



RECOMMENDED QUESTION :

I would like my reader to solve this question after this one.

FASHION

Fashion Shows

Link to the question : FASHION 

HINT :

Simply just sort the array containing hotness level of men and women, then multiply the elements in the same index and keep on adding.

RECOMMENDED QUESTION :

Try solving this question   after getting an AC in this one.

SOURCE CODE :

  #include<iostream>
#include<new>
#include<vector>
#include<algorithm>
using namespace std;
int main()
{
     int *a,*b,n,s,i=0,t,j;
     cin>>t;
     while(t--)
     {
           cin>>s;
           i=0;
           a= new (nothrow)int[s];
           b= new (nothrow)int[s];
          for(j=0;j<s;j++)
                 cin>>a[j];
           sort(a,a+s);
             for(j=0;j<s;j++)
                  cin>>b[j];
              sort(b,b+s);
              for(j=0;j<s;j++)
              {
                  i= i+ a[j]*b[j];
              }
              cout<<i<<endl;
     }
 return 0;
}