Statistics

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.

Definition

Class:

TriangleXor

Method:

theArea

Parameters:

int

Returns:

int

Method signature:

int theArea(int W)

(be sure your method is public)

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.

Examples

1. 1

   Returns: 0

   The exact area is 0.5.

2. 2

   Returns: 1

   The area is approximately 1.33333.

3. 3

   Returns: 1

   The exact area is 1.35.

4. 4

   Returns: 2

   The area is approximately 2.62857. Note that the correct answer is 2, not 3.

5. 5

   Returns: 2

   The area is approximately 2.13294.

6. 12345

   Returns: 4629

7. 6

   Returns: 3

8. 7

   Returns: 2

9. 8

   Returns: 5

10. 9

    Returns: 3

11. 10

    Returns: 6

12. 11

    Returns: 4

13. 12

    Returns: 7

14. 13

    Returns: 5

15. 126

    Returns: 78

16. 129

    Returns: 48

17. 247

    Returns: 92

18. 128

    Returns: 80

19. 192

    Returns: 120

20. 165

    Returns: 62

21. 181

    Returns: 68

22. 109

    Returns: 41

23. 239

    Returns: 89

24. 176

    Returns: 110

25. 62678

    Returns: 39173

26. 52183

    Returns: 19568

27. 54773

    Returns: 20540

28. 50991

    Returns: 19121

29. 61545

    Returns: 23079

30. 67741

    Returns: 25403

31. 55859

    Returns: 20947

32. 68053

    Returns: 25520

33. 57781

    Returns: 21668

34. 50892

    Returns: 31807

35. 70000

    Returns: 43750

36. 69999

    Returns: 26249

37. 69998

    Returns: 43748

38. 69997

    Returns: 26249

39. 69996

    Returns: 43747

40. 69995

    Returns: 26248

41. 69994

    Returns: 43746

42. 69993

    Returns: 26247

43. 9934

    Returns: 6208

44. 27635

    Returns: 10363

45. 37533

    Returns: 14075

46. 66823

    Returns: 25058

47. 46636

    Returns: 29147

48. 59791

    Returns: 22421

49. 20256

    Returns: 12660

50. 11160

    Returns: 6975

51. 44448

    Returns: 27780

52. 48882

    Returns: 30551

53. 38098

    Returns: 23811

54. 17056

    Returns: 10660

55. 63804

    Returns: 39877

56. 66666

    Returns: 41666

57. 29997

    Returns: 11249

58. 69977

    Returns: 26241

59. 1000

    Returns: 625

60. 56789

    Returns: 21296