Codeforces: B. Jumping Jack

The problem is from codeforces, http://www.codeforces.com/problemset/problem/11/B

Jack is originally standing at zero point. He can walk left or right at an increasing step. We suppose Jack always walks towards a direction. Therefore, with n steps, he can reach

We denote the . Replacing with , so Jack can reach a new location of , similarly , … can also be reached. An exhaustive search will be timed out in the test cases. The negative tests can be mirrored to the positive ones because the tests are symmetrical.

Therefore, the Python solution is given below.

#!/usr/bin/env python
# helloacm.com
n = int(raw_input())

def sum(x):
    return x * (x + 1) / 2

if n < 0:
    n = -n

ans = 0
while 1:
    s = sum(ans)
    if (s - n) % 2 > 0 or (s < n):
        ans += 1
    else:
        break

print ans

The sum() can also be defined as a lambda function in python as follows.

sum = lambda x: x * (x + 1) / 2

–EOF (The Ultimate Computing & Technology Blog) —