TriangleXor

Problem Statement

You are given an int W. There is a rectangle in the XY-plane with corners at (0, 0), (0, 1), (W, 0), and (W, 1). Let T[x] be the triangle with vertices at (0, 1), (W, 1) and (x, 0). (All points that lie inside the triangle are a part of T[x] as well.)

The objective in this problem is to calculate the area of the region (T[0] xor T[1] xor ... xor T[W]). (See Notes for a formal definition.) The figures below show the region (T[0] xor T[1] xor ... xor T[W]) for W=1,2,3,4,5,6.

Return the integer part of the area of the region.

Notes

• For sets of points A and B in the XY-plane, the set (A xor B) is defined as the set of all points that lie in exactly one of the sets A and B (i.e., points that belong to the union of A and B but don't belong to their intersection).
• If the exact area is A, the correct return value is floor(A), not round(A). In words: you should return the largest integer that is less than or equal to the exact area.
• The format of the return value was chosen to help you in case of small precision errors. The constraints guarantee that computing the correct area with absolute error less than 0.01 is sufficient to determine the correct return value. The author's solution is significantly more precise than that.

Constraints

• W will be between 1 and 70,000, inclusive.
• The difference between the exact area of the region and the nearest integer will be greater than 0.01.