HomeVolumesContestsSectionsForumsUsersPrintHelpAbout

Sections > Recursion > problem:


50724 - Number of Circles

Guest
• Discussion of problem (2)

Section problems

• 50723 - Tribonacci
• 50909 - Gold Coins
• 50415 - The Scientist
• 50385 - The 3n + 1 problem
• 50911 - Symmetric Array
• 50381 - Sum of the numbers
• 51081 - Fish Pond I
• 50935 - Max Discount
• 50724 - Number of Circles
• 50729 - Max number in 2D array
• 50928 - War Of Battleships
• 50577 - Perfect Numbers and Perfec...
• 50725 - Fibonacci Series
• 50370 - Number of rectangles in a ...
• 50376 - Sequences
• 50421 - Repairing road segments
• 50389 - Reverse an Array

Feedback

If you notice incorrect translations in Contester, please let author know.

Time limit 2000/4000/4000/4000 ms. Memory limit 65000/65000/65000/65000 Kb.
Question by Ibrahim Mesecan.

Number of circles

You are asked to draw one circle in the given coordinate. Then, you draw four other circles with the half radius of previous first circle. And then, you continue drawing circles around every circle with the half of the previous radius as far as integer radius is greater than 0 and the center coordinates of the current circle are in border (between 1 and field size).

  • When you draw a circle to the left of any circle, you draw 3 new circles around it: Left, Up and Down, if they are in border and their new radius is greater than zero.
  • When drawing a circle above any circle, you draw 3 other circles around: Up, Right and Left, if they comply the conditions
  • etc.

Question: Write a program that reads initial circle coordinate, its radius and the size of the field. Then your program will calculate and show the number of circles. Notes:

  • Bottom left corner is (0,0)
  • It's guarantied that the first circle is in border.
  • Assume that all radius and coordinates are integers

Input specification
You will be given 4 integers x, y, r, and (s) where x and y are the center coordinate and r is the radius of the initial circle. And s is the size of square field. 1 ≤ s ≤ 10,000; 1 ≤ r ≤ 10,000. Any circle is assumed to be in the field if its center is between 1 and s.

Output specification
Show one integer, the number of circles that can be drawn with the given conditions.

Sample Input  
3 4 4 10
Sample Output  
6

Для отправки решений необходимо выполнить вход.

www.contester.ru