I. Innovative Business

Codeforces

IDCF10068I

Time2000ms

Memory256MB

Difficulty—

English · Original

Formal · Original

Chip 'n' Dale have started a new business in the forest: they produce tiles of fixed rectangular size and pave roads with them. Road paving rules are the following. Starting from one corner of the rectangular road tiles are paved side-by-side without gaps or overlaps. Tiles can be cut into pieces to be used to pave the road if and only if the whole tile doesn't fit. Each tile contains a pattern with parallel lines that must be retained on the paved road. This makes their orientation significant: any tile or its piece can not be rotated. All tile connection lines are straight, parallel to one of the road edges and either perpendicular or parallel to each other. Chip 'n' Dale always pave the road so that each edge of a tile is adjacent to not more than one other tile, and they always pave the road with the least possible amount of tile pieces on the road. Given the size of the road and the size of one tile please help Chip 'n' Dale determine the number of tiles they need to produce to fully pave the road. On the first line of input integers Widthroad and Lengthroad (1 ≤ Widthroad, Lengthroad ≤ 10 000) are given — the width and the length of the road respectively. On the second line of input integers Widthtile and Lengthtile (1 ≤ Widthtile ≤ Widthroad, 1 ≤ Lengthtile ≤ Lengthroad) are given — the width and the length of the tile respectively. The first line of the output should contain a single integer number N — the minimal number of whole tiles needed to fully pave the road according to Chip 'n' Dale road paving rules. ## Input On the first line of input integers Widthroad and Lengthroad (1 ≤ Widthroad, Lengthroad ≤ 10 000) are given — the width and the length of the road respectively.On the second line of input integers Widthtile and Lengthtile (1 ≤ Widthtile ≤ Widthroad, 1 ≤ Lengthtile ≤ Lengthroad) are given — the width and the length of the tile respectively. ## Output The first line of the output should contain a single integer number N — the minimal number of whole tiles needed to fully pave the road according to Chip 'n' Dale road paving rules. [samples]

**Definitions** Let $ W_r, L_r \in \mathbb{Z}^+ $ denote the width and length of the road. Let $ W_t, L_t \in \mathbb{Z}^+ $ denote the width and length of the tile. **Constraints** 1. $ 1 \leq W_r, L_r \leq 10{,}000 $ 2. $ 1 \leq W_t \leq W_r $ 3. $ 1 \leq L_t \leq L_r $ **Objective** Compute the minimal number of whole tiles $ N $ required to cover the rectangular road of dimensions $ W_r \times L_r $ using non-rotated tiles of dimensions $ W_t \times L_t $, allowing only straight cuts parallel to tile edges, with the constraint that each tile piece must be a rectangular subpiece of an original tile and no tile may be rotated. Assume tiles are placed in axis-aligned orientation (i.e., tile width aligns with road width, tile length with road length). Then: $$ N = \left\lceil \frac{W_r}{W_t} \right\rceil \cdot \left\lceil \frac{L_r}{L_t} \right\rceil $$

API Response (JSON)

{
  "problem": {
    "name": "I. Innovative Business",
    "description": {
      "content": "Chip 'n' Dale have started a new business in the forest: they produce tiles of fixed rectangular size and pave roads with them. Road paving rules are the following. Starting from one corner of the re",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF10068I"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "Chip 'n' Dale have started a new business in the forest: they produce tiles of fixed rectangular size and pave roads with them.\n\nRoad paving rules are the following. Starting from one corner of the re...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ W_r, L_r \\in \\mathbb{Z}^+ $ denote the width and length of the road.  \nLet $ W_t, L_t \\in \\mathbb{Z}^+ $ denote the width and length of the tile.  \n\n**Constraints**  \n1. $ 1 \\l...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments