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.

SPOJ: PTO7Y Solution

#include<stdio.h>
#include<stdlib.h>
#include<vector>
#include<stack>
#define N 10005

using namespace std;
stack <pair<int,int> > s;
int main()
{
vector <int> adj[N];//array of vectors
int vt[N];
    int i,j,k,n,e,a,b;
    scanf("%d%d",&n,&e);
    for(i=0;i<e;i++)
    {
        scanf("%d%d",&a,&b);
        adj[a].push_back(b);
        adj[b].push_back(a);
    }
    for(i=0;i<N;i++)
        vt[i]=0;
    if(n!=(e+1))
      {
          printf("NO\n");
          return 0;
      }
      else
      {
       int i=1,parent,c=0,count=0;
       parent=-1;
       s.push(make_pair(i,parent));
     //while
       while(!s.empty())
       {
            pair<int,int> kk=s.top();
            s.pop();
            int k=kk.first;
            int p=kk.second;
            vt[k]=1;//printf("parent=%d\n",p);
            for(i=0;i<adj[k].size();i++)
              {
                  int d=adj[k][i];
                  if(!vt[d])
                  {
                   p=k;s.push(make_pair(d,p));
                  }
     else if(d!=p)/*else if d is visited , then it must be the parent. If its not parent then there is a cycle*/
   {c=1;
     break;}
              }//for closed

            if(c==1)
            break;
            count++;
          }
          if(c==1  ) printf("NO\n");
          else if(count!=n) printf("NO\n");
          else  printf("YES\n");

      }//else
    return 0;
}

SPOJ: LASTDIG Solution

SPOJ Solution Of LASTDIG

Source Code.....

#include<stdio.h>
#include<stdlib.h>
using namespace std;
int main()
{
    int a2[10][4]={{0,0,0,0},{1,1,1,1},{6,2,4,8},{1,3,9,7},{6,4,6,4},{5,5,5,5},{6,6,6,6},{1,7,9,3},{6,8,4,2},{1,9,1,9}};// last digits of all numbers when
                                  // repeatedly multiplied by its own number
    long int b;
    int a,t,l,z=0;
    for(scanf("%d",&t);t>0;t--)
    {   z=0;
        scanf("%d%ld",&a,&b);
        l=a%10;  //Get last digit of the number
        z=a2[l][b%4]; //Get last digit of a raised to power b
         if(a!=0 && b==0)  //condition when number is raised to the power zero.
            printf("1\n");
         else
        printf("%d\n",z);
    }
    return 0;
}

EXPLAINATION:  

Note that each number will repeat some set of numbers on being raised to some power. Therefore ,

keeping all the set in a matrix.Try keeping variable names as small as possible because Space Limit is just 700Bytes. :) 

Also erase any extra space in code or output ..

SPOJ : DIVSUM Solution

Spoj:  DIVSUM Solution


#include<stdio.h>
#include<stdlib.h>
#include<iostream>

using namespace std;

int main()
{
int divisor[500002];    //creating array to store divsum 
                                     //of all numbers till 500001 
int t,i=0,j=0,n=0;

for(i=1;i< 500002;i++)
{
    for(j=2*i;j< 500002; j+=i){
        divisor[j]+=i;                  
    }                                  
}

for(scanf("%d",&t);t>0;t--){
    scanf("%d",&n);
    printf("%d\n",divisor[n]);
}
return 0;
}

EXPAINATION :

  To create the array of divsum ,  do it the same way as in Sieve of Eratosthenes. That is, first mark all multiple of 2 except 2*1 ,   then mark all multiples of 3 except 3*1 i.e starting from 3*2 and then mark all multiples of 4 except 4*1 ie starting fron 4*2 and so on....

SPOJ : CANDY 1 solution

EXPLANATION :

This one has a simple way to solve just by using averages.
Calculate the sum of all candies, now if it can be completely 
divided by total no. of packets , i.e remainder of sum/total no. 
of packets , candies can be equally divided into each packet.
Now get the average , and find out the moves.. 

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

int main()
{

    int n,t,sum=0,rem=0,avg=0,total=0;
   
    while(1)
    {
     scanf("%d",&n); // n is no. of packets
     sum=0;
     if(n==-1)   //to end inputting
        break;
     int candy[n];//array for no. of candy in each packets
     for(t=0;t<n;t++)
     {
         scanf("%d",&candy[t]);
         sum+=candy[t];
     }

     rem=sum%n;
     avg=sum/n;
     if(rem != 0)//means it cannot be divided equally
     {
         printf("-1\n");
     }
     else    // else get the total no. of moves by using averages
        {
          total=0;
          for(t=0;t<n;t++)
          {
              if(candy[t]>avg)
                total=total+(candy[t]-avg);
          }
          printf("%d\n",total);
    }//else closed
    }
    return 0;
}