English · Original
Chinese · Translation
Formal · Original
$k$ people want to split $n$ candies between them. Each candy should be given to exactly one of them or be thrown away.
The people are numbered from $1$ to $k$, and Arkady is the first of them. To split the candies, Arkady will choose an integer $x$ and then give the first $x$ candies to himself, the next $x$ candies to the second person, the next $x$ candies to the third person and so on in a cycle. The leftover (the remainder that is not divisible by $x$) will be thrown away.
Arkady can't choose $x$ greater than $M$ as it is considered greedy. Also, he can't choose such a small $x$ that some person will receive candies more than $D$ times, as it is considered a slow splitting.
Please find what is the maximum number of candies Arkady can receive by choosing some valid $x$.
## Input
The only line contains four integers $n$, $k$, $M$ and $D$ ($2 \le n \le 10^{18}$, $2 \le k \le n$, $1 \le M \le n$, $1 \le D \le \min{(n, 1000)}$, $M \cdot D \cdot k \ge n$) — the number of candies, the number of people, the maximum number of candies given to a person at once, the maximum number of times a person can receive candies.
## Output
Print a single integer — the maximum possible number of candies Arkady can give to himself.
Note that it is always possible to choose some valid $x$.
[samples]
## Note
In the first example Arkady should choose $x = 4$. He will give $4$ candies to himself, $4$ candies to the second person, $4$ candies to the third person, then $4$ candies to the fourth person and then again $4$ candies to himself. No person is given candies more than $2$ times, and Arkady receives $8$ candies in total.
Note that if Arkady chooses $x = 5$, he will receive only $5$ candies, and if he chooses $x = 3$, he will receive only $3 + 3 = 6$ candies as well as the second person, the third and the fourth persons will receive $3$ candies, and $2$ candies will be thrown away. He can't choose $x = 1$ nor $x = 2$ because in these cases he will receive candies more than $2$ times.
In the second example Arkady has to choose $x = 4$, because any smaller value leads to him receiving candies more than $1$ time.
$k$ 个人想要分 $n$ 颗糖果。每颗糖果必须恰好分给其中一人，或被丢弃。
这些人编号为 $1$ 到 $k$，其中 Arkady 是第一个人。为了分糖果，Arkady 将选择一个整数 $x$，然后将前 $x$ 颗糖果给他自己，接下来的 $x$ 颗给第二个人，再接下来的 $x$ 颗给第三个人，依此类推循环分配。剩余的（不能被 $x$ 整除的部分）将被丢弃。
Arkady 不能选择大于 $M$ 的 $x$，因为这被认为是贪婪的。他也不能选择过小的 $x$，使得任何人收到糖果的次数超过 $D$ 次，因为这被认为是缓慢分配。
请找出通过选择某个合法的 $x$，Arkady 能获得的最大糖果数。
仅一行包含四个整数 $n$, $k$, $M$ 和 $D$（$2 lt.eq n lt.eq 10^(18)$，$2 lt.eq k lt.eq n$，$1 lt.eq M lt.eq n$，$1 lt.eq D lt.eq min (n, 1000)$，$M dot.op D dot.op k gt.eq n$）—— 分别表示糖果数量、人数、每人每次最多获得的糖果数、每人最多能收到糖果的次数。
输出一个整数——Arkady 能给自己分配的最多糖果数。
注意，总存在至少一个合法的 $x$。
在第一个例子中，Arkady 应选择 $x = 4$。他将给自身 $4$ 颗糖果，第二人 $4$ 颗，第三人 $4$ 颗，第四人 $4$ 颗，然后再给自身 $4$ 颗。没有人收到糖果超过 $2$ 次，Arkady 总共获得 $8$ 颗糖果。
注意，如果 Arkady 选择 $x = 5$，他将只获得 $5$ 颗糖果；如果选择 $x = 3$，他将获得 $3 + 3 = 6$ 颗糖果，同时第二、三、四人各获得 $3$ 颗，剩余 $2$ 颗被丢弃。他不能选择 $x = 1$ 或 $x = 2$，因为在这些情况下他会收到糖果超过 $2$ 次。
在第二个例子中，Arkady 必须选择 $x = 4$，因为任何更小的值都会导致他收到糖果超过 $1$ 次。
## Input
仅一行包含四个整数 $n$, $k$, $M$ 和 $D$（$2 lt.eq n lt.eq 10^(18)$，$2 lt.eq k lt.eq n$，$1 lt.eq M lt.eq n$，$1 lt.eq D lt.eq min (n, 1000)$，$M dot.op D dot.op k gt.eq n$）—— 分别表示糖果数量、人数、每人每次最多获得的糖果数、每人最多能收到糖果的次数。
## Output
输出一个整数——Arkady 能给自己分配的最多糖果数。注意，总存在至少一个合法的 $x$。
[samples]
## Note
在第一个例子中，Arkady 应选择 $x = 4$。他将给自身 $4$ 颗糖果，第二人 $4$ 颗，第三人 $4$ 颗，第四人 $4$ 颗，然后再给自身 $4$ 颗。没有人收到糖果超过 $2$ 次，Arkady 总共获得 $8$ 颗糖果。
注意，如果 Arkady 选择 $x = 5$，他将只获得 $5$ 颗糖果；如果选择 $x = 3$，他将获得 $3 + 3 = 6$ 颗糖果，同时第二、三、四人各获得 $3$ 颗，剩余 $2$ 颗被丢弃。他不能选择 $x = 1$ 或 $x = 2$，因为在这些情况下他会收到糖果超过 $2$ 次。
在第二个例子中，Arkady 必须选择 $x = 4$，因为任何更小的值都会导致他收到糖果超过 $1$ 次。
**Definitions**
Let $ n, k, M, D \in \mathbb{Z}^+ $ be given integers with:
- $ n $: total number of candies,
- $ k $: number of people (Arkady is person 1),
- $ M $: maximum candies per turn ($ x \leq M $),
- $ D $: maximum number of times any person may receive candies.
Let $ x \in \mathbb{Z}^+ $ be the number of candies distributed per turn, satisfying:
- $ 1 \leq x \leq M $,
- Each person receives candies at most $ D $ times.
**Constraints**
1. $ 2 \leq n \leq 10^{18} $
2. $ 2 \leq k \leq n $
3. $ 1 \leq M \leq n $
4. $ 1 \leq D \leq \min(n, 1000) $
5. $ M \cdot D \cdot k \geq n $ (guarantees at least one valid $ x $)
**Objective**
For a fixed $ x $, the candies are distributed in cycles of $ k $ people, each receiving $ x $ candies per turn. The total number of full turns is $ t = \left\lfloor \frac{n}{x} \right\rfloor $.
The number of times Arkady (person 1) receives candies is:
$$
t_1 = \left\lfloor \frac{t - 1}{k} \right\rfloor + 1
$$
(He receives candies on turns $ 1, k+1, 2k+1, \dots $)
Arkady’s total candies:
$$
C(x) = x \cdot t_1 = x \cdot \left( \left\lfloor \frac{ \left\lfloor \frac{n}{x} \right\rfloor - 1 }{k} \right\rfloor + 1 \right)
$$
Subject to:
- $ x \leq M $,
- $ t_1 \leq D $
**Goal**:
Maximize $ C(x) $ over all integers $ x \in [1, M] $ such that $ \left\lfloor \frac{ \left\lfloor \frac{n}{x} \right\rfloor - 1 }{k} \right\rfloor + 1 \leq D $.
That is:
$$
\max_{\substack{1 \leq x \leq M \\ \left\lfloor \frac{ \left\lfloor \frac{n}{x} \right\rfloor - 1 }{k} \right\rfloor + 1 \leq D}} \left( x \cdot \left( \left\lfloor \frac{ \left\lfloor \frac{n}{x} \right\rfloor - 1 }{k} \right\rfloor + 1 \right) \right)
$$
API Response (JSON)
{
"problem": {
"name": "C. Greedy Arkady",
"description": {
"content": "$k$ people want to split $n$ candies between them. Each candy should be given to exactly one of them or be thrown away. The people are numbered from $1$ to $k$, and Arkady is the first of them. To sp",
"description_type": "Markdown"
},
"platform": "Codeforces",
"limit": {
"time_limit": 1000,
"memory_limit": 262144
},
"difficulty": "None",
"is_remote": true,
"is_sync": true,
"sync_url": null,
"sign": "CF965C"
},
"statements": [
{
"statement_type": "Markdown",
"content": "$k$ people want to split $n$ candies between them. Each candy should be given to exactly one of them or be thrown away.\n\nThe people are numbered from $1$ to $k$, and Arkady is the first of them. To sp...",
"is_translate": false,
"language": "English"
},
{
"statement_type": "Markdown",
"content": "$k$ 个人想要分 $n$ 颗糖果。每颗糖果必须恰好分给其中一人，或被丢弃。\n\n这些人编号为 $1$ 到 $k$，其中 Arkady 是第一个人。为了分糖果，Arkady 将选择一个整数 $x$，然后将前 $x$ 颗糖果给他自己，接下来的 $x$ 颗给第二个人，再接下来的 $x$ 颗给第三个人，依此类推循环分配。剩余的（不能被 $x$ 整除的部分）将被丢弃。\n\nArkady 不能选择大于 $M$ ...",
"is_translate": true,
"language": "Chinese"
},
{
"statement_type": "Markdown",
"content": "**Definitions** \nLet $ n, k, M, D \\in \\mathbb{Z}^+ $ be given integers with: \n- $ n $: total number of candies, \n- $ k $: number of people (Arkady is person 1), \n- $ M $: maximum candies per turn ...",
"is_translate": false,
"language": "Formal"
}
]
}