{"problem":{"name":"C. Table Tennis Game 2","description":{"content":"Misha and Vanya have played several table tennis sets. Each set consists of several serves, each serve is won by one of the players, he receives one point and the loser receives nothing. Once one of t","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":2000,"memory_limit":524288},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF765C"},"statements":[{"statement_type":"Markdown","content":"Misha and Vanya have played several table tennis sets. Each set consists of several serves, each serve is won by one of the players, he receives one point and the loser receives nothing. Once one of the players scores exactly _k_ points, the score is reset and a new set begins.\n\nAcross all the sets Misha scored _a_ points in total, and Vanya scored _b_ points. Given this information, determine the maximum number of sets they could have played, or that the situation is impossible.\n\nNote that the game consisted of several complete sets.\n\n## Input\n\nThe first line contains three space-separated integers _k_, _a_ and _b_ (1 ≤ _k_ ≤ 109, 0 ≤ _a_, _b_ ≤ 109, _a_ + _b_ > 0).\n\n## Output\n\nIf the situation is impossible, print a single number -1. Otherwise, print the maximum possible number of sets.\n\n[samples]\n\n## Note\n\nNote that the rules of the game in this problem differ from the real table tennis game, for example, the rule of \"balance\" (the winning player has to be at least two points ahead to win a set) has no power within the present problem.","is_translate":false,"language":"English"},{"statement_type":"Markdown","content":"Misha 和 Vanya 玩了若干局乒乓球。每局由若干次发球组成，每次发球由一方获胜，胜者得一分，败者得零分。当某一方恰好获得 #cf_span[k] 分时，比分重置，开始新的一局。\n\n在所有局中，Misha 总共得了 #cf_span[a] 分，Vanya 总共得了 #cf_span[b] 分。根据这些信息，确定他们最多可能玩了多少局，或判断这种情况不可能。\n\n注意，比赛由若干个完整的局组成。\n\n第一行包含三个用空格分隔的整数 #cf_span[k], #cf_span[a] 和 #cf_span[b]（#cf_span[1 ≤ k ≤ 109], #cf_span[0 ≤ a, b ≤ 109], #cf_span[a + b > 0]）。\n\n如果情况不可能，输出 -1；否则，输出可能的最大局数。\n\n注意，本题中的游戏规则与真实乒乓球规则不同，例如“领先两分才能赢局”的规则在此题中不适用。\n\n## Input\n\n第一行包含三个用空格分隔的整数 #cf_span[k], #cf_span[a] 和 #cf_span[b]（#cf_span[1 ≤ k ≤ 109], #cf_span[0 ≤ a, b ≤ 109], #cf_span[a + b > 0]）。\n\n## Output\n\n如果情况不可能，输出 -1；否则，输出可能的最大局数。\n\n[samples]\n\n## Note\n\n注意，本题中的游戏规则与真实乒乓球规则不同，例如“领先两分才能赢局”的规则在此题中不适用。","is_translate":true,"language":"Chinese"},{"statement_type":"Markdown","content":"Let $ k, a, b \\in \\mathbb{Z} $ with $ 1 \\leq k \\leq 10^9 $, $ 0 \\leq a, b \\leq 10^9 $, and $ a + b > 0 $.\n\nDefine:\n- Each set ends when one player reaches exactly $ k $ points.\n- The winner of a set scores $ k $ points; the loser scores $ \\ell \\in \\{0, 1, \\dots, k-1\\} $ points.\n- Total points scored by Misha: $ a $\n- Total points scored by Vanya: $ b $\n\nLet $ m $ be the number of sets won by Misha, and $ n $ the number of sets won by Vanya. Then:\n\n$$\na = m \\cdot k + r, \\quad \\text{where } 0 \\leq r \\leq n(k-1)\n$$\n$$\nb = n \\cdot k + s, \\quad \\text{where } 0 \\leq s \\leq m(k-1)\n$$\n\nHere:\n- $ m \\cdot k $: points Misha earned by winning $ m $ sets.\n- $ r $: points Misha earned as a loser in $ n $ sets (at most $ k-1 $ per set).\n- Similarly for $ b = n \\cdot k + s $, with $ s \\leq m(k-1) $.\n\nWe aim to **maximize the total number of sets**: $ m + n $, subject to:\n\n$$\n\\begin{cases}\na = m k + r, & 0 \\leq r \\leq n(k-1) \\\\\nb = n k + s, & 0 \\leq s \\leq m(k-1)\n\\end{cases}\n\\quad \\text{with } m, n \\in \\mathbb{Z}_{\\geq 0}\n$$\n\nRewriting:\n\n$$\nr = a - m k \\geq 0 \\Rightarrow m \\leq \\left\\lfloor \\frac{a}{k} \\right\\rfloor\n$$\n$$\nr \\leq n(k-1) \\Rightarrow a - m k \\leq n(k-1)\n$$\n$$\ns = b - n k \\geq 0 \\Rightarrow n \\leq \\left\\lfloor \\frac{b}{k} \\right\\rfloor\n$$\n$$\ns \\leq m(k-1) \\Rightarrow b - n k \\leq m(k-1)\n$$\n\nSo for nonnegative integers $ m, n $, we require:\n\n$$\n\\begin{cases}\n0 \\leq m \\leq \\left\\lfloor \\frac{a}{k} \\right\\rfloor \\\\\n0 \\leq n \\leq \\left\\lfloor \\frac{b}{k} \\right\\rfloor \\\\\na - m k \\leq n(k - 1) \\\\\nb - n k \\leq m(k - 1)\n\\end{cases}\n$$\n\nWe seek to **maximize** $ m + n $ over all integer pairs $ (m, n) $ satisfying the above.\n\n---\n\n**Alternative approach for maximum sets:**\n\nTo maximize the number of sets, we want to **minimize** the points per set — i.e., have as many sets as possible where the winner wins by exactly $ k $, and the loser scores as many points as possible (up to $ k-1 $) to \"use up\" the remaining points.\n\nLet:\n- $ m = \\left\\lfloor \\frac{a}{k} \\right\\rfloor $: maximum number of sets Misha could have won\n- $ n = \\left\\lfloor \\frac{b}{k} \\right\\rfloor $: maximum number of sets Vanya could have won\n\nThen the remaining points are:\n- $ r = a \\bmod k $: Misha’s points from losing sets\n- $ s = b \\bmod k $: Vanya’s points from losing sets\n\nFor these to be valid:\n- Misha’s $ r $ points must have been earned while losing $ n $ sets → $ r \\leq n(k - 1) $\n- Vanya’s $ s $ points must have been earned while losing $ m $ sets → $ s \\leq m(k - 1) $\n\nThus, the **maximum possible number of sets** is $ m + n $ **if and only if**:\n$$\na \\bmod k \\leq \\left\\lfloor \\frac{b}{k} \\right\\rfloor (k - 1) \\quad \\text{and} \\quad b \\bmod k \\leq \\left\\lfloor \\frac{a}{k} \\right\\rfloor (k - 1)\n$$\n\nIf both conditions hold, answer is $ \\left\\lfloor \\frac{a}{k} \\right\\rfloor + \\left\\lfloor \\frac{b}{k} \\right\\rfloor $\n\nBut is this always maximal?\n\nSuppose we reduce $ m $ by 1 to allow more \"loss points\" for Vanya? Could that allow a higher total $ m + n $? Let’s test.\n\nSuppose we try $ m' = m - t $, $ n' = n + u $, but then $ m'k \\leq a $, $ n'k \\leq b $, and we need:\n\n- $ a - m'k \\leq n'(k - 1) $\n- $ b - n'k \\leq m'(k - 1) $\n\nBut since $ m = \\lfloor a/k \\rfloor $, reducing $ m $ reduces the left-hand side of the second inequality, making it harder to satisfy. Similarly, increasing $ n $ beyond $ \\lfloor b/k \\rfloor $ is impossible.\n\nSo the **maximum possible** number of sets is achieved when $ m = \\lfloor a/k \\rfloor $, $ n = \\lfloor b/k \\rfloor $, **if** the loss-point constraints are satisfied.\n\nIf not, then it’s impossible? Not necessarily — maybe we can reduce *both* $ m $ and $ n $ to make the loss-point constraints hold? But that would reduce total sets. We want the **maximum**.\n\nSo if the natural $ m, n $ don’t satisfy the loss constraints, we must check whether **any** $ m' \\leq \\lfloor a/k \\rfloor $, $ n' \\leq \\lfloor b/k \\rfloor $ exist such that:\n\n$$\na - m'k \\leq n'(k - 1) \\\\\nb - n'k \\leq m'(k - 1)\n$$\n\nBut since we want to **maximize** $ m' + n' $, and $ m' = \\lfloor a/k \\rfloor $, $ n' = \\lfloor b/k \\rfloor $ is the largest possible, if it fails, then **no larger** combination exists. So we must check if **any** pair $ (m', n') $ with $ m' + n' = m + n - 1 $, etc., satisfies — but that would yield fewer sets.\n\nThus, the **maximum possible** number of sets is $ \\lfloor a/k \\rfloor + \\lfloor b/k \\rfloor $ **if and only if**:\n\n$$\n(a \\bmod k) \\leq \\left\\lfloor \\frac{b}{k} \\right\\rfloor (k - 1) \\quad \\text{and} \\quad (b \\bmod k) \\leq \\left\\lfloor \\frac{a}{k} \\right\\rfloor (k - 1)\n$$\n\nIf not, then we must check whether it's possible at all.\n\nWait — what if one of $ a $ or $ b $ is zero?\n\nExample: $ k=2, a=1, b=0 $\n\nThen $ m = \\lfloor 1/2 \\rfloor = 0 $, $ n = 0 $, so total sets = 0? But total points = 1 > 0 — contradiction.\n\nWait: if no set was completed? But problem says: “the game consisted of several complete sets.” So **every point must come from a complete set**.\n\nSo if $ a + b > 0 $, and no set was completed? Contradiction.\n\nThus, if $ a < k $ and $ b < k $, then **no set can be completed**, but total points > 0 → **impossible**.\n\nSo we must have **at least one set completed**.\n\nTherefore, if $ a < k $ and $ b < k $, then it's impossible unless one of them is ≥ k.\n\nWait — but in a set, only one player reaches k. So if both a < k and b < k, then no set was completed → contradiction with “several complete sets”.\n\nSo necessary condition: $ a \\geq k $ or $ b \\geq k $\n\nBut even more: since each set ends when someone reaches k, the total number of sets is at least 1, so at least one of $ a \\geq k $ or $ b \\geq k $ must hold.\n\nBut even then, if $ a = 1, b = 1, k = 2 $, then total points = 2, but no one reached 2 → no complete set → impossible.\n\nSo **necessary condition**: $ \\max(a, b) \\geq k $\n\nBut is that sufficient? No: suppose $ a = k $, $ b = k-1 $. Then Misha won one set (k points), Vanya lost that set with k-1 points — valid. So total sets = 1.\n\nBut if $ a = k $, $ b = k $, then possibly two sets: Misha won one, Vanya won one — each with 0 loss points. Or one set? No — in one set, only one player reaches k. So if both have k, then two sets must have been played.\n\nSo:\n\nLet $ m = \\lfloor a/k \\rfloor $, $ n = \\lfloor b/k \\rfloor $\n\nThen total sets = $ m + n $\n\nRemaining points: $ r = a - mk $, $ s = b - nk $\n\nThese must be explainable as loss points:\n\n- Misha lost $ n $ sets → can have at most $ n(k-1) $ loss points → $ r \\leq n(k-1) $\n- Vanya lost $ m $ sets → can have at most $ m(k-1) $ loss points → $ s \\leq m(k-1) $\n\nIf both inequalities hold → answer = $ m + n $\n\nIf not → is it possible with fewer sets?\n\nSuppose we try to reduce $ m $ by 1 → then Misha’s loss points become $ r + k $, and Vanya’s maximum allowed loss points become $ (m-1)(k-1) $\n\nBut $ r + k \\leq n(k-1) $? Unlikely, since $ r = a \\bmod k < k $, so $ r + k < 2k $, but $ n(k-1) $ could be small.\n\nActually, if the natural assignment fails, **it is impossible** to assign the points to any number of sets, because:\n\n- Each set contributes exactly $ k $ points to the winner and between 0 and $ k-1 $ to the loser.\n- The total number of sets is $ m + n $, where $ m $ is number of sets won by Misha, $ n $ by Vanya.\n- The total points from wins: $ mk + nk = (m+n)k $\n- The total points from losses: $ a + b - (m+n)k = r + s $\n- And we must have $ r \\leq n(k-1) $, $ s \\leq m(k-1) $\n\nBut if $ r > n(k-1) $, then even if Misha lost all $ n $ sets, he couldn’t have scored $ r $ points — impossible.\n\nSimilarly for $ s > m(k-1) $\n\nAnd since $ m $ and $ n $ are **maximal** possible (because $ m = \\lfloor a/k \\rfloor $, $ n = \\lfloor b/k \\rfloor $), any reduction in $ m $ or $ n $ would only reduce the capacity for loss points (since $ m(k-1) $ or $ n(k-1) $ decreases), while increasing $ r $ or $ s $ (because we’re removing $ k $ from a win and adding it to loss), making constraints harder to satisfy.\n\nTherefore, if the maximal $ m, n $ do not satisfy the constraints, **no solution exists**.\n\nThus, algorithm:\n\n1. Let $ m = \\left\\lfloor \\frac{a}{k} \\right\\rfloor $, $ n = \\left\\lfloor \\frac{b}{k} \\right\\rfloor $\n2. Let $ r = a \\bmod k $, $ s = b \\bmod k $\n3. If $ r \\leq n(k - 1) $ and $ s \\leq m(k - 1) $, then answer is $ m + n $\n4. Else, answer is -1\n\nBut wait — what if $ k = 1 $? Then $ k - 1 = 0 $, so loss points must be 0.\n\nThen $ r = a \\bmod 1 = 0 $, $ s = b \\bmod 1 = 0 $, so always satisfied.\n\nAnd $ m = a $, $ n = b $, total sets = $ a + b $, which makes sense: each point is a set.\n\nAlso, if $ a = 0 $, $ b = 5 $, $ k = 3 $: then $ m = 0 $, $ n = 1 $, $ r = 0 $, $ s = 2 $\n\nCheck: $ r = 0 \\leq n(k-1) = 1 \\cdot 2 = 2 $ → OK\n\n$ s = 2 \\leq m(k-1) = 0 \\cdot 2 = 0 $ → **2 ≤ 0?** No → impossible.\n\nBut Vanya won 1 set (scored 3), and has 2 extra points? That would mean he scored 5 total: 3 from win, 2 from loss — but if he won 1 set, he couldn’t have lost any set! So those 2 points are unaccounted for → impossible.\n\nSo condition correctly rejects.\n\nAnother case: $ a = 3, b = 3, k = 3 $\n\nThen $ m = 1, n = 1 $\n\n$ r = 0, s = 0 $\n\nCheck: $ 0 \\leq 1 \\cdot 2 = 2 $, $ 0 \\leq 1 \\cdot 2 = 2 $ → OK → total sets = 2\n\nValid: Misha won one set (3-0), Vanya won one set (3-0)\n\nOr: Misha won one set (3-1), Vanya won one set (3-2)? But then a = 3 + 2 = 5, b = 1 + 3 = 4 — not this case.\n\nIn our case, a=3, b=3 → each won one set with 0 loss points → valid.\n\nSo final formal answer:\n\n---\n\nLet $ m = \\left\\lfloor \\frac{a}{k} \\right\\rfloor $, $ n = \\left\\lfloor \\frac{b}{k} \\right\\rfloor $,  \n$ r = a - m k $, $ s = b - n k $\n\nThen:\n\n$$\n\\boxed{\n\\begin{cases}\nm + n & \\text{if } r \\leq n(k - 1) \\text{ and } s \\leq m(k - 1) \\\\\n-1 & \\text{otherwise}\n\\end{cases}\n}\n$$","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF765C","tags":["math"],"sample_group":[["11 11 5","1"],["11 2 3","\\-1"]],"created_at":"2026-03-03 11:00:39"}}