Wednesday, 23 September 2015

BAT3

Standard

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

Standard


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

Standard

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

Standard


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

Standard

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

Standard


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