in SPOJ

SPOJ: 8060. Cookies Piles

The kids in my son’s kindergarten made Christmas cookies with their teacher, and piled them up in columns. They then arranged the columns so that the tops of the columns, going from shortest to tallest, were in a nice straight ramp. The cookies were all of uniform size. Given that there were A cookies in the shortest pile, that the difference in height between any two adjacent piles was D cookies, and that there were N piles, can you write a program to figure out how many cookies there were in total?

Problem: Sphere Online Judge (SPOJ) – Problem AMR10F

Solution: This is quite a nice and simple problem. The easiest solution is just to write a loop to calculate the amount of cookies. If you think one step further you can write a general formula for calculating this.
Let’s imagine three piles of cookies.

At the rightmost there are A cookies. The middle one got A + D cookies and the leftmost got A + 2D cookies. If we generalize this we get: \text{allCookies} = (A + 2 * D) + (A + 1 * D) + (A + 0 * D) which can be written as \sum_{i=0}^{N-1} (A + iD).
And thus can be simplified:

$latex \sum_{i=0}^{N-1} A + D \sum_{i=0}^{N-1} i = NA + D\frac{(N-1)N}{2}.

Write a Comment

Comment