799.champagne-tower.md

799. Champagne Tower

Simulation

The idea is to simulate. Every cup will be full, the current pour will decrease by one (current - 1) and pour the rest to the next cup. The amount of pour the next cup is (current - 1) / 2.

The index:

// The real shape of the tower
    0
  0, 1
 0, 1, 2
0, 1, 2, 3
...

// The index of the array from above
0
0, 1
0, 1, 2
0, 1, 2, 3

So A[i] will pour (A[i] - 1) / 2 to the next coupe A[i] and A[i + 1].

fun champagneTower(poured: Int, queryRow: Int, queryGlass: Int): Double {
    // The max row is 100.
    val a = Array(101) { DoubleArray(101) }
    a[0][0] = poured.toDouble()
    for (r in 0..queryRow) {
        for (c in 0..r) {
            val flow = (a[r][c] - 1.0) / 2.0
            if (flow > 0) {
                a[r + 1][c] += flow
                a[r + 1][c + 1] += flow
            }
        }
    }
    return minOf(1.0, a[queryRow][queryGlass])
}