B. Segments

Codeforces

IDCF909B

Time2000ms

Memory256MB

Difficulty—

constructive algorithmsmath

English · Original

Chinese · Translation

Formal · Original

You are given an integer _N_. Consider all possible segments on the coordinate axis with endpoints at integer points with coordinates between 0 and _N_, inclusive; there will be of them. You want to draw these segments in several layers so that in each layer the segments don't overlap (they might touch at the endpoints though). You **can not** move the segments to a different location on the coordinate axis. Find the minimal number of layers you have to use for the given _N_. ## Input The only input line contains a single integer _N_ (1 ≤ _N_ ≤ 100). ## Output Output a single integer - the minimal number of layers required to draw the segments for the given _N_. [samples] ## Note As an example, here are the segments and their optimal arrangement into layers for _N_ = 4. <center>![image](https://espresso.codeforces.com/8a475108c50ca3e7a56a047302228224fc3fa969.png)</center>

[{"iden":"statement","content":"给定一个整数 $N$。考虑所有在坐标轴上端点为整数点、且坐标介于 0 和 $N$ 之间（含端点）的线段；共有 $\\frac{(N+1)(N+2)}{2}$ 条这样的线段。\n\n你希望将这些线段绘制在若干层中，使得每层中的线段互不重叠（但端点可以接触）。你*不能*将线段移动到坐标轴上的其他位置。\n\n求出绘制这些线段所需的最少层数。\n\n输入仅一行，包含一个整数 $N$（$1 ≤ N ≤ 100$）。\n\n输出一个整数——为给定 $N$ 绘制所有线段所需的最少层数。\n\n例如，下图展示了当 $N = 4$ 时的线段及其在各层中的最优排列方式。\n\n"},{"iden":"input","content":"输入仅一行，包含一个整数 $N$（$1 ≤ N ≤ 100$）。"},{"iden":"output","content":"输出一个整数——为给定 $N$ 绘制所有线段所需的最少层数。"},{"iden":"examples","content":"输入2输出2输入3输出4输入4输出6"},{"iden":"note","content":"例如，下图展示了当 $N = 4$ 时的线段及其在各层中的最优排列方式。 "}]}

**Definitions** Let $ N \in \mathbb{Z} $, with $ 1 \leq N \leq 100 $. Let $ \mathcal{S} = \{ [i, j] \mid 0 \leq i \leq j \leq N \} $ be the set of all integer-coordinate segments on $[0, N]$. **Constraints** - $ |\mathcal{S}| = \binom{N+1}{2} + (N+1) = \frac{(N+1)(N+2)}{2} $ **Objective** Find the minimum number of layers $ L $ such that $ \mathcal{S} $ can be partitioned into $ L $ subsets, where in each subset, no two segments overlap (i.e., for any two segments $[a,b], [c,d]$ in the same subset, either $ b \leq c $ or $ d \leq a $). **Known Result** The minimal number of layers equals the maximum number of segments that share a common interior point. This maximum is achieved at the midpoint, and equals $ \left\lfloor \frac{N}{2} \right\rfloor + 1 $. Thus: $$ L = \left\lfloor \frac{N}{2} \right\rfloor + 1 $$

Samples

Input #1

Output #1

Input #2

Output #2

Input #3

Output #3

API Response (JSON)

{
  "problem": {
    "name": "B. Segments",
    "description": {
      "content": "You are given an integer _N_. Consider all possible segments on the coordinate axis with endpoints at integer points with coordinates between 0 and _N_, inclusive; there will be of them. You want to ",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF909B"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "You are given an integer _N_. Consider all possible segments on the coordinate axis with endpoints at integer points with coordinates between 0 and _N_, inclusive; there will be of them.\n\nYou want to ...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "[{\"iden\":\"statement\",\"content\":\"给定一个整数 $N$。考虑所有在坐标轴上端点为整数点、且坐标介于 0 和 $N$ 之间（含端点）的线段；共有 $\\\\frac{(N+1)(N+2)}{2}$ 条这样的线段。\\n\\n你希望将这些线段绘制在若干层中，使得每层中的线段互不重叠（但端点可以接触）。你*不能*将线段移动到坐标轴上的其他位置。\\n\\n求出绘制这些线段所需的最少层数...",
      "is_translate": true,
      "language": "Chinese"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ N \\in \\mathbb{Z} $, with $ 1 \\leq N \\leq 100 $.  \nLet $ \\mathcal{S} = \\{ [i, j] \\mid 0 \\leq i \\leq j \\leq N \\} $ be the set of all integer-coordinate segments on $[0, N]$.\n\n**C...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments