UVa 913

From Algorithmist

[edit] 913 - Joana and the Odd Numbers

http://acm.uva.es/p/v9/913.html

[edit] Summary

The only problem here is to calculate the last number of the n-th line. Bruteforce won´t do it, so we need a little thinking :-)

[edit] Explanation

First you can calculate the number of numbers per line. That is $2 \cdot n - 1$

Now you know how many numbers you have in one line. To get the last number of the n-th line, you need to know how many numbers there were before that line + the number of numbers in that line. So you can simply sum that up $\sum^{n-1}_{i=1} 2 \cdot i - 1 + \left(2n - 1\right) = \sum^{n}_{i=1} 2 \cdot i-1 = 2\cdot \sum^{n}_{i=1}n - \sum^{n}_{i=1} 1 = 2 \cdot \frac{n \cdot \left(n+1\right)}{2} - n = n \cdot (n +1) -n$