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 $.
Define:
- Each set ends when one player reaches exactly $ k $ points.
- The winner of a set scores $ k $ points; the loser scores $ \ell \in \{0, 1, \dots, k-1\} $ points.
- Total points scored by Misha: $ a $
- Total points scored by Vanya: $ b $
Let $ m $ be the number of sets won by Misha, and $ n $ the number of sets won by Vanya. Then:
$$
a = m \cdot k + r, \quad \text{where } 0 \leq r \leq n(k-1)
$$
$$
b = n \cdot k + s, \quad \text{where } 0 \leq s \leq m(k-1)
$$
Here:
- $ m \cdot k $: points Misha earned by winning $ m $ sets.
- $ r $: points Misha earned as a loser in $ n $ sets (at most $ k-1 $ per set).
- Similarly for $ b = n \cdot k + s $, with $ s \leq m(k-1) $.
We aim to **maximize the total number of sets**: $ m + n $, subject to:
$$
\begin{cases}
a = m k + r, & 0 \leq r \leq n(k-1) \\
b = n k + s, & 0 \leq s \leq m(k-1)
\end{cases}
\quad \text{with } m, n \in \mathbb{Z}_{\geq 0}
$$
Rewriting:
$$
r = a - m k \geq 0 \Rightarrow m \leq \left\lfloor \frac{a}{k} \right\rfloor
$$
$$
r \leq n(k-1) \Rightarrow a - m k \leq n(k-1)
$$
$$
s = b - n k \geq 0 \Rightarrow n \leq \left\lfloor \frac{b}{k} \right\rfloor
$$
$$
s \leq m(k-1) \Rightarrow b - n k \leq m(k-1)
$$
So for nonnegative integers $ m, n $, we require:
$$
\begin{cases}
0 \leq m \leq \left\lfloor \frac{a}{k} \right\rfloor \\
0 \leq n \leq \left\lfloor \frac{b}{k} \right\rfloor \\
a - m k \leq n(k - 1) \\
b - n k \leq m(k - 1)
\end{cases}
$$
We seek to **maximize** $ m + n $ over all integer pairs $ (m, n) $ satisfying the above.
---
**Alternative approach for maximum sets:**
To 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.
Let:
- $ m = \left\lfloor \frac{a}{k} \right\rfloor $: maximum number of sets Misha could have won
- $ n = \left\lfloor \frac{b}{k} \right\rfloor $: maximum number of sets Vanya could have won
Then the remaining points are:
- $ r = a \bmod k $: Misha’s points from losing sets
- $ s = b \bmod k $: Vanya’s points from losing sets
For these to be valid:
- Misha’s $ r $ points must have been earned while losing $ n $ sets → $ r \leq n(k - 1) $
- Vanya’s $ s $ points must have been earned while losing $ m $ sets → $ s \leq m(k - 1) $
Thus, the **maximum possible number of sets** is $ m + n $ **if and only if**:
$$
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)
$$
If both conditions hold, answer is $ \left\lfloor \frac{a}{k} \right\rfloor + \left\lfloor \frac{b}{k} \right\rfloor $
But is this always maximal?
Suppose we reduce $ m $ by 1 to allow more "loss points" for Vanya? Could that allow a higher total $ m + n $? Let’s test.
Suppose we try $ m' = m - t $, $ n' = n + u $, but then $ m'k \leq a $, $ n'k \leq b $, and we need:
- $ a - m'k \leq n'(k - 1) $
- $ b - n'k \leq m'(k - 1) $
But 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.
So 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.
If 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**.
So 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:
$$
a - m'k \leq n'(k - 1) \\
b - n'k \leq m'(k - 1)
$$
But 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.
Thus, the **maximum possible** number of sets is $ \lfloor a/k \rfloor + \lfloor b/k \rfloor $ **if and only if**:
$$
(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)
$$
If not, then we must check whether it's possible at all.
Wait — what if one of $ a $ or $ b $ is zero?
Example: $ k=2, a=1, b=0 $
Then $ m = \lfloor 1/2 \rfloor = 0 $, $ n = 0 $, so total sets = 0? But total points = 1 > 0 — contradiction.
Wait: if no set was completed? But problem says: “the game consisted of several complete sets.” So **every point must come from a complete set**.
So if $ a + b > 0 $, and no set was completed? Contradiction.
Thus, if $ a < k $ and $ b < k $, then **no set can be completed**, but total points > 0 → **impossible**.
So we must have **at least one set completed**.
Therefore, if $ a < k $ and $ b < k $, then it's impossible unless one of them is ≥ k.
Wait — 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”.
So necessary condition: $ a \geq k $ or $ b \geq k $
But 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.
But even then, if $ a = 1, b = 1, k = 2 $, then total points = 2, but no one reached 2 → no complete set → impossible.
So **necessary condition**: $ \max(a, b) \geq k $
But 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.
But 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.
So:
Let $ m = \lfloor a/k \rfloor $, $ n = \lfloor b/k \rfloor $
Then total sets = $ m + n $
Remaining points: $ r = a - mk $, $ s = b - nk $
These must be explainable as loss points:
- Misha lost $ n $ sets → can have at most $ n(k-1) $ loss points → $ r \leq n(k-1) $
- Vanya lost $ m $ sets → can have at most $ m(k-1) $ loss points → $ s \leq m(k-1) $
If both inequalities hold → answer = $ m + n $
If not → is it possible with fewer sets?
Suppose 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) $
But $ r + k \leq n(k-1) $? Unlikely, since $ r = a \bmod k < k $, so $ r + k < 2k $, but $ n(k-1) $ could be small.
Actually, if the natural assignment fails, **it is impossible** to assign the points to any number of sets, because:
- Each set contributes exactly $ k $ points to the winner and between 0 and $ k-1 $ to the loser.
- The total number of sets is $ m + n $, where $ m $ is number of sets won by Misha, $ n $ by Vanya.
- The total points from wins: $ mk + nk = (m+n)k $
- The total points from losses: $ a + b - (m+n)k = r + s $
- And we must have $ r \leq n(k-1) $, $ s \leq m(k-1) $
But if $ r > n(k-1) $, then even if Misha lost all $ n $ sets, he couldn’t have scored $ r $ points — impossible.
Similarly for $ s > m(k-1) $
And 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.
Therefore, if the maximal $ m, n $ do not satisfy the constraints, **no solution exists**.
Thus, algorithm:
1. Let $ m = \left\lfloor \frac{a}{k} \right\rfloor $, $ n = \left\lfloor \frac{b}{k} \right\rfloor $
2. Let $ r = a \bmod k $, $ s = b \bmod k $
3. If $ r \leq n(k - 1) $ and $ s \leq m(k - 1) $, then answer is $ m + n $
4. Else, answer is -1
But wait — what if $ k = 1 $? Then $ k - 1 = 0 $, so loss points must be 0.
Then $ r = a \bmod 1 = 0 $, $ s = b \bmod 1 = 0 $, so always satisfied.
And $ m = a $, $ n = b $, total sets = $ a + b $, which makes sense: each point is a set.
Also, if $ a = 0 $, $ b = 5 $, $ k = 3 $: then $ m = 0 $, $ n = 1 $, $ r = 0 $, $ s = 2 $
Check: $ r = 0 \leq n(k-1) = 1 \cdot 2 = 2 $ → OK
$ s = 2 \leq m(k-1) = 0 \cdot 2 = 0 $ → **2 ≤ 0?** No → impossible.
But 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.
So condition correctly rejects.
Another case: $ a = 3, b = 3, k = 3 $
Then $ m = 1, n = 1 $
$ r = 0, s = 0 $
Check: $ 0 \leq 1 \cdot 2 = 2 $, $ 0 \leq 1 \cdot 2 = 2 $ → OK → total sets = 2
Valid: Misha won one set (3-0), Vanya won one set (3-0)
Or: 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.
In our case, a=3, b=3 → each won one set with 0 loss points → valid.
So final formal answer:
---
Let $ m = \left\lfloor \frac{a}{k} \right\rfloor $, $ n = \left\lfloor \frac{b}{k} \right\rfloor $,
$ r = a - m k $, $ s = b - n k $
Then:
$$
\boxed{
\begin{cases}
m + n & \text{if } r \leq n(k - 1) \text{ and } s \leq m(k - 1) \\
-1 & \text{otherwise}
\end{cases}
}
$$