Friday, 4 March 2016

PROFF

Standard

Professor Farouk Question


Link to the question : PROFF

HINT :

Just simple brute force.  Add one digit at a time from right to left and check if there is a carry. Keep in mind some corner cases. 

RECOMMENDED QUESTION :

Try your hands on this question : Headshot

SOLUTION :

/*  PROFF */
/* Sushant Gupta */
#include<stdio.h>
#include<string.h>
int main()
{
  
    long long int x1=1,x2=1,n1,n2;
    while(1)
    {
        scanf("%lld%lld",&x1,&x2);
        if(x1==0 && x2==0)
            return 0;
        else
        {
            n1 = x1;
            n2 = x2;
            int s=0,c=0;
            while(n1 || n2)
            {
                s = ((n1 %10) + (n2 %10) + s >=10);
                c = c+s;
                n1 = n1/10;
                n2 = n2/10;
                /*if(s>9)
                {
                    c++;
                    f=1;
                }
                else if(s==9)
                {
                    if(f==1)
                        c++;
                    else
                        f= 0;
                }
                else
                    f= 0; */
            }
            if(c==0)
                printf("No carry operation.\n");
            else if(c==1)
                printf("1 carry operation.\n");
            else
                printf("%d carry operations.\n",c);
        }
    }
}

Wednesday, 2 March 2016

ABA12C

Standard

Buying Apples!

Link to the question : ABA12C

HINT :

This is a problem of unbounded knapsack. 
We will maintain an array ans[ k+1 ] where the j th index stores the minimum money required to buy  j kg of apples. 
To find the optimal ans[ j ] , we need to decide whether to  select or reject an instance of weight 'i'.
If we reject all the weights then ans[ j ] = price[ j ], and if we select 'i'  then 
ans[ j ] = minimum[ ans[j - i] + price[ i ] ]  for i= 0,1....j-1.

You can look into the source code for a better understanding.

RECOMMENDED QUESTION :

Try your hands on this dp question :  Morena
  

SOLUTION :

   /* ABA12C - Buying Apples */
/* Sushant Gupta */

#include<bits/stdc++.h>
using namespace std;
int main()
{
 int t;
 scanf("%d",&t);
 while(t--)
 {
  int n,k,b;
  scanf("%d%d",&n,&k);
  b =k;
  int p[k +1];
  int i,j;
  for( i=1; i<=k; i++ )
   scanf("%d",&p[i]);
  int ans[k+1];
  for(i=1; i<=k; i++)
  {
   //if(p[i] == -1)
   // ans[i] = INT_MAX;
   //else
    ans[i] = p[i];
  }
  for(i=2; i<=k; i++)
  {
   for(j=1; j<i; j++)
   {
    if(p[i-j] == -1  || ans[j] == -1)
     continue;
    if(ans[i] == -1)
     ans[i] = ans[j] + p[i-j];
    else
    ans[i] = min(ans[i], ans[j] + p[i-j]);

   }

  }
  if(k==0)
   printf("0\n");
  else
  printf("%d\n",ans[k]);

 }
 return 0;
}

Tuesday, 1 March 2016

KQUERY

Standard

K-query

Link to the question : KQUERY

HINT :

PREREQUISITE : BINARY INDEXED TREE

This is an offline approach. 
Store the array elements and the queries in the same array(for this you may define your own class or structure) . You can see my structure in the code below. 
Now, we sort this array in decreasing order (according to the value of the array elements and the k values of the queries) .
Now, just traverse this sorted array :
   a. If the element is array element , update the binary indexed tree to have this element  
       at the given index .
   b. If the element is a query <left,right,k> , make a query to find the number of elements in the segment tree between [left, right]. Store this information in our answer array at the location corresponding to the query number we are dealing with .
Finally, output this array .

RECOMMENDED QUESTION :

Try this question : hlprams

SOLUTION :

#include<bits/stdc++.h>
using namespace std;
int btree[30009];
struct pos
{
    int l,r,p;
    long long int v;
};
pos a[230009];
bool cmp(pos a, pos b)
{
    if(a.v == b.v)
    {
        return a.l > b.l;
    }
    return a.v > b.v;
}
void update_it(int idx, int n)
{
    while(idx <=n)
    {
        btree[idx] += 1;
        idx += idx & (-idx);
    }
}
int read_it(int idx)
{
    int s=0;
    while(idx >0)
    {
        s += btree[idx];
        idx -= idx &(-idx);
    }
    return s;
}
int main()
{
    fill(btree,btree + 30009, 0);
    int n;
    scanf("%d",&n);
    int i;
    for(i=0;i<n;i++)
    {
        scanf("%lld",&a[i].v);
        a[i].l = 0;
        a[i].p =0;
        a[i].r = i+1;
    }
    int q;
    scanf("%d",&q);
    int ans[q+1];
    for(i=n ;i< n+q; i++)
    {
        scanf("%d%d%d",&a[i].l,&a[i].r,&a[i].v);
        a[i].p = i-n+1;
    }
    sort(a,a+n+q,cmp);
    //printf("Hello\n");   //check
   /* for(i=0; i<n+q;i++)
    {
        printf("%d %d %d\n",a[i].l,a[i].r,a[i].v);
    }*/
    for(i=0;i< n+q;i++)
    {
        if(a[i].l == 0)
        {
            update_it(a[i].r,n + 9);
        }
        else
        {
           // printf("\n");
       //     for(int j=1;j<=n;j++)
         //      printf("b[%d] = %d\n",j,btree[j]);  // check
           ans[a[i].p] = read_it(a[i].r) - read_it(a[i].l -1);
        }
    }
    //for(i=1;i<=n;i++)
      //  printf("b = %d\n",btree[i]);  //check
    for(i=1;i<=q;i++)
        printf("%d\n",ans[i]);
    return 0;
}