Monthly Archives: November 2015

Spoj IITKWPCN solution

Spoj IITKWPCN solution. Spoj Playing With Balls solution.

Category : AdHoc

Related post : Spoj HC solution.

In this question, if the two balls belong to the same colour , in that case the white ball is put back else black.
This seems a little confusing, lets substitute the balls with signs.

Lets say that black is ‘-‘(negative) and white is ‘+'(positive). Let us check our assumption.

According to the problem, if the chosen balls belong to the same colour, the ball put back will be white else black.
Going with our assumption, if the two signs are same it will result in ‘+'(white)( – – =+ ) else ‘-‘(black), which is true.
So, irrespective of the order of balls chosen, if the number of ‘-‘ balls is even it will result in ‘+’ else ‘-‘.

So we can see if the number of balls initially belonging to black is even, it will finally belong to white else black.

Spoj IITKWPCN solution code:

Here is the working code:

#include <bits/stdc++.h>
using namespace std;

int main() {
   int t,W,B;
   scanf("%d",&t);
   while(t--)
   {
      scanf("%d%d",&W,&B);
      double ans=0;
      if(B%2==1)
         ans=1;
      printf("%0.6lf\n",ans);
   }
   return 0;
}

Spoj HC solution

Spoj HC solution. Spoj Happy Coins solution.

Category: AdHoc

In this question, if the two coins belong to the same person, in that case the coin belongs to hhb else to lxh.
This seems a little confusing, lets substitute the coins with signs.

Lets say that lxh is ‘-‘(negative) and hhb is ‘+'(positive). Let us check our assumption.

According to the problem, if the chosen coins belong to the same person, the new coin will belong to hhb else lxh.
Going with our assumption, if the two signs are same it will result in ‘+'(hhb) else ‘-‘(lxh), which is true.
So, irrespective of the order of coins chosen, if the number of ‘-‘ coins is even it will result in ‘+’ else ‘-‘.

So we can see if the number of coins initially belonging to lxh is even, it will finally belong to hhb else lxh.

Spoj HC solution code:

Here is the working code:

#include <bits/stdc++.h>
using namespace std;

int main() {
   int t,n;
   scanf("%d",&t);
   while(t--)
   {
      scanf("%d",&n);	
      char str[4];
      int countv=0;
      while(n--)
      {
         scanf("%s",str);
         
         /*Counting the coins that
         belong to lxh*/
         if(!strcmp(str,"lxh"))
            countv++;
      }
      if(countv%2==0)
         printf("hhb\n");
      else
         printf("lxh\n");
   }
   return 0;
}

Similar question: Spoj IITKWPCN

Spoj CIRCLE_E solution

Spoj CIRCLE_E solution. Spoj Three Circle Problem Problem

Category: AdHoc, Maths

CIRCLE_E/Three Circle Problem

This question is the direct application of Soddy Circles(Inner).

We are given three radii, we need to print the 4th radius.

Her is the Formula:

 r_4^+/-=(r_1r_2r_3)/(r_1r_2+r_1r_3+r_2r_3+/-2sqrt(r_1r_2r_3(r_1+r_2+r_3))).

Spoj CIRCLE_E solution code:

Here is the working code:

#include <bits/stdc++.h>
using namespace std;

int main() {
   int t;
   double r1,r2,r3,r4;
   scanf("%d",&t);
   while(t--)
   {
      scanf("%lf%lf%lf",&r1,&r2,&r3);	
      double den=((r1*r2)+(r1*r3)+(r2*r3)+2*(sqrt((r1*r2*r3)*(r1+r2+r3))));
      r4=((r1*r2*r3)/den);
      printf("%lf\n",r4);
   }
   return 0;
}

Spoj FTHEELF solution

Spoj FTHEELF solution. Spoj Feanor The Elf solution.

Category: AdHoc, Formula

In this question is simply based on the formula.

Refer to the code to see the formula.

Spoj FTHEELF solution code:

Here is the working code:

#include <bits/stdc++.h>
using namespace std;

int main() {
   int V,H;
   scanf("%d%d",&V,&H);
   while(V!=-1)
   {
      printf("%.6f\n",V / 9.8 * sqrt(2 * 9.8 * H + V * V));
      scanf("%d%d",&V,&H);
   }
   return 0;
}

Spoj FASHION solution

Spoj FASHION solution. Spoj Fashion Shows solution.

Category: AdHoc, Sorting

In this question, we need to maximise the hotness bond X*Y.

To maximise anything, we need to multiply the biggest of the values.

