B. Lazy Security Guard

Codeforces

IDCF859B

Time2000ms

Memory256MB

Difficulty—

brute forcegeometrymath

English · Original

Chinese · Translation

Formal · Original

Your security guard friend recently got a new job at a new security company. The company requires him to patrol an area of the city encompassing exactly _N_ city blocks, but they let him choose which blocks. That is, your friend must walk the perimeter of a region whose area is exactly _N_ blocks. Your friend is quite lazy and would like your help to find the shortest possible route that meets the requirements. The city is laid out in a square grid pattern, and is large enough that for the sake of the problem it can be considered infinite. ## Input Input will consist of a single integer _N_ (1 ≤ _N_ ≤ 106), the number of city blocks that must be enclosed by the route. ## Output Print the minimum perimeter that can be achieved. [samples] ## Note Here are some possible shapes for the examples: ![image](https://espresso.codeforces.com/e11bef2cf82b55dd583cfc97d12b5aee5e483a65.png)

你的安保朋友最近在一家新的安保公司找到了一份新工作。该公司要求他巡逻一个恰好包含 #cf_span[N] 个街区的区域，但允许他自行选择哪些街区。也就是说，你的朋友必须沿着一个面积恰好为 #cf_span[N] 个街区的区域的边界行走。这座城市采用正方形网格布局，且规模足够大，可以视为无限大。输入为一个整数 #cf_span[N] (#cf_span[1 ≤ N ≤ 106])，表示路线必须围住的街区数量。请输出能达到的最小周长。以下是示例中可能的形状： ## Input 输入为一个整数 #cf_span[N] (#cf_span[1 ≤ N ≤ 106])，表示路线必须围住的街区数量。 ## Output 请输出能达到的最小周长。 [samples] ## Note 以下是示例中可能的形状：

Given: - $ N \in \mathbb{Z}^+ $, $ 1 \leq N \leq 10^6 $, the required enclosed area in square blocks. Objective: Minimize the perimeter $ P $ of a polyomino (connected region on the square grid) of area $ N $, where the perimeter is the total length of the boundary between the enclosed region and the exterior. Formally: Find $$ \min \left\{ P(A) \,\middle|\, A \subseteq \mathbb{Z}^2 \text{ is a connected set of } N \text{ unit squares} \right\} $$ where $ P(A) $ denotes the perimeter of the region $ A $, defined as the number of unit edges on the grid that separate squares in $ A $ from squares not in $ A $. **Known Result:** The minimal perimeter is achieved when the shape is as close to a square as possible. Let: - $ s = \lfloor \sqrt{N} \rfloor $ - $ r = N - s^2 $ (remainder) Then: $$ P_{\min} = \begin{cases} 4s & \text{if } r = 0 \\ 2s + 2\lceil \frac{N}{s} \rceil & \text{if } r > 0 \end{cases} $$ Alternatively, more directly: Let $ a = \lfloor \sqrt{N} \rfloor $, $ b = \lceil \frac{N}{a} \rceil $. Then: $$ P_{\min} = 2(a + b) $$ **Final Formal Statement:** Let $ a = \lfloor \sqrt{N} \rfloor $, $ b = \left\lceil \frac{N}{a} \right\rceil $. Then the minimal perimeter is: $$ \boxed{2(a + b)} $$

Samples

Input #1

Output #1

Input #2

Output #2

Input #3

Output #3

API Response (JSON)

{
  "problem": {
    "name": "B. Lazy Security Guard",
    "description": {
      "content": "Your security guard friend recently got a new job at a new security company. The company requires him to patrol an area of the city encompassing exactly _N_ city blocks, but they let him choose which ",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF859B"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "Your security guard friend recently got a new job at a new security company. The company requires him to patrol an area of the city encompassing exactly _N_ city blocks, but they let him choose which ...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "你的安保朋友最近在一家新的安保公司找到了一份新工作。该公司要求他巡逻一个恰好包含 #cf_span[N] 个街区的区域，但允许他自行选择哪些街区。也就是说，你的朋友必须沿着一个面积恰好为 #cf_span[N] 个街区的区域的边界行走。这座城市采用正方形网格布局，且规模足够大，可以视为无限大。\n\n输入为一个整数 #cf_span[N] (#cf_span[1 ≤ N ≤ 106])，表示路线必须围...",
      "is_translate": true,
      "language": "Chinese"
    },
    {
      "statement_type": "Markdown",
      "content": "Given:  \n- $ N \\in \\mathbb{Z}^+ $, $ 1 \\leq N \\leq 10^6 $, the required enclosed area in square blocks.\n\nObjective:  \nMinimize the perimeter $ P $ of a polyomino (connected region on the square grid) ...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments