{"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 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.\n\nArkady 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.\n\nPlease find what is the maximum number of candies Arkady can receive by choosing some valid $x$.\n\n## Input\n\nThe 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.\n\n## Output\n\nPrint a single integer — the maximum possible number of candies Arkady can give to himself.\n\nNote that it is always possible to choose some valid $x$.\n\n[samples]\n\n## Note\n\nIn 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.\n\nNote 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.\n\nIn the second example Arkady has to choose $x = 4$, because any smaller value leads to him receiving candies more than $1$ time.","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$ 的 $x$，因为这被认为是贪婪的。他也不能选择过小的 $x$，使得任何人收到糖果的次数超过 $D$ 次，因为这被认为是缓慢分配。\n\n请找出通过选择某个合法的 $x$，Arkady 能获得的最大糖果数。\n\n仅一行包含四个整数 $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$）—— 分别表示糖果数量、人数、每人每次最多获得的糖果数、每人最多能收到糖果的次数。\n\n输出一个整数——Arkady 能给自己分配的最多糖果数。\n\n注意，总存在至少一个合法的 $x$。\n\n在第一个例子中，Arkady 应选择 $x = 4$。他将给自身 $4$ 颗糖果，第二人 $4$ 颗，第三人 $4$ 颗，第四人 $4$ 颗，然后再给自身 $4$ 颗。没有人收到糖果超过 $2$ 次，Arkady 总共获得 $8$ 颗糖果。\n\n注意，如果 Arkady 选择 $x = 5$，他将只获得 $5$ 颗糖果；如果选择 $x = 3$，他将获得 $3 + 3 = 6$ 颗糖果，同时第二、三、四人各获得 $3$ 颗，剩余 $2$ 颗被丢弃。他不能选择 $x = 1$ 或 $x = 2$，因为在这些情况下他会收到糖果超过 $2$ 次。\n\n在第二个例子中，Arkady 必须选择 $x = 4$，因为任何更小的值都会导致他收到糖果超过 $1$ 次。\n\n## Input\n\n仅一行包含四个整数 $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$）—— 分别表示糖果数量、人数、每人每次最多获得的糖果数、每人最多能收到糖果的次数。\n\n## Output\n\n输出一个整数——Arkady 能给自己分配的最多糖果数。注意，总存在至少一个合法的 $x$。\n\n[samples]\n\n## Note\n\n在第一个例子中，Arkady 应选择 $x = 4$。他将给自身 $4$ 颗糖果，第二人 $4$ 颗，第三人 $4$ 颗，第四人 $4$ 颗，然后再给自身 $4$ 颗。没有人收到糖果超过 $2$ 次，Arkady 总共获得 $8$ 颗糖果。\n\n注意，如果 Arkady 选择 $x = 5$，他将只获得 $5$ 颗糖果；如果选择 $x = 3$，他将获得 $3 + 3 = 6$ 颗糖果，同时第二、三、四人各获得 $3$ 颗，剩余 $2$ 颗被丢弃。他不能选择 $x = 1$ 或 $x = 2$，因为在这些情况下他会收到糖果超过 $2$ 次。\n\n在第二个例子中，Arkady 必须选择 $x = 4$，因为任何更小的值都会导致他收到糖果超过 $1$ 次。","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 ($ x \\leq M $),  \n- $ D $: maximum number of times any person may receive candies.  \n\nLet $ x \\in \\mathbb{Z}^+ $ be the number of candies distributed per turn, satisfying:  \n- $ 1 \\leq x \\leq M $,  \n- Each person receives candies at most $ D $ times.  \n\n**Constraints**  \n1. $ 2 \\leq n \\leq 10^{18} $  \n2. $ 2 \\leq k \\leq n $  \n3. $ 1 \\leq M \\leq n $  \n4. $ 1 \\leq D \\leq \\min(n, 1000) $  \n5. $ M \\cdot D \\cdot k \\geq n $ (guarantees at least one valid $ x $)  \n\n**Objective**  \nFor 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 $.  \n\nThe number of times Arkady (person 1) receives candies is:  \n$$\nt_1 = \\left\\lfloor \\frac{t - 1}{k} \\right\\rfloor + 1\n$$  \n(He receives candies on turns $ 1, k+1, 2k+1, \\dots $)  \n\nArkady’s total candies:  \n$$\nC(x) = x \\cdot t_1 = x \\cdot \\left( \\left\\lfloor \\frac{ \\left\\lfloor \\frac{n}{x} \\right\\rfloor - 1 }{k} \\right\\rfloor + 1 \\right)\n$$  \n\nSubject to:  \n- $ x \\leq M $,  \n- $ t_1 \\leq D $  \n\n**Goal**:  \nMaximize $ 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 $.  \n\nThat is:  \n$$\n\\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)\n$$","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF965C","tags":["math"],"sample_group":[["20 4 5 2","8"],["30 9 4 1","4"]],"created_at":"2026-03-03 11:00:39"}}