PROFF

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





        }

    }





}

ABA12C

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

KQUERY

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;

}