[USACO24OPEN] Activating Robots P

Luogu

IDLGP10285

Time2000ms

Memory256MB

DifficultyP6

二分USACO2024状压 DP

You and a single robot are initially at point $0$ on a circle with perimeter $L$ ($1 \le L \le 10^9$). You can move either counterclockwise or clockwise along the circle at $1$ unit per second. All movement in this problem is continuous. Your goal is to place exactly $R-1$ robots such that at the end, every two consecutive robots are spaced $L/R$ away from each other ($2\le R\le 20$, $R$ divides $L$). There are $N$ ($1\le N\le 10^5$) activation points, the $i$th of which is located $a_i$ distance counterclockwise from $0$ ($0\le a_i<L$). If you are currently at an activation point, you can instantaneously place a robot at that point. All robots (including the original) move counterclockwise at a rate of $1$ unit per $K$ seconds ($1\leq K\leq 10^6$). Compute the minimum time required to achieve the goal. ## Input The first line contains $L$, $R$, $N$, and $K$. The next line contains $N$ space-separated integers $a_1,a_2,\dots,a_N$. ## Output The minimum time required to achieve the goal. [samples] ## Note ##### For Sample 1: We can reach the activation point at $6$ in $4$ seconds by going clockwise. At this time, the initial robot will be located at $2$. Wait an additional $18$ seconds until the initial robot is located at $1$. Now we can place a robot to immediately win. ##### For Sample 2: We can reach the activation point at $7$ in $3$ seconds by going clockwise. At this time, the initial robot will be located at $1.5$. Wait an additional second until the initial robot is located at $2$. Now we can place a robot to immediately win. #### SCORING: - Inputs 5-6: $R=2$. - Inputs 7-12: $R\le 10, N\le 80$. - Inputs 13-20: $R\le 16$. - Inputs 21-24: No additional constraints.

Samples

Input #1

10 2 1 2
6

Output #1

Input #2

10 2 1 2
7

Output #2

Input #3

32 4 5 2
0 23 12 5 11

Output #3

Input #4

24 3 1 2
16

Output #4

API Response (JSON)

{
  "problem": {
    "name": "[USACO24OPEN] Activating Robots P",
    "description": {
      "content": "You and a single robot are initially at point $0$ on a circle with perimeter $L$ ($1 \\le L \\le 10^9$). You can move either counterclockwise or clockwise along the circle at $1$ unit per second. All mo",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 262144
    },
    "difficulty": {
      "LuoguStyle": "P6"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGP10285"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "You and a single robot are initially at point $0$ on a circle with perimeter $L$ ($1 \\le L \\le 10^9$). You can move either counterclockwise or clockwise along the circle at $1$ unit per second. All mo...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments