CupPyramid.cpp

/*
http://www.careercup.com/question?id=9820788
there is a pyramid with 1 cup at level , 2 at level 2 , 3 at level 3 and so on.. 
It looks something like this 
1 
2 3 
4 5 6 
every cup has capacity C. you pour L liters of water from top . when cup 1 gets filled , it overflows to cup 2,3 equally, and when they get filled , Cup 4 and 6 get water only from 2 and 3 resp but 5 gets water from both the cups and so on. 
Now given C and M .Find the amount of water in ith cup.

Solved it with O(k). 
The idea is simple. Pour L into coup 1. Divide into its children if overflows. Do this for subsequent elements, until find k. 
The biggest problem is to find the children. The first child of a coup is the same of last if height does not change. The second one is first + 1. 
For the given example, children would found in the the following order (se how children repeats when height repeats (kth is one based!):
*/
#include <vector>
#include <iostream>
using namespace std;

double remainingWater(double c, int k) {
    int i = 1;
    vector<double> vec(k * 2 + 2);
    vec[1] = c;
    int height = 1;
    int count = 0;
    while (i <= k) {
        double r = 0;
        if (vec[i] > i) {
            r = vec[i] - i;
            vec[i] = i;
            
        }

        vec[i+height] += r / 2;
        vec[i+height+1] += r / 2;
        count++;
        
        if (count == height) {
            count = 0;
            height++;
        }
        i++;
    }
    return vec[k];
}

int main() {
    cout << remainingWater(10, 1) << endl; // 1
    cout << remainingWater(10, 2) << endl; // 2
    cout << remainingWater(10, 3) << endl; // 3
    cout << remainingWater(10, 4) << endl; // 1.25
    cout << remainingWater(10, 5) << endl; // 2
    cout << remainingWater(10, 6) << endl; // 0.75
    cout << remainingWater(10, 7) << endl; // 0
    system("pause");
}