UVa 913

From Algorithmist
Jump to: navigation, search

913 - Joana and the Odd Numbers[edit]

Summary[edit]

The only problem here is to calculate the last number of the n-th line. Bruteforce won't do it

Explanation[edit]

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 _{{i=1}}^{{n-1}}2\cdot i-1+\left(2n-1\right)=\sum _{{i=1}}^{{n}}2\cdot i-1=2\cdot \sum _{{i=1}}^{{n}}n-\sum _{{i=1}}^{{n}}1=2\cdot {\frac  {n\cdot \left(n+1\right)}{2}}-n=n\cdot (n+1)-n

The last number of the n-th is then: last=2\cdot \left(n\cdot (n+1)-n\right)-1

Now you can simply calculte the sum: sum=last+last-2+last-4=3\cdot last-6

Gotcha's[edit]

  • You need to use long long int to do the calculations

Solutions[edit]