SPOJ : MARBLES Solution

Question MARBLES - Marbles
Explaination....
Fill n spaces , with k colors.
First select k spaces with k-different color. 
Now we are left with n-k spaces ,which can be filled with any of the k colors. Now to fill m-spaces by r-color with each r is infinte amount,we do this..

Using a method that's often called "stars and bars":
We draw n
stars in a row to represent the cakes, and k−1 bars to divide them up. All of the stars to the left of the first bar are cakes of the first type; stars between the first two bars are of the second type; 
 

**|***||*|

Here's an example with n=6
and k=5. We're getting 2 of the first type, 3 of the second type, 0 of the third type, 1 of the fourth type, and 0 of the fifth type.
In order to solve the problem, we just need to reorder the stars and bars by choosing the k−1
spots for the bars out of the n+k−1 total spots, so our answer is:

(n+k−1k−1)

((n-k)+k-1)C(k-1) =>  (n-1)C(k-1)  
#include <iostream>
#include<stdio.h>
#include<math.h>
#include<string.h>
using namespace std;

int main() {
    int t,i=0;
    scanf("%d",&t);
    long long int n,k;
    while(t--)
    {
        long long int res=1;
        scanf("%lld%lld",&n,&k);
        if( n-k < (k-1))//Its IMPORTANT! to get accepted
        k=n-k+1;//selecting the smaller value
        if(k==1)
        printf("1\n");
        else
        {
             for(i=1;i<=k-1;i++)
            {
            res=res*(n-i)/(i); 
       /* Dont do res*((n-i)/(i));divide then multiply
        * but instead do res*(n-i)/(i); Its multiply and divide */
            }
        printf("%lld\n",res);
        }
    }
  
    return 0;
}

To calculate nCr , n! will be huge. so we do n*(n-1)*(n-2)...... 
                                                                                                           1   2     3 .....k

SPOJ : EGYPIZZA Solution

Question EGYPIZZA - Pizza
Exaplaination :
Count the number of 1/4 , 1/2 , 3/4. 3/4 slice will have space for a 1/4 slice. Now,you can start from counting the number of 3/4, because a single can have just one slice of 3/4 and one of 1/4 at the same time.So , we count the number of 3/4slices, and the 1/4slices which can fit in each of them.Now,if there are extra 1/4slices, we add them up.Now,the fraction part of this sum tells what amount of slice is cut from last pizza. if we have some slice left(ie greater than equal to 1/2 of pizza),we can just have one 1/2slice from this pizza.Now, count the rest of 1/2 slices and account the no. of pizzas.


#include <iostream>
#include<stdio.h>
#include<math.h>
#include<string.h>
using namespace std;

int main() {
    int n;
    int half=0,one4=0,three4=0;
    scanf("%d",&n);//no. of slices
    char st[5];
    while(n--)
    {
     scanf(" %s",st);
     if(strcmp(st,"1/4")==0) one4++;
     if(strcmp(st,"1/2")==0) half++;
     if(strcmp(st,"3/4")==0) three4++;//counting no.of slices of each type
    }
    int sum=three4;//counting no.of 3/4 slices
    three4-=one4;//fitting them with 1/4 slices
    if(three4<0)//if its negative, means there still some 1/4 slices
      {
          double k=(-three4 * 1.0/4.0);//sum all left over 1/4 slices
          sum=sum+(int)k;//add no.of pizzas
          k=k-(int)k;//amount cut off last pizza,its <1
          k=1-k;//amount left in last pizza
          if(k>=0.5 && half>0)//if amount left is still >=0.5
            half--;//cut off a half from it
          sum++;//add no. of pizza
      }
    sum=sum+(ceil(half*0.5));//add rest of half slices
    sum=sum+1;//add one pizza of winner
    printf("%d\n",sum);
    return 0;
} 

SPOJ : EASYPROB solution

Question :EASYPROB - A Very Easy Problem!
The expansion is power.Eg 137= 2^(2^2 +2+ 2^0)+2^(2+2^0)+2^0
Eg.137 is 10001001
1 Now, To find the first (leftmost) set bit ,you can use k=log(num)/log(2).(gives you 7 as 7th bit is set)
2 Then to remove that first set bit ,you substract num=num-2^k. This gives you resultant number.(gives you 1001)
Now Repeat the above steps until num is 0
 
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#include<iostream>
#include<math.h>
#define LL long long
#define mx 10010
using namespace std;

void rec(int num)
{
    //printf("rec==%d\n",num);
    if(num==1) {return ;}
    if(num==0) {printf("0");return ;}
    if(num==2) {printf("2");return ;}

        while(num>0)
        {
            double k=(log(num)/log(2));
            int lo=(int)k;//printf("while==%d, lo=%d\n",num,lo);
            if(lo==1) printf("2");
            else    printf("2(");

            rec(lo);
          //printf("  %d",num);
           num=num-(int)(pow(2,lo));
           if(lo!=1)
           printf(")");
           if(num>0) printf("+");
        }
        return ;
}

