{"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 movement in this problem is continuous.  \n\nYour 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$).  \n\nCompute the minimum time required to achieve the goal.\n\n## Input\n\nThe first line contains $L$, $R$, $N$, and $K$.  \n\nThe next line contains $N$ space-separated integers $a_1,a_2,\\dots,a_N$.\n\n## Output\n\nThe minimum time required to achieve the goal.\n\n[samples]\n\n## Note\n\n##### For Sample 1:\nWe 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.  \n\n##### For Sample 2:\nWe 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.  \n\n#### SCORING:\n- Inputs 5-6: $R=2$.\n- Inputs 7-12: $R\\le 10, N\\le 80$.\n- Inputs 13-20: $R\\le 16$.\n- Inputs 21-24: No additional constraints.","is_translate":false,"language":"English"}],"meta":{"iden":"LGP10285","tags":["二分","USACO","2024","状压 DP"],"sample_group":[["10 2 1 2\n6","22"],["10 2 1 2\n7","4"],["32 4 5 2\n0 23 12 5 11","48"],["24 3 1 2\n16","48"]],"created_at":"2026-03-03 11:09:25"}}