Algorithm:

  1. Input the two arrays.
  2. Sort the two arrays.
  3. Initialise ans=0.
  4. for each element in the array
    add product of men[i]*women[i] to ans.
  5. Print ans.

Spoj FASHION solution code:

Here is the working code:

#include <bits/stdc++.h>
using namespace std;

int main() {
   int t,n;
   scanf("%d",&t);
   while(t--)
   {
      scanf("%d",&n);
      
      int men[n],women[n];
      for(int i=0;i<n;++i)
         scanf("%d",&men[i]);
      for(int i=0;i<n;++i)
         scanf("%d",&women[i]);	
         
      sort(men,men+n);
      sort(women,women+n);
      
      int ans=0;
      
      for(int i=0;i<n;++i)
         ans+=men[i]*women[i];
      printf("%d\n",ans);
      
   }
   return 0;
}

Spoj MKLABELS solution

Spoj MKLABELS solution. Spoj Making Labels solution.

Category: AdHoc, Maths

In this question, if you analyse you will get to know that you simply have to print N(N-2).

Spoj MKLABELS solution code:

Here is the working code:

#include <bits/stdc++.h>
using namespace std;

int main() {
   int n,caseCount=0;
   scanf("%d",&n);
   while(n)
   {
      caseCount++;
      
      /*Multiplying ans with N, N-2 times*/
      int ans=1;
      for(int i=1;i<=(n-2);++i)
         ans*=n;
         
      printf("Case %d, N = %d, # of different labelings = %d\n",caseCount,n,ans);
      scanf("%d",&n);
   }
   return 0;
}

Spoj SILVER solution

Spoj SILVER solution. Spoj Cut the Silver Bar Solution.

Category : AdHoc, Maths

In this question, we need to give the number of minimum cuts required.

Explanation:

Any number up to 2n-1 can be represented by the combinations of the ‘n’ numbers: 20,21,22,…2n-1.
For example, if 7 is considered, all numbers from 1 to 7 can be represented as combinations of 1,2, and 4:

1 = 1; 2 = 2; 3 = 1+2; 4 = 4; 5 = 1+4; 6 = 2+4; 7 = 1+2+4

If 9 is considered, all numbers from 1 to 9 can be represented as combinations of 1,2,4 and 2:
1 = 1; 2 = 2; 3 = 1+2; 4 = 4; 5 = 1+4; 6 = 2+4; 7 = 1+2+4; 8 = 2+2+4; 9 = 1+2+2+4;

If 15 is considered, all numbers from 1 to 15 can be represented as combinations of 1,2,4 and 8:
1 = 1; 2 = 2; 3 = 1+2; 4 = 4; 5 = 1+4; 6 = 2+4; 7 = 1+2+4; 8 = 8; 9 = 1+8; 10 = 2+8;
11 = 1+2+8; 12 = 4+8; 13 = 1+4+8; 14 = 2+4+8; 15 = 1+2+4+8

EXAMPLE:

Let the length of the rod is : 31µ

If miner cuts the silver bar of 31µ in to the pieces with following sizes , it will result in minimum number of pieces- solution:

1, 2, 4, 8, 16

On day-1 miner gives 1-inch piece to the creditor.
On day-2 he gives 2-inch piece and takes back the 1-inch piece.
On day-3 he gives 1-inch piece in addition to the already given 2-inch piece, thus making it 3-inches in total.
On day-4 he gives 4-inch piece and takes back the 1-inch and 2-inch pieces.
On day-5 he gives 1-inch piece in addition to the already given 4-inch piece, thus making it 5-inches in total.
This will continue till day-31.

Hence a minimum of five pieces is enough, and to make 5 pieces, only 4- cuts  are required.

THUS, we need to find the maximum power of two, less than N or , we need to count the number of times that we need to divide N so that N becomes less than or equal to 1

Algorithm:

  1. Initialise ans=0
  2. Till N>1
    Divide N by 2, increment ans.
  3. Print ans

Spoj SILVER solution code:

Here is the working code:

#include <bits/stdc++.h>
using namespace std;

int main() {
   int n;
   scanf("%d",&n);
   while(n)
   {
      int ans=0;
      while(n>1)
      {
         n=n>>1;
         ans++;
      }
      printf("%d\n",ans);
      scanf("%d",&n);
   }
   return 0;
}

Spoj TAP2013G solution

Spoj TAP2013G solution. Spoj WAR solution.

Category: AdHoc, Sorting

In this question, we need to tell the numbers of battle can be won by NLogN army.

we sort and then compare the values of two armies, if they NlogN[j]>Quadrad[i], we increment our answer as well as both i and j, else we increment the value of ‘j’ and check with the next soldier. This is repeated till i,j<n.

Algorithm:

  1. Initialise ans=0.
  2. Sort the two arrays representing armies.
  3. if NlogN[j]>Quadrad[i],
    increment i,j , ans. (i,j are incremented as 1 soldier can fight once).
  4. else
    increment j, to check for next soldier.

Spoj TAP2013G solution code:

Here is the working code:

#include <bits/stdc++.h>
using namespace std;

int main() {
   int n;
   scanf("%d",&n);
   int NlogN[n],Quadrad[n];
   
   for(int i=0;i<n;++i)
      scanf("%d",&Quadrad[i]);
   for(int i=0;i<n;++i)
      scanf("%d",&NlogN[i]);	
   
   sort(NlogN,NlogN+n);
   sort(Quadrad,Quadrad+n);
   
   int ans=0,i=0,j=0;
   
   while(i<n && j<n)
   {
      /*In this case the NlogN 
      army can win a battle, 
      so we incremenet the count*/
      if(Quadrad[i]<NlogN[j])
      {
         ans++;
         i++;
         j++;
      }
      /*If we cant win, we check if 
      the next soldier can win*/
      else
         j++;
   }
   printf("%d\n",ans);
   return 0;
}

Spoj MAXLN solution

Spoj MAXLN solution. Spoj THE MAX LINES solution.

Category: AdHoc, Maths

Explanation:

MAXLN

Angle in a semi-circle is a right angle always, hence, the triangle formed  is a Right angled triangle (Thales’ theorem).
So, now we have :

AB2+AC2=BC2
AB2+AC2=(2r)2
AB2=4r2AC2
In the question we have this equation:
s=AB2+AC
s=4r2AC2+AC
s=AC2+AC+ 4r2

Now we have a quadratic equation, and we have to find its maximum. Maximum value occurs when
AC=-b/2a
So now using values of a and b from equation we get :
AC=-b/2a
AC=-1/-2
AC=1/2
Putting the value of AC in equation we get :
s=(1/2)2+1/2+4r2
s=(1/4)+1/2+4r2
s1/4+4r2
s=0.25+4r2

Hence the equation we are going to use is :
s=0.25+4r2

Spoj MAXLN solution code:

Here is the working code:

#include <bits/stdc++.h>
using namespace std;

int main() {
   int t,caseCount=0;
   double r, s;
   scanf("%d",&t);
   while(t--)
   {
      caseCount++;
      scanf("%lf",&r);	
      
      /*For maximum length, after 
      solving we get this equation for s*/
      s= 0.25 + 4*r*r;
      
      /*To print only two digits after decimal*/
      printf("Case %d: %0.2lf\n",caseCount,s);
   }
   return 0;
}

Spoj ZSUM solution

Spoj ZSUM solution. Spoj Just Add It solution.

Category: Number Theory, Modular Exponentiation

Pre-Requisite:  Modular Exponentiation

For two given integers n and k find (Zn+Zn-1-2Zn-2)mod 10000007 , where Zn=Sn+Pn and Sn=1k+2k+3k+…..+nk and Pn=11+22+33+……+nn.

After substituting the values for all Zi we are left with only 4 terms :
nk+ nn + 2(n-1)(n-1) + 2(n-1)..

We just need to sum these 4 terms using modular addition, these 4 values/terms  are calculated using Modular Exponentiation (refer to the link to understand how it works)

Spoj ZSUM solution code:

Here is the working code:

#include <bits/stdc++.h>
using namespace std;
#define LL long long
 
 /*ModularExponentiaion*/
LL ModEx(LL x,LL n,LL p)
{
       LL ans=1,temp=x%p;
       while(n)
       {
              if(n&1) // to check if last bit is 1 or not
              {
                     ans=(ans*temp)%p;
              }
              n>>=1;
              temp=(temp*temp)%p;
       }
       return  ans%p;
}

int main() {
   LL p=10000007;
   LL n,k;
   scanf("%lld%lld",&n,&k);
   while(n && k)
   {
      /*We use modular exponentiation
      to calculate and sum the 4 terms 
      that are left after expansion*/
      
      LL ans=ModEx(n,k,p);
      ans = (ans + ModEx(n,n,p))%p;
      ans = (ans +2*ModEx(n-1,n-1,p))%p;
      ans = (ans + 2*ModEx(n-1,k,p))%p;
      
      printf("%lld\n",ans);
      scanf("%lld%lld",&n,&k);
   }	
   return 0;
}