CareerCup

This simple code will work... some error checking will be needed but simple tree traversal is sufficient. but I think you can assume in beginning that N liters of water will fill in buckets with C capacity each.

void fillBuckets(BinaryTree *  root,double C,double N){
  if(!root) return;
  
  double diff=C-root->val; // root->val is 0 initially for each bucket. some modification is needed is it can have other value
  
  if(diff>=N){  //this bucket can take all water
     root->val+=N;
     N=0;
  }else{ //fill bucket completely and spill remaining water. trick is we don't need to take care of any bucket getting overflow. simply spill water to lower levels. If bucket is filled completely by left parent, right will spill all water.
     root->val+=diff;
     N-=diff;
   }
 
  if(N>0){
    fillBuckets(root->left,C,N/2);
    fillBuckets(root->right,C,N/2);
  }
}

For fillBuckets(root,5,40), this gives
5
5 5
5 5 5
.625 4.375 4.375 .625

please let me know if any thing is wrong.

no of glasses on level L is L i.e. total glasses = 1+2+...+L = L(L+1)/2 == call it t
if(N >= t) all glasses full;
else some glasses empty or partly filled.

In the second case, I guess go one by one, N < C level 1
N>C && N<3C level 2
and so on.
The partly filled case can be thought of as dividing extra equally among all in the given level,

first calculate int n = floor[log(N/C + 1)/log2]
Now all levels less then n will have C amount of water and glasses at level n will have
(N-(2^n-1)C)/2^n.

lets take an example suppose we have N = 4C
in this case n = 2, which means glasses at level 0 and 1(i.e < 2) will have C amount of water and glass at level 2 will have (N-3C)/4 i.e C/4 each.

Following code will let to take to the goal ....

class GlassesStatus {

    double liquidInLiters, capacityOfEachGlass;
    int numberOfLevelsOfGlasses;
    int level = 0;

    GlassesStatus(double liquid, double capacity, int levels) {
        this.liquidInLiters = liquid;
        this.capacityOfEachGlass = capacity;
        this.numberOfLevelsOfGlasses = levels;
    }

    void describeGlassesStatus() {
        System.out.println("In Method ...");
        int glassNumber = 1;
        int level = 1;
        describe(glassNumber, liquidInLiters);
    }

    private void describe(int glassNumber, double liquidInLiters) {
        if (level <= numberOfLevelsOfGlasses) {
            if (liquidInLiters < 0) {
                System.out.println("No Liquid in " + glassNumber);
            } else {
                if (liquidInLiters <= capacityOfEachGlass) {
                    System.out.println("In glass-" + glassNumber + " : " + liquidInLiters + " litres");
                } else {
                    System.out.println("In glass-" + glassNumber + " : " + capacityOfEachGlass + " litres");
                    liquidInLiters = liquidInLiters - capacityOfEachGlass;
                    describe((glassNumber * 2), liquidInLiters / 2);
                    describe((glassNumber * 2) + 1, liquidInLiters / 2);
                    level++;
                }
            }
        }
    }
}

AnanthaNag KUNDANALA

Below is the workable code

#include "stdafx.h"
#include <iostream>
#include <iomanip>
using namespace std;

void pascal_water(int n, int, float);

float storeW[1000][1000];

int _tmain(int argc, _TCHAR* argv[])
{
	int level = 5, capacity = 1;
	float totalwater=10; 
	pascal_water(level-1, capacity, totalwater);

	for(int i=0; i<=level; i++)
	{
		for(int j=0; j<=level; j++)
			cout << setw(3) << storeW[i][j];
		cout << endl;
	}
	return 0;
}

void pascal_water(int level, int capacity, float totalwater)
{
	storeW[0][0] = totalwater;

	for(int i=0; i<level; i++)
	{
		for(int j=0; j<=i; j++)
		{
			if(storeW[i][j] > capacity)
			{
				float temp = storeW[i][j] - (float)capacity;
				storeW[i][j] = capacity;
				storeW[i+1][j] += temp / 2;
				storeW[i+1][j+1] += temp / 2;
			}
		}
	}
}

float storeW[1000][1000];
for(int i=0; i<level; i++)
{
   for(int j=0; j<=i; j++)
   {
      if(storeW[i][j] > capacity)
      {
         float temp = storeW[i][j] - (float)capacity;
	 storeW[i][j] = capacity;
	 storeW[i+1][j] += temp / 2;
	 storeW[i+1][j+1] += temp / 2;
      }
   }
}

Its like this ...
C capacity of each glass... let first glass gets C remainingn N-C it has to be destributed between two class so each gets (N-C)/2
now again the capacity of next glass C so the remagnign for next lavel.. (N-C)/2 -C
so the next level will get (N-3C)/4 so if root is level 0 ie n=1 then each will get (N-(2n-1)*C)/2^n-1

{
void AmazonGlassProblem(int maxlitres, int numberofLevel, int glassCapacity)
{
float glasses[1000] = {0};
int glassInALevel = 1;
int currentLevel = 0;
bool isNextLevelRequired = true;
glasses[0] = maxlitres;
while(currentLevel < numberofLevel)
{
for(int indexInLevel = 1; indexInLevel <= currentLevel + 1; indexInLevel++)
{
int glassIndex = (currentLevel*(currentLevel + 1))/2;
if(glasses[glassIndex - 1+indexInLevel] > glassCapacity)
{
float remainCapacity = glasses[glassIndex - 1+indexInLevel] - glassCapacity;
int nextIndex = ((currentLevel+1) * (currentLevel + 2))/2 + indexInLevel;
glasses[nextIndex -1] += remainCapacity/2;
glasses[nextIndex] += remainCapacity/2;
glasses[glassIndex - 1+indexInLevel] = glassCapacity;
}
}
currentLevel++;
}
for(int index =0 ; index < (numberofLevel *(numberofLevel + 1))/2; index++)
{
std::cout<<"\n Glass of "<<index<<" "<<glasses[index]<<" "<<"litres";
}

}

void InputForMaxLitresProblem()
{
AmazonGlassProblem(10,5,1);
}
}

void AmazonGlassProblem(int maxlitres, int numberofLevel, int glassCapacity)
{
float glasses[1000] = {0};
int glassInALevel = 1;
int currentLevel = 0;
bool isNextLevelRequired = true;
glasses[0] = maxlitres;
while(currentLevel < numberofLevel)
{
for(int indexInLevel = 1; indexInLevel <= currentLevel + 1; indexInLevel++)
{
int glassIndex = (currentLevel*(currentLevel + 1))/2;
if(glasses[glassIndex - 1+indexInLevel] > glassCapacity)
{
float remainCapacity = glasses[glassIndex - 1+indexInLevel] - glassCapacity;
int nextIndex = ((currentLevel+1) * (currentLevel + 2))/2 + indexInLevel;
glasses[nextIndex -1] += remainCapacity/2;
glasses[nextIndex] += remainCapacity/2;
glasses[glassIndex - 1+indexInLevel] = glassCapacity;
}
}
currentLevel++;
}
for(int index =0 ; index < (numberofLevel *(numberofLevel + 1))/2; index++)
{
std::cout<<"\n Glass of "<<index<<" "<<glasses[index]<<" "<<"litres";
}

}

void InputForMaxLitresProblem()
{
AmazonGlassProblem(10,5,1);
}

#include <iostream>
using namespace std;
#define N 50
#define C 5
#define L 5 //assumed level start 0,1,2,3...
int main()
{
int i,j;
float arr[(L*(1+L))/2] = {0.0,};
int total_glass = (L*(1+L))/2;
int left, right;
int current;
float remain;
int flag = 1; // to exit loop if no glass at a level has more than C litre.

arr[0] = N;
for(i = 0; i<L && flag; i++)
{
flag = 0;
for(j = 0; j<(i+1)/*no. of node at a particular level*/; j++)
{
current = (i*(i+1))/2 + j;
left = current + (i + 1);
right = left + 1;
if(arr[current] > C)
{
remain = arr[current] - C;
arr[current] = C;
if(right < total_glass)
{
arr[left] += remain/2;
arr[right] += remain/2;
}
flag = 1;
}
}
}
for(i = 0; i<total_glass; i++)
{
if(arr[i] > C)
cout<<i<<"th "<<C<<endl;
else
cout<<i<<"th "<<arr[i]<<endl;
}
getchar();
return 0;
}

