Post date: Jul 18, 2013 11:15:51 AM
Problem
There are some glasses with equal volume 1 litre. The glasses kept as follows
1
2 3
4 5 6
7 8 9 10
You can put water to only top glass. If you put more than 1 litre water to 1st glass, water overflow and fill equally both 2nd and 3rd glass. Glass 5 will get water from both 2nd glass and 3rd glass and so on..
If you have X litre of water and you put that water in top glass, so tell me how much water contained by jth glass in ith row.
Example. If you will put 2 litre on top.
1st – 1 litre
2nd – 1/2 litre
3rd - 1/
*/
/*
level 0: 1
level 1: 1/2 1/2
level 2: 1/4 2/4 1/4
level 3: 1/8 3/8 3/8 1/8
level 4: 1/16 4/16 6/16 4/16 1/16
*/
Solution
/*
============================================================================
Author : James Chen
Email : a.james.chen@gmail.com
Description : Calculate how many water contained by jth glasses
Created Data : 18-07-2013
Last Modified :
============================================================================
*/
#include <iostream>
#include <iomanip>
#include <cassert>
using namespace std;
float CalcWaterInGlass(int jth, int ith, float x)
{
assert(ith >= 0);
assert(jth >= 0);
assert(jth <= ith);
int level = 0;
float* prevCol = new float[ith + 2];
float* currCol = new float[ith + 2];
for(int i = 0; i < ith + 2; ++i){
prevCol[i] = currCol[i] = 0.0f;
}
prevCol[0] = x;
for(level = 0; level < ith; ++level){
for(int i = 0; i <= level; ++i){
if(prevCol[i] > 1.0f){
currCol[i] += (prevCol[i] - 1.0f) / 2;
currCol[i + 1] += (prevCol[i] - 1.0f) / 2;
}
}
for(int i = 0; i <= level + 1; ++i){
prevCol[i] = currCol[i];
currCol[i] = 0.0f;
}
}
float retVal = (prevCol[jth] > 1.0) ? 1.0 : prevCol[jth];
delete[] prevCol;
delete[] currCol;
return retVal;
}
void DoTest(int jth, int ith, float water)
{
cout << "Total water:" << water << endl;
cout << "(" << jth << ", " << ith << ")";
cout << " = " << CalcWaterInGlass(jth, ith, water) << endl;
cout << "---------------------------------------" << endl;
}
int main(int argc, char* argv[])
{
DoTest(0, 0, 0);
DoTest(0, 0, 0.5);
DoTest(0, 0, 1.0);
DoTest(0, 0, 1.5);
DoTest(0, 1, 0.5);
DoTest(0, 1, 1);
DoTest(0, 1, 1.5);
DoTest(0, 1, 3);
DoTest(0, 1, 3.5);
DoTest(1, 1, 0.5);
DoTest(1, 1, 1);
DoTest(1, 1, 1.5);
DoTest(1, 1, 3);
DoTest(1, 1, 3.5);
DoTest(0, 2, 0.5);
DoTest(0, 2, 3.0);
DoTest(0, 2, 4.5);
DoTest(0, 2, 6);
DoTest(1, 2, 1.5);
DoTest(1, 2, 3);
DoTest(1, 2, 5);
DoTest(1, 2, 6);
DoTest(2, 2, 1.5);
DoTest(2, 2, 3);
DoTest(2, 2, 5);
DoTest(2, 2, 6);
DoTest(0, 3, 8);
DoTest(1, 3, 8);
DoTest(2, 3, 8);
DoTest(3, 3, 8);
return 0;
}
Output
Total water:0
(0, 0) = 0
---------------------------------------
Total water:0.5
(0, 0) = 0.5
---------------------------------------
Total water:1
(0, 0) = 1
---------------------------------------
Total water:1.5
(0, 0) = 1
---------------------------------------
Total water:0.5
(0, 1) = 0
---------------------------------------
Total water:1
(0, 1) = 0
---------------------------------------
Total water:1.5
(0, 1) = 0.25
---------------------------------------
Total water:3
(0, 1) = 1
---------------------------------------
Total water:3.5
(0, 1) = 1
---------------------------------------
Total water:0.5
(1, 1) = 0
---------------------------------------
Total water:1
(1, 1) = 0
---------------------------------------
Total water:1.5
(1, 1) = 0.25
---------------------------------------
Total water:3
(1, 1) = 1
---------------------------------------
Total water:3.5
(1, 1) = 1
---------------------------------------
Total water:0.5
(0, 2) = 0
---------------------------------------
Total water:3
(0, 2) = 0
---------------------------------------
Total water:4.5
(0, 2) = 0.375
---------------------------------------
Total water:6
(0, 2) = 0.75
---------------------------------------
Total water:1.5
(1, 2) = 0
---------------------------------------
Total water:3
(1, 2) = 0
---------------------------------------
Total water:5
(1, 2) = 1
---------------------------------------
Total water:6
(1, 2) = 1
---------------------------------------
Total water:1.5
(2, 2) = 0
---------------------------------------
Total water:3
(2, 2) = 0
---------------------------------------
Total water:5
(2, 2) = 0.5
---------------------------------------
Total water:6
(2, 2) = 0.75
---------------------------------------
Total water:8
(0, 3) = 0.125
---------------------------------------
Total water:8
(1, 3) = 0.875
---------------------------------------
Total water:8
(2, 3) = 0.875
---------------------------------------
Total water:8
(3, 3) = 0.125
---------------------------------------
Press any key to continue . . .