[信息与未来 2015] 拴奶牛

Luogu

IDLGB3881

Time1000ms

Memory128MB

DifficultyP2

2015二分江苏信息与未来

有 $n$ 头奶牛，有 $k$ 个木桩，每个木桩有一个位置，一个木桩上只能拴一头奶牛。由于奶牛好斗，所以在拴奶牛的时候，要求距离最近的奶牛的距离尽可能大。例如 $n=4,k=6$，木桩的位置为 $0,3,4,7,8,9$，此时为下图。 $$ \begin{aligned} \underline{\text{\qquad O\quad l\quad l\quad O\quad O\quad l\quad l\quad O\quad O\quad O\qquad}}\\ \text{\qquad 0\quad\ \quad\ \ \quad 3\ \quad 4\quad\quad\quad\quad 7\quad\ 8\quad\ 9\qquad} \end{aligned} $$ 有许多种拴牛方案，例如： - $0,3,4,9$：此时最近距离为 $1$（$3,4$ 之间）； - $0,3,7,9$：此时最近距离为 $2$。 ## Input 三个整数 $n,k,p_1$，其中 $p_1$ 为第 $1$ 个木桩的位置，其他木桩 $p_i(i\ge2)$ 的位置由下面公式给出： $p_i = p_{i-1} + ((p_{i-1}\times2357+137) \bmod 10)+1$。 ## Output 一个整数，即奶牛间最近距离的最大值。 [samples] ## Note $1\le n\le k\le10^6,0\le p_1\le100$。

Samples

Input #1

25 70 99

Output #1

API Response (JSON)

{
  "problem": {
    "name": "[信息与未来 2015] 拴奶牛",
    "description": {
      "content": "有 $n$ 头奶牛，有 $k$ 个木桩，每个木桩有一个位置，一个木桩上只能拴一头奶牛。由于奶牛好斗，所以在拴奶牛的时候，要求距离最近的奶牛的距离尽可能大。 例如 $n=4,k=6$，木桩的位置为 $0,3,4,7,8,9$，此时为下图。 $$ \\begin{aligned} \\underline{\\text{\\qquad O\\quad l\\quad l\\quad O\\quad O\\quad l\\",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 131072
    },
    "difficulty": {
      "LuoguStyle": "P2"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGB3881"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "有 $n$ 头奶牛，有 $k$ 个木桩，每个木桩有一个位置，一个木桩上只能拴一头奶牛。由于奶牛好斗，所以在拴奶牛的时候，要求距离最近的奶牛的距离尽可能大。\n\n例如 $n=4,k=6$，木桩的位置为 $0,3,4,7,8,9$，此时为下图。\n$$\n\\begin{aligned}\n\\underline{\\text{\\qquad O\\quad l\\quad l\\quad O\\quad O\\quad l\\...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments