CCC '08 S2 - Pennies in the Ring

View as PDF

Submit solution

Points: 5
Time limit: 1.0s
Memory limit: 64M

Problem type
Allowed languages
Ada, Assembly, Awk, Brain****, C, C#, C++, COBOL, CommonLisp, D, Dart, F#, Forth, Fortran, Go, Groovy, Haskell, Intercal, Java, JS, Kotlin, Lisp, Lua, Nim, ObjC, OCaml, Octave, Pascal, Perl, PHP, Pike, Prolog, Python, Racket, Ruby, Rust, Scala, Scheme, Sed, Swift, TCL, Text, Turing, VB, Zig
Canadian Computing Competition: 2008 Stage 1, Senior 2

The game "Pennies in the Ring" is often played by bored computer programmers who have gotten tired of playing solitare. The objective is to see how many pennies can be put into a circle. The circle is drawn on a grid, with its center at the coordinate (0, 0). A single penny is placed on every integer grid coordinate (e.g., (1, 1), (1, 2), etc.) that lies within or on the circle. It's not a very exciting game, but it's very good for wasting time. Your goal is to calculate how many pennies are needed for a circle with a given radius.

Input

The input is a sequence of positive integer values, one per line, where each integer is the radius of a circle. You can assume the radius will be less than or equal to 25\,000. The last integer will be indicated by 0. You may assume that the grid is large enough for two pennies to be on adjacent integer coordinates and not touch.

Output

You are to output, each on its own line, the number of pennies needed for each circle. You do not need to output 0 for the last 0. You may assume that the number of possible pennies is less than 2 billion (which is only $20 million dollars: computer scientists have lots of money).

Sample Input

2
3
4
0

Output for Sample Input

13
29
49

Comments


  • 2
    theMang  commented on Sept. 1, 2020, 1:15 p.m.

    i keep getting TLE for the last case


  • -4
    slowmomoe  commented on Feb. 12, 2020, 1:00 a.m. edited

    Is this the equation? Is this the equation? Used a system of 4 equations and I have no idea if I made any mistakes throughout the process.


  • 1
    HARRIBO  commented on Aug. 23, 2019, 12:24 a.m.

    Can someone tell me what's wrong with my program


    • 3
      magicalsoup  commented on Aug. 23, 2019, 10:33 a.m.

      Try this case

      1
      2
      3
      0

      The correct output should be

      5
      13
      29

      • 1
        HARRIBO  commented on Aug. 23, 2019, 6:24 p.m.

        Are you sure about that? Cause a circle with radius 1 is 3.14. And if you are rounding up it should be four??


        • 7
          Kirito  commented on Aug. 23, 2019, 7:20 p.m. edit 3

          A grid

          Observe that there are 5 lattice points within the circle.


  • 3
    dawangk  commented on June 2, 2018, 10:04 p.m.

    TLE for last two cases


    • 10
      DarthVader336  commented on June 12, 2018, 7:12 p.m.

      This can be done in O(n) time.


  • 4
    STA  commented on Nov. 13, 2014, 1:37 p.m.

    Why is there a fourth line in the output? Shouldn't there only be three lines of output in this particular sample?


    • 5
      FatalEagle  commented on Nov. 14, 2014, 12:22 p.m.

      Sorry about that. The page number from the pdf was copied into the output by accident. It has been fixed.