ooops this is so simple !!! do practical n start coding...lol
T -> total liquid in ltrs poured at 1st glass
L -> level (considering each glass row as a level) 
C -> Capacity of individual glass
arr -> array of glasses(i.e. total glasses = L * (L + 1)  / 2

void pour_liquid(float *arr, int T, int L, int C)
{
	int level = 0, element = 0;

	*(arr + 0) = T;/* POURING T ltrs here */
	for (level = 1; level <= L; ++level)
		for (element = ((level * (level + 1)) / 2 ) - level; element < (level * (level + 1) / 2); ++element)
		{
			if ((C < *(arr + element)) && (level != L))
			{
				*(arr + element + level) += ((*(arr + element) - C) / 2);
				*(arr + element + level + 1) += ((*(arr + element) - C) / 2);
				*(arr + element) = C;
			}
			else
			{
				if ((C < *(arr + element)) && (level = L))
				       *(arr + element) = C;/* liquid spilled over at last level glasses and wasted */ 
			}	
		}
		
}


Oolalalaaa....

Number of Levels needed for N litres to accommodate, in a Binomial Tree Expansion like Tree of cups with Capacity "C" = Log2((N+C)/C) . (We can prove this with simple Geometric Progression sequence)

When we compute this it will be some floating point number. Let's say number of levels comes out to be 2.7 then it means that we need 2 Levels completely filled and 3rd level distributed accordingly. we can compute the liquid left after filling 2 levels and then fill 3rd level.

Am I missing something? This seems like a math problem, not a coding problem.


Total capacity of all glasses (T) = C * sum(1 -> L)

Total # of glasses filled (G) = floor(N / T)

Remainder R = N/T - G; will be split evenly across L glasses.

???

I hate looking at code without mathematical explanation or proof. :)

this is an old question.

Every node has to have two children.. why does the figure show otherwise? :O

We can use a 2-d array of vessels for storing their current water. We start from the top assigning whole jug of water ( pot ) to the top vessel. Vessels would basically keep water of its capacity ( c ) and spill the rest equally (current - c )/2 to its left and right vessels. It would try to fill itself to c. At every vessel we decrease the remaining water to be distributed. Here's sample code in c:

#include<stdio.h>

int main()
{
        int h=0,i,j,c=5;
        float v[10][10],pot=50;
        v[0][0]=pot;

        while(pot!=0)
        {
                for(i=0;i<=h+1;i++)
                        v[h+1][i] = 0;

                for(i=0;i<=h;i++)
                {
                        if(v[h][i] > c)
                        {
                                v[h+1][i] += (v[h][i]-c)/2;
                                v[h+1][i+1] += (v[h][i]-c)/2;
                                v[h][i] = c;
                        }
                        pot -= v[h][i];
                }
                h++;
        }
        for(i=0;i<h;i++)
        {
                for(j=0;j<=i;j++)
                        printf("[%d][%d]: %f\t",i,j,v[i][j]);
                printf("\n");
        }
return 0;
}

node* fillCup(node *root,float pour,float capacity)
{
float temp;
if(root==NULL)
return NULL;

if(root->data+pour >= capacity)
{
if(root->data==0)
{
root->data=capacity;
pour=pour-capacity;
}
else
{
// this will execute if there is already some water added to this node but cup is not full
temp=capacity-(root->data);
root->data=capacity;
pour=pour-temp;
if(pour==0)
{
return root;
}

}
}
else
{
// for the case amout poured to this node is less than capacity of the cup
root->data+=pour;
return root;

}

fillCup(root->left,pour/2,capacity);
fillCup(root->right,pour/2,capacity);
}

given a tree , suppose intially data of each node is set to 0. bcozz they are empty.
now just keep on spilling pour/2 to left ans right child. this will take care of the shared node also.

node* fillCup(node *root,float pour,float capacity)
{
float temp;
        if(root==NULL)
                return NULL;

        if(root->data+pour >= capacity)
        {
                if(root->data==0)
                {
                        root->data=capacity;
                        pour=pour-capacity;
                }
                else
                {
                     // this will execute if there is already some water added to this node but cup is not full
                        temp=capacity-(root->data);
                        root->data=capacity;
                        pour=pour-temp;
                        if(pour==0)
                        {
                                return root;
                        }

                }
        }
        else
        {
              // for the case amout poured to this node is less than capacity of the cup
                root->data+=pour;
                return root;

        }

        fillCup(root->left,pour/2,capacity);
        fillCup(root->right,pour/2,capacity);
}

given a tree , suppose intially data of each node is set to 0. bcozz they are empty.
now just keep on spilling pour/2 to left ans right child. this will take care of the shared node also.

