CareerCup

Ans:8

int main()
{
	int i,j,k,count=0;
	for(i=0;i<=2;i++)
	{
		for(j=0;j<=3;j++)
		{
			for(k=0;k<=2;k++)
			{
					if((i+j+k)==3)
					{
						cout<<i<<j<<k<<endl;
						count++;
					}
			}
		}
	}
	cout<<"count is "<<count;
	cin.get();
	return 0;
}

// simple solution
int main()
{
int i,j,k,count=0;
for(i=0;i<=2;i++)
{
for(j=0;j<=3;j++)
{
for(k=0;k<=2;k++)
{
if((i+j+k)==3)
{
cout<<i<<j<<k<<endl;
count++;
}
}
}
}
cout<<"count is "<<count;
cin.get();
return 0;
}

here is the generic solution works for all buckets

#include <cstdlib>
#include <iostream>

using namespace std;

 int ways;
void fill(int b[],int n,int sum,int toFill,int filled[],int index)
{
     if(sum==toFill)
     {
          ways++;
         cout<<"\n";           
         for(int i=0;i<index;i++)  
         cout<<filled[i]<<" ";
         return;
     }   
     if(index<n)
     {
       for(int i=0;i<=b[index];i++)      
       {
          filled[index]=i;
          fill(b,n,sum+i,toFill,filled,index+1);
       }
     }       
}     
int main(int argc, char *argv[])
{
    int b[]={2,3,2};
    int filled[3];
    fill(b,3,0,4,filled,0);
    
    cout<<"Total Number Of ways :"<<ways;
    system("PAUSE");
    return EXIT_SUCCESS;
}

6

ans is 8.
111
120
102
012
021
030
201
210

Is this problem like 0/1 knapsack? Can't really formulate exactly because there are 3 knapsacks here.

@insigniya: Was the question to be done programmatically or manually? If manually then Cl soln is the else if not then either DP or recursive mtd is to be applied.

Possible Algo:
polynomials:
P1(x) = 1 + x + x^2 //bucket 1 with capacity = 2
P2(x) = 1 + x + x^2 + x^3 //bucket 2 with capacity = 3
P3(x) = 1 + x + x^2 //bucket 3 with capacity = 2

Ans for n balls is coefficient of x^n in P1*P2*P3

Is there any shorter simpler to directly to do this?

FillBuck( int x[], int b1, int b2, int b3, int sum){
if (sum == 0) count ++;
else{
if( x[0] && b1<2) FillBuck(x, b1+1, b2, b3, sum-1);
if( x[1] && b1<3) FillBuck(x, b1, b2+1, b3, sum-1);
if( x[2] && b1<2) FillBuck(x, b1, b2, b3+1, sum-1);

x[0]=0;
if( b1 >0) FillBuck(x, b1-1, b2, b3, sum+1);
x[1]=0;
if( b2 >0) FillBuck(x, b1, b2-1, b3, sum+1);
x[2]=0;
if( b3 >0) FillBuck(x, b1, b2, b3-1, sum+1);
}
}

//FillBuck(x, 0, 0, 0, 3) ; where for i = 1 to 3, x[i]=1;