{"problem":{"name":"H. Packing circles","description":{"content":"You are given rectangle dimensions (W - width, H - height) and circle diameter D. How many circles can you fit inside that rectangle? Circles must be placed in rows parallel to the bottom. Each row mu","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":2000,"memory_limit":65536},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF10074H"},"statements":[{"statement_type":"Markdown","content":"You are given rectangle dimensions (W - width, H - height) and circle diameter D. How many circles can you fit inside that rectangle? Circles must be placed in rows parallel to the bottom. Each row must have the same amount of circles. Each pair of consecutive rows must have the same distance between them. A row is defined by a horizontal line. Circle belongs to a row if its center point lies on that line. \n\nA single line contains 3 integers W, H and D. (1 ≤ W, H, D ≤ 106)\n\nA single integer - the maximal amount of circles that can fit inside the rectangle with given restrictions.\n\n## Input\n\nA single line contains 3 integers W, H and D. (1 ≤ W, H, D ≤ 106)\n\n## Output\n\nA single integer - the maximal amount of circles that can fit inside the rectangle with given restrictions.\n\n[samples]","is_translate":false,"language":"English"},{"statement_type":"Markdown","content":"**Definitions**  \nLet $ W, H, D \\in \\mathbb{Z}^+ $ denote the width, height, and diameter of the circle, respectively.\n\n**Constraints**  \n$ 1 \\leq W, H, D \\leq 10^6 $\n\n**Objective**  \nMaximize the number of circles of diameter $ D $ that can be placed in a rectangle of dimensions $ W \\times H $, such that:  \n- Circles are arranged in horizontal rows parallel to the bottom edge.  \n- Each row contains the same number of circles.  \n- Centers of circles in consecutive rows are separated vertically by a fixed distance $ h \\geq D $ (to avoid overlap).  \n- Each circle’s center lies on its row’s horizontal line.  \n- All circles lie entirely within the rectangle.  \n\nLet $ n $ be the number of circles per row:  \n$ n = \\left\\lfloor \\frac{W}{D} \\right\\rfloor $\n\nLet $ m $ be the number of rows.  \nThe vertical spacing between row centers must be at least $ D $. The minimal vertical spacing to avoid overlap (in a hexagonal packing) is $ \\frac{\\sqrt{3}}{2} D $, but the problem requires **equal distance between consecutive rows** and **same number per row**, implying **rectangular (grid) packing** — thus vertical spacing is exactly $ D $.  \n\nTherefore:  \n$ m = \\left\\lfloor \\frac{H}{D} \\right\\rfloor $\n\nTotal circles:  \n$$\nn \\cdot m = \\left\\lfloor \\frac{W}{D} \\right\\rfloor \\cdot \\left\\lfloor \\frac{H}{D} \\right\\rfloor\n$$\n\n**Answer**  \n$$\n\\left\\lfloor \\frac{W}{D} \\right\\rfloor \\cdot \\left\\lfloor \\frac{H}{D} \\right\\rfloor\n$$","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF10074H","tags":[],"sample_group":[],"created_at":"2026-03-03 11:00:39"}}