KQUERYO

K-Query Online

Link to the question : KQUERYO

HINT :

Question can be easily solved with Segment Trees with vector.  Read more about it here :  http://codeforces.com/blog/entry/15890

RECOMMENDED QUESTION :

Try your hands on this question : QUEEN

SOLUTION :

#include <bits/stdc++.h>
#define ll long long
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define mod 1000000007
using namespace std;

int n,q, ar[30005];
std::vector<int> v[100005];

void build(int id ,int l ,int r )
{
if(r == l )
{
v[id].push_back(ar[l]);
return ;
}
int mid = (l+r)/2;
build(2 * id, l, mid);
build(2*id+1, mid+1, r);
merge(v[2 * id].begin(), v[2 * id].end(), v[2 * id + 1].begin(), v[2 * id + 1].end(), back_inserter(v[id]));
}

int query(int x,int y,int k,int id ,int l ,int r )
{

if(x > r || l > y)
return 0;
if(x <= l && r <= y)
{
return v[id].size() - (upper_bound(v[id].begin(), v[id].end(), k) - v[id].begin());
}
int mid = (l+r)/2;

return query(x, y, k, 2 * id, l, mid) +
  query(x, y, k, 2*id+1, mid+1, r) ;
}


int main()
{
scanf("%d", &n);
for(int i=0; i<n; i++)
scanf("%d", &ar[i]);

build(1,0,n-1);
scanf("%d", &q);

int prev = 0;
while(q--)
{
int a,b,c;
scanf("%d%d%d", &a, &b, &c);
int i = a^prev;
int j = b^prev;
int k = c^prev;

prev = query(i-1,j-1,k,1,0,n-1);
printf("%d\n", prev);
}
return 0;
}

QUEEN

Wandering Queen

Link to the question : QUEEN

HINT :

This question requires bfs as can be clearly understood from the tag. We start doing bfs from the position of the queen. And push into the queue all the squares which can be visited by the queen from that position and update their distance by 1 and mark it visited. For eg :
S..
 ..F
when starting from S we push into the queue positions (0,1), (0,2), (1,0), (1,1), consider 0 based indexing, update their position and mark them visited.
But while pushing into the queue just checking whether that position has been visited wont do.
Because consider the case
S..
XX.
..F
here, from (0,1) you can visit (1,2) and update its distance and mark it visited, and when you check for (0,2) you will see (1,2) is visited and not check further. This is incorrect because for optimal solution you must visit (1,2) and (2,2) from here. Hence even if the square is visited you should visit it again if it can be reached from the current position in 1 move.
Look code for further details.

RECOMMENDED QUESTION :

Try your hands on this question : Headshot

SOLUTION :

#include <iostream> #include <stdio.h> #include <queue> using namespace std; struct point { int x,y; }; int X[] = {-1, -1, -1, 0, 0, 1, 1, 1}; int Y[] = {-1, 0, 1, -1, 1, -1, 0, 1}; int n,m; char str[1005][1005]; int dist[1000][1000]; bool check(point t) { if(t.x >=0 && t.x <n && t.y >=0 && t.y <m && str[t.x][t.y] != 'X') return true; return false; } int main() { int t; scanf("%d", &t); while(t--) { scanf("%d %d", &n, &m); for(int i=0; i<n; i++) scanf("%s", str[i]); queue<point> q; point start, final; for(int i=0; i<n; i++) { for(int j=0; j<m; j++) { dist[i][j] = 0; if(str[i][j] == 'S') { start.x = i; start.y = j; dist[i][j] = 1; } else if(str[i][j] == 'F') { final.x = i; final.y = j; } } } q.push(start); while(!q.empty()) { point temp = q.front(); q.pop(); for(int i=0; i<8; i++) { point copy = temp; copy.x += X[i]; copy.y += Y[i]; while(check(copy)) { if(dist[copy.x][copy.y] == 0) { dist[copy.x][copy.y] = dist[temp.x][temp.y] + 1; q.push(copy); } else if(dist[copy.x][copy.y] != dist[temp.x][temp.y]+1) break; copy.x += X[i]; copy.y += Y[i]; } } } cout << dist[final.x][final.y]-1 << endl; } return 0; }

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;

}

PPATH

Prime Path

Link to the question : PPATH

RECOMMENDED QUESTION:

Try your hands on this permutation question : QUESTION

HINT :

A good problem on bfs for beginners. The question asks us to find the shortest route between the two prime numbers. What we can do is change each digit of the number and check whether the new number is prime. If its prime then we again apply the above process and continue this process untill we reach the destination. 

The forming of new number and traversing to new one can be easily done  using Breadth First Search. If you don't know about it, I would recommend you to have a look at it here .

SOLUTION :

#include<bits/stdc++.h>



using namespace std;




bool prime[100005];

 bool visit[100005];

int dist[100005];




void sieve(int n = 100005)

{

    // Create a boolean array "prime[0..n]" and initialize

    // all entries it as true. A value in prime[i] will

    // finally be false if i is Not a prime, else true.

    

    memset(prime, true, sizeof(prime));

    prime[0] = false;

    prime[1] = false;

    for (int p=2; p*p<=n; p++)

    {

        // If prime[p] is not changed, then it is a prime

        if (prime[p] == true)

        {

            // Update all multiples of p

            for (int i=p*p; i<=n; i += p)

                prime[i] = false;

        }

    }

 

    

}

int conv_to_num(int a[])

{

 int n;

 n = (a[3] *1000)  + (a[2] *100)   + (a[1] * 10) + (a[0]);

 return n;

}




void conv_to_arr(int digit[],int n)

{

 digit[0] = n%10;

 n /= 10;

    digit[1] = n%10;

 n /= 10;

 digit[2] = n%10;

 n /= 10;

 digit[3] = n%10;

  

}

int main()

{

 int t;

 sieve();

 

 scanf("%d",&t);

 

 while(t--)

 {

      queue<int> q;

  int num1, num2,  i, digit[4];

  scanf("%d%d",&num1,&num2);

  memset(dist,-1,sizeof(dist));

  memset(visit,false,sizeof(visit));

  if(num1 == num2)

  {

   printf("0\n");

   continue;

  }

  q.push(num1);

     dist[num1] = 0;

     visit[num1] = true;

     //printf("hello\n");    //chedk

  while(!q.empty())

  {

           //printf("hello\n");    //chedk

        int val = q.front();

       // cout<<"val = "<<val<<endl;    //check

        if(val == num2)

        break;

       // q.pop();

       // conv_to_arr(val);

        //cout<<digit[3]<<digit[2]<<digit[1]<<digit[0]<<endl;

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

        {

             //int x = digit[i];

             conv_to_arr(digit,val);

                for(int j= 0; j<10; j++)

       {

            

               digit[i] = j;

         int temp = conv_to_num(digit);

         if(!visit[temp] && prime[temp] && temp >= 1000) 

         {

              //printf("hello\n");    //chedk

              //cout<<"temp = "<<temp<<endl;   //check

               visit[temp] = true;

               q.push(temp);

               dist[temp] =  dist[val] + 1;

             }  

       } 

      // digit[i] = x;

       //cout<<digit[3]<<digit[2]<<digit[1]<<digit[0]<<endl;

     }

     q.pop();

  } 

  if(dist[num2]==-1)

  printf("-1\n");

  else

  printf("%d\n",dist[num2]);

  //cout<<prime[3739]<<endl;

 }

 return 0;

} 

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;

}

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;



}

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;

}

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

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;

}