int main()
{
	cin >> N >> C;
//	pouring(N,0,0);
	A[0][0] = N;
	int level;
	for (int i = 0; i < 5; i++)
	{
		level = i;
		bool flag = false;
		for (int j =0; j <=i; j++)
		{
			if (A[i][j] > C)
			{
				flag = true;
				A[i+1][j]+= (A[i][j]-C)/2;
				A[i+1][j+1] +=(A[i][j]-C)/2;
			}
		}
		if (!flag)
			break;
	}

	for (int i = 0; i <= level; i++)
	{
		for (int j = 0; j <= i; j++)
			cout << A[i][j] << " ";
		cout << endl;
	}
	return 0;
}

We could do it easily by means of arrays.

class PyramidGlasses
{
	static float[] glasses;
	static int levels = 5;
	static int capacity = 5;
	static int total = 40;
	public static void main(String[] args)
	{
		createGlasses();
		fill(1, 1, total);
		for(int i=0; i<glasses.length; i++)
		{
			System.out.println(glasses[i]);
		}
	}
	public static void createGlasses()
	{
		glasses = new float[(levels*(levels+1)/2)+1];

	}
	public static void fill(int i, int j, float remaining)
	{
		if(remaining>capacity)
		{
			glasses[i] = capacity;
			remaining = remaining -  capacity;
			if (remaining>0)
			{
				int left = i+j;
				int right = i+j+1;
				j++;
				fill(left, j, remaining/2);
				fill(right, j, remaining/2);
			}
		}
		else
		{
			glasses[i] = glasses[i]+remaining;
			return;
		}
	}
}

result is
0.0
5.0
5.0
5.0
5.0
5.0
5.0
0.625
1.875
1.875
0.625
0.0
0.0
0.0
0.0
0.0

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

// Returns the amount of water in jth glass of ith row
float findWater(int i, int j, float X)
{
// A row number i has maximum i columns. So input column number must
// be less than i
if (j > i)
{
printf("Incorrect Input\n");
exit(0);
}

// There will be i*(i+1)/2 glasses till ith row (including ith row)
float glass[i * (i + 1) / 2];

// Initialize all glasses as empty
memset(glass, 0, sizeof(glass));

// Put all water in first glass
int index = 0;
glass[index] = X;

// Now let the water flow to the downward glassses till the
// amount of water X is not 0 and row number is less than or
// equal to i (given row)
for (int row = 1; row <= i && X !=0.0; ++row)
{
// Fill glasses in a given row. Number of columns in a row
// is equal to row number
for (int col = 1; col <= row; ++col, ++index)
{
// Get the water from current glass
X = glass[index];

// Keep the amount less than or equal to
// capacity in current glass
glass[index] = (X >= 1.0f) ? 1.0f : X;

// Get the remaining amount
X = (X >= 1.0f) ? (X - 1) : 0.0f;

// Distribute the remaining amount to the down two glasses
glass[index + row] += X / 2;
glass[index + row + 1] += X / 2;
}
}

// The index of jth glass in ith row will be i*(i-1)/2 + j - 1
return glass[i*(i-1)/2 + j - 1];
}


//Main program to test above function
int main()
{
int i = 2, j = 2;
float X = 2.0; // Total amount of water

printf("Amount of water in jth glass of ith row is: %f",
findWater(i, j, X));

return 0;
}

Output:

Amount of water in jth glass of ith row is: 0.500000

Time Complexity: O(i*(i+1)/2) or O(i^2)
Auxiliary Space: O(i*(i+1)/2) or O(i^2)

/***************************
			1
		  2   3
		4	5	6
	  7	  8	  9	 10
	11	12	13	14	15
	..................	
	..................
****************************/

double fillGlasses(double C, double L, int ht, int idx)
{
	// total how many glasses including the one at (h,i) position
	// upto (ht-1) height all glasses will be there i.e. (ht-1)*ht/2
	int n = (ht-1)*ht/2 + idx;
	double a[n]; // one more to use the array as indexed-1
	memset(a, 0, sizeof(a));
	
	a[1] = L; // 1st glass gets L amount of liquid
	for(int h = 1, i = 1; h < ht; h++) // iterate upto (ht-1) height
	{
		// i corresponds to the current glass
		for(int w = 1; w <= h; w++) // at h height h glasses will be there
		{
			int l = i + h; // left child glass (look at the structure above)
			int r = i + h + 1; // right child glass (by the structure)
			if(a[i] > C) // if current glass is over filled
			{
				if(l <= n) // if left child glass is within our range
					a[l] += (a[i]-C)/2;
				if(r <= n) // if child child glass is within our range
					a[r] += (a[i]-C)/2;
				a[i] = C; // current glass should be full
			}
			i++; // next glass
		}
	}
	
	return a[n];
}