Statistics

Problem Statement for "TheRoundCityDiv1"

Problem Statement

John and Brus have found a nice horizontal plane and they built a round city somewhere on the plane. The center of the city is at coordinates (0, 0). This point is left empty. There is a house at each other lattice point that is at most r units away from the city center. That is, the lattice point (x, y) other than (0, 0) contains a house if and only if sqrt(x*x + y*y) ≤ r.

John and Brus are wondering how many houses are visible from the city center. A house is visible if and only if there are no other houses on the line segment connecting the house and the city center. (For the purpose of this definition, each house is a single point.)

You are given the int r. Return the number of houses that are visible from the city center.

Definition

Class:
TheRoundCityDiv1
Method:
find
Parameters:
int
Returns:
long
Method signature:
long find(int r)
(be sure your method is public)

Constraints

  • r will be between 1 and 1,000,000, inclusive.

Examples

  1. 1

    Returns: 4

    There are four houses in the city: at (0, 1), (0, -1), (1, 0), and (-1, 0). All four of them are visible from the city center.

  2. 2

    Returns: 8

    There are twelve houses in the city: (0, 1), (0, -1), (1, 0), (-1, 0), (1, 1), (1, -1), (-1, 1), (-1, -1), (0, 2), (0, -2), (2, 0), (-2, 0), The last four are not visible from the city center. For example, (0, 2) is not visible because (0, 1) is on the line segment from (0, 2) to the city center.

  3. 3

    Returns: 16

    There are twenty-eight houses in the city: (0, 1), (0, -1), (1, 0), (-1, 0), (0, 2), (0, -2), (2, 0), (-2, 0), (1, 1), (1, -1), (-1, 1), (-1, -1), (0, 3), (0, -3), (3, 0), (-3, 0), (1, 2), (1, -2), (-1, 2), (-1, -2), (2, 1), (2, -1), (-2, 1), (-2, -1), (2, 2), (2, -2), (-2, 2), (-2, -2). Twelve of them: (0, 2), (0, -2), (2, 0), (-2, 0), (0, 3), (0, -3), (3, 0), (-3, 0), (2, 2), (2, -2), (-2, 2), (-2, -2) are not visible from the city center.

  4. 47

    Returns: 4176

  5. 96

    Returns: 17592

  6. 75

    Returns: 10728

  7. 86

    Returns: 14120

  8. 85

    Returns: 13784

  9. 17

    Returns: 544

  10. 23

    Returns: 1000

  11. 52

    Returns: 5184

  12. 83

    Returns: 13144

  13. 64

    Returns: 7840

  14. 88

    Returns: 14784

  15. 62

    Returns: 7336

  16. 78

    Returns: 11632

  17. 97

    Returns: 17920

  18. 56

    Returns: 6000

  19. 65

    Returns: 8072

  20. 31

    Returns: 1816

  21. 99

    Returns: 18696

  22. 92

    Returns: 16168

  23. 57

    Returns: 6192

  24. 30

    Returns: 1704

  25. 96

    Returns: 17592

  26. 69

    Returns: 9088

  27. 76

    Returns: 11024

  28. 2

    Returns: 8

  29. 14

    Returns: 384

  30. 43

    Returns: 3480

  31. 31

    Returns: 1816

  32. 45

    Returns: 3856

  33. 37

    Returns: 2600

  34. 60

    Returns: 6880

  35. 33

    Returns: 2072

  36. 73

    Returns: 10136

  37. 67

    Returns: 8528

  38. 59

    Returns: 6632

  39. 94

    Returns: 16880

  40. 78

    Returns: 11632

  41. 70

    Returns: 9328

  42. 45

    Returns: 3856

  43. 70

    Returns: 9328

  44. 30

    Returns: 1704

  45. 47

    Returns: 4176

  46. 70

    Returns: 9328

  47. 100

    Returns: 19088

  48. 434396

    Returns: 360390231816

  49. 927975

    Returns: 1644651677048

  50. 267186

    Returns: 136341720616

  51. 773085

    Returns: 1141447313800

  52. 53117

    Returns: 5388505280

  53. 534723

    Returns: 546083570080

  54. 930352

    Returns: 1653087988912

  55. 416783

    Returns: 331757973904

  56. 722664

    Returns: 997411148888

  57. 887088

    Returns: 1502916270000

  58. 957762

    Returns: 1751929325728

  59. 875578

    Returns: 1464168499368

  60. 132697

    Returns: 33629745016

  61. 923695

    Returns: 1629515751088

  62. 943274

    Returns: 1699327576472

  63. 938985

    Returns: 1683909270056

  64. 999584

    Returns: 1908270648336

  65. 993416

    Returns: 1884793085376

  66. 948222

    Returns: 1717202186416

  67. 904051

    Returns: 1560943695016

  68. 988482

    Returns: 1866117166216

  69. 927063

    Returns: 1641420585008

  70. 970487

    Returns: 1798791477896

  71. 965461

    Returns: 1780208408008

  72. 962777

    Returns: 1770324132144

  73. 997596

    Returns: 1900687747992

  74. 1000000

    Returns: 1909859313984

  75. 999999

    Returns: 1909855494720

This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2024, TopCoder, Inc. All rights reserved.
This problem was used for: