Codeforces: 268B. Buttons

The problem is from codeforces: http://www.codeforces.com/contest/268/problem/B

This is clearly a math counting problem. In easy description, the problem can be described as: how many numbers are there in this pattern,

Looking too complex? Actually not at all, we can see the first few items.

1  // total 1
1, 2, 1  // total 3
1, 2, 3, 1, 3, 2, 1  // total 7
1, 2, 3, 4, 1, 4, 2, 4, 3, 1, 4, 3, 2, 1 // total 14
...

We can simulate the process and count the answer, of course,

(1*1-0)=1
(1*2-0)+(2*1-1)=3
(1*3-0)+(2*2-1)+(3*1-2)=7
(1*4-0)+(2*3-1)+(3*2-2)+(4*1-3)=14

Well, I think you got the pattern. The following Python code gives the answer.

#!/usr/bin/env python
n = int(raw_input())
s = 0
for i in xrange(n):
    s += (i + 1) * (n - i) - i
print s

The above loop can be summed to the equation: . This is even shorter and of course, more efficient.

#!/usr/bin/env python
n = int(raw_input())
print (n * n + 5) * n / 6

–EOF (The Ultimate Computing & Technology Blog) —