int main()
{
    //int num=128;
    //double k=(log(num)/log (2));
    //printf("%d",(int)k);
    printf("137=");rec(137);
    printf("\n1315=");rec(1315);
    printf("\n73=");rec(73);
    printf("\n136=");rec(136);
    printf("\n255=");rec(255);
    printf("\n1384=");rec(1384);
    printf("\n16385=");rec(16385);
    printf("\n");
    return 0;
}    

SPOJ : PIR Solution

Question:PIR - Pyramids
Explaination 
Use the formula  
 
Heron-type formula for the volume of a tetrahedron
If U, V, W, u, v, w are lengths of edges of the tetrahedron (first three form a triangle; u opposite to U and so on), then
                                                             
    volume=\/(-a+b+c+d)*(a-b+c+d)*(a+b-c+d)*(a+b+c-d)  
                            192*u*v*w 
where                           
a=\/xYZ  b=\/yZX    c=\/zXY  d=\/xyz 
X=(w-U+v)*(U+v+w) 
x=(U-v+w)*(v-w+U)
Y=(u-V+w)*(V+w+u)
y=(V-w+u)*(w-u+V)
Z=(v-W+u)*(W+u+v)
z=(W-u+v)*(u-v+W) 

${\displaystyle {\begin{aligned}a&={\sqrt {xYZ}}\\b&={\sqrt {yZX}}\\c&={\sqrt {zXY}}\\d&={\sqrt {xyz}}\\X&=(w-U+v)\,(U+v+w)\\x&=(U-v+w)\,(v-w+U)\\Y&=(u-V+w)\,(V+w+u)\\y&=(V-w+u)\,(w-u+V)\\Z&=(v-W+u)\,(W+u+v)\\z&=(W-u+v)\,(u-v+W).\end{aligned}}}$

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#include<iostream>
#include<math.h>
#define LL long long
#define mx 10010
using namespace std;
int main()
{
    double u,v,w,U,V,W;
    int t=0;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%lf%lf%lf%lf%lf%lf",&u,&v,&w,&W,&V,&U);
        double a,b,c,d,x,y,z,X,Y,Z;
        X=(w-U+v)*(U+v+w);
        x=(U-v+w)*(v-w+U);
        Y=(u-V+w)*(V+w+u);
        y=(V-w+u)*(w-u+V);
        Z=(v-W+u)*(W+u+v);
        z=(W-u+v)*(u-v+W);
        a=sqrt(x*Y*Z);
        b=sqrt(y*Z*X);
        c=sqrt(z*X*Y);
        d=sqrt(x*y*z);
        double vol=(b+c+d-a)*(a-b+c+d)*(a+b-c+d)*(a+b+c-d);
        vol=sqrt(vol)/(192*u*v*w);
        printf("%.4lf\n",vol);
    }
    return 0;
}   

SPOJ : NGM Solution

Question :NGM - A Game with Numbers
This problem must be given some time to tinker the brains  
Explaination 
If the largest digit is at the unit's place,then 1st player has to substract it and number becomes ".....0".Now,if you use pen on paper to solve it eg. 58 makes payer1 to win, 64 makes player2 to win.
64 , 58 , 50, 45, 40 ,36, 30 ,27, 20, 18 , 10,9->0


#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#include<iostream>
#define LL long long
#define mx 10010
using namespace std;

int main()
{
    char ss[12];
    scanf("%s",ss);
    int l=strlen(ss);
    int i=0,lar=ss[0]-'0',pos=0,k=0;
    for (i=1;i<l;i++)
    {
        k=ss[i]-'0';
        if(k>lar) lar=k,pos=i;
    }
    if(pos==l-1)
        printf("1\n%d\n",lar);
    else
        printf("2\n");

    return 0;
}
 

SPOJ : FENCE1 Solution

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#include<iostream>
#define LL long long
using namespace std;

int main()
{
   int a;//Don't use 22/7 or 22.0/7.0 because its value is different    double pi=3.14159265359;
   while(scanf("%d",&a) && a!=0)
   {
      printf("%.2lf\n",(double)(a*a)/pi/2);
  }

   return 0;
}

SPOJ : OFFSIDE Solution

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#include<iostream>
#define LL long long
#define mx 10010
using namespace std;

int main()
{
    int n,i;
    int a,b;
    scanf("%d%d",&a,&b);
    while(a!=0 || b!=0)
      {
          int small=mx;
          while(a--)
          {scanf("%d",&i);if(i<small)small=i;}

          int sm1=mx,sm2=mx,pos=0;
          int k[b];
          for(i=0;i<b;i++)
          {
              scanf("%d",&k[i]);
              if(k[i]<sm1) sm1=k[i],pos=i;
          }
          for(i=0;i<b;i++)
          {
              if(k[i]<=sm2 && k[i]>=sm1 && i!=pos) sm2=k[i];
          }

          //printf("%d %d %d\n",small,sm1,sm2);

          if(small==sm2 || (small==sm2 && small==sm1))
            printf("N\n");
          else
          {if(small<sm2)
            printf("Y\n");
            else printf("N\n");
          }

            scanf("%d%d",&a,&b);
      }

    return 0;
}
Question at: OFFSIDE - He is offside!
Find smallest element in the ist array , this will be the last player closest to goal line.Then find the smallest and second smallest element as sm1 and sm2 in 2nd array , this will be the last and second last player of opponent team, then apply offside and not offside rule as given in question.