H. Packing circles

Codeforces

IDCF10074H

Time2000ms

Memory64MB

Difficulty—

English · Original

Formal · Original

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. A single line contains 3 integers W, H and D. (1 ≤ W, H, D ≤ 106) A single integer - the maximal amount of circles that can fit inside the rectangle with given restrictions. ## Input A single line contains 3 integers W, H and D. (1 ≤ W, H, D ≤ 106) ## Output A single integer - the maximal amount of circles that can fit inside the rectangle with given restrictions. [samples]

**Definitions** Let $ W, H, D \in \mathbb{Z}^+ $ denote the width, height, and diameter of the circle, respectively. **Constraints** $ 1 \leq W, H, D \leq 10^6 $ **Objective** Maximize the number of circles of diameter $ D $ that can be placed in a rectangle of dimensions $ W \times H $, such that: - Circles are arranged in horizontal rows parallel to the bottom edge. - Each row contains the same number of circles. - Centers of circles in consecutive rows are separated vertically by a fixed distance $ h \geq D $ (to avoid overlap). - Each circle’s center lies on its row’s horizontal line. - All circles lie entirely within the rectangle. Let $ n $ be the number of circles per row: $ n = \left\lfloor \frac{W}{D} \right\rfloor $ Let $ m $ be the number of rows. The 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 $. Therefore: $ m = \left\lfloor \frac{H}{D} \right\rfloor $ Total circles: $$ n \cdot m = \left\lfloor \frac{W}{D} \right\rfloor \cdot \left\lfloor \frac{H}{D} \right\rfloor $$ **Answer** $$ \left\lfloor \frac{W}{D} \right\rfloor \cdot \left\lfloor \frac{H}{D} \right\rfloor $$

API Response (JSON)

{
  "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 mu...",
      "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 num...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments