↵
<spoiler summary="Hint 1">↵
</spoiler>↵
↵
<spoiler summary="
Давайте заметим, что у нас могут быть только следующие пары чисел
Notice that only the following pairs of numbers are possible: $(x, x)$, $(x, 2 \cdot x)$, and $(x, 3 \cdot x)$.
↵
<spoiler summary="
Пусть $d = gcd(a, b)$, тогда заметим, что не может быть
Let $d = gcd(a, b)$. Now notice that it's impossible that $a = k \cdot d$
</spoiler>↵
↵
Количество первого типа $n$, второго
</spoiler>↵
↵
The number of the pairs of the first kind is $n$, of the second kind is $\lfloor \frac{n}{2} \rfloor$,
</spoiler>↵
↵
------------------------------↵
↵
↵
<spoiler summary="Hint 1">↵
</spoiler>↵
↵
<spoiler summary="Hint 2">↵
</spoiler>↵
↵
<spoiler summary="Hint 3">↵
Попытайтесь закрашивать клетки по диагоналям.
</spoiler>↵
↵
<spoiler summary="Hint 3">↵
Try to paint diagonals↵
</spoiler>↵
↵
<spoiler summary="Hint 4">↵
</spoiler>↵
↵
<spoiler summary="Решение">↵
↵
Давайте заметим, что ответ на задачу не меньше $\frac{n^2}{k}$, так как квадрат можно разбить на непересекающиеся подпрямоугольники размера $1 \times k$. Значит нужно научиться делать пример на это число.↵
↵
Решим вначале задачу, без ограничения на закрашенную клетку. Тогда нам хочется сделать что-то типа шахматной расскраски, то есть диаганальную раскраску.↵
↵
В этом случае, мы можем пронумеравать диаганали (от самой "нижней", до самой "верхней"). В этом случае в каждом подпрямоугольнике будет $k$ подряд идущих диагоналей, а значит, если закрасить каждую $k$ диаганаль, то мы получим ответ на задачу (и ответ в точности будет равен $\frac{n^2}{k}$, так как в каждом подпрямоугольнике мы закрасили ровно одну клетку).↵
↵
Ну а можно заметить, что клетка
</spoiler>↵
↵
<spoiler summary="Solution">↵
Notice that the answer to the problem is at least $\frac{n^2}{k}$, because you can split the square into so many non-intersecting rectangles of dimensions $1 \times k$. So let's try to paint exactly so many cells and see if maybe it's always possible.↵
↵
For simplicity, let's first solve the problem without necessarily painting $(r, c)$. In this case, we're looking for something like a chess coloring, which is a diagonal coloring.↵
↵
Let's number the diagonals from the "lowest" to the "highest". Notice that every $1 \times k$ and $k \times 1$ subrectangle intersects exactly $k$ consecutive diagonals, so we can paint every $k$-th diagonal to obtain the required answer: every such subrectangle will contain exactly one painted cell.↵
↵
To add the $(r, c)$ requirement back, notice that $(
↵
</spoiler>↵
↵
------------------------------↵
↵
↵
<spoiler summary="Hint 1">↵
</spoiler>↵
↵
<spoiler summary="Hint 2">↵
</spoiler>↵
↵
<spoiler summary="Hint 3">↵
</spoiler>↵
↵
<spoiler summary="Решение">↵
Очевидно, что для любого $i$ должно выполняться, что либо $a_i = b_i$, либо $b_i \leq b_{i + 1} + 1$, так как либо $a_i$ уже равно $b_i$ и $i$ элемент увеличивать не нужно, либо же мы должны увеличить $a_i$ до $b_i$ операциями из условия, а на них накладываются ограничения выше.↵
↵
Теперь докажем, что этих двух условий достаточно. Пусть $i$ — это индекс минимального элемента в $a$, который не равен $b_i$. Тогда заметим, что мы в любом случае сможем сделать $a_i := a_i+1$, так как в этом случае выполняется $a_i \leq b_i \leq b_{i + 1} + 1$, а значит можно увеличить $a_i$. То есть такими операциями можно получить массив $b$.↵
</spoiler>↵
↵
-------------------------------↵
↵
Задача D. Идея [user:FairyWinx,2022-09-02]↵
↵
<spoiler summary="Hint 1">↵
Переформулируйте чуть лучше задачу в терминах полного бинарного дерева.↵
</spoiler>↵
↵
<spoiler summary="Hint 2">↵
Странно на одной и той же глубине делать два изменения.↵
</spoiler>↵
↵
<spoiler summary="Решение">↵
↵
Давайте поймем, что задачу можно переформулировать следующим образом: Дано полное бинарное дерево с $2^n$ листами. Также для каждой вершины, не являющейся листом, помечено ребро в ровно одного из детей. А ответ на задачу — это лист, до которого можно добраться из корня по отмеченным ребрам. А изменения — это сменить помеченное ребро выходящее из вершины.↵
↵
Тогда понятно, что нет смысла делать изменения больше, чем у одной вершины на уровне, так как нам важна только одна вершина, до которой идет путь, а значит ответ зависит только от того, на каких глубинах мы решили поменять исход (и очевидно, что разные множества изменненых исходов дают разного победителя). А значит если $k$ фиксированно — $\binom{n}{k}$ (так как нам нужно просто выбрать, какие из $k$ глубин мы будем изменять), а значит ответ на задачу равен $\sum{\binom{n}{i}}$, где $0 \leq k \leq min(n, k)$
</spoiler>↵
↵
<spoiler summary="Solution">↵
Firstly, we obviously require $a_i \le b_i$ to hold for all $i$. With that out of our way, let's consider non-trivial cases. Also let $a_{n+1} = a_1, b_{n+1} = b_1$ cyclically.↵
↵
For each $i$, we require that either $a_i = b_i$ or $b_i \leq b_{i + 1} + 1$ holds. That's because if we increment $a_i$ at least once, we had $a_i = b_i - 1$ and $a_{i + 1} \le b_{i + 1}$ before the last increment of $a_i$, and from here it's just a matter of simple algebraic transformations.↵
↵
Now let's prove these two conditions are enough. Let $i$ be the index of the minimal element of $a$ such that $a_i < b_i$ (i.e. the smallest element that's not ready yet). Notice that in this case we can, in fact, assign $a_i := a_i+1$, because $a_i \leq b_i \leq b_{i + 1} + 1$ holds, and now we're one step closer to the required array. It's easy to continue this proof by induction.↵
</spoiler>↵
↵
-------------------------------↵
↵
Problem D. Idea by [user:FairyWinx,2022-09-02]↵
↵
<spoiler summary="Hint 1">↵
Reformulate this problem in terms of a complete binary tree.↵
</spoiler>↵
↵
<spoiler summary="Hint 2">↵
It would be strange for the sponsors to changes two nodes of the same depth.↵
</spoiler>↵
↵
<spoiler summary="Solution">↵
The problem can be reformulated as follows. We've got a complete binary tree with $2^n$ leaves. There's a marked edge from each intermediate node to one of its children. The winner is the leaf reachable from the root via marked edges. Changes modify the outgoing marked edge of a node.↵
↵
Now it should be fairly obvious that there's no reason to change more than one node per level, because only one node matters per level--the one on the path from the root to the answer node. So, the winner only depends on the subset of levels we perform changes on, and vice versa: different subsets always yield different winners.↵
↵
Sponsors can change exactly $i$ nodes in $\bimom{n}{i}$ ways. Summing this over $i$, we get $\sum_{i=0}^{\min(n, k)} \binom{n}{i}$. Call this number $m$. $m$ is the number of winners the sponsors choose between--let's call them candidates for brevity. It's easy to see that $m$ is the answer to the problem, because a) sponsors can guarantee the winner is at least $m$, as, independent of the list of candidate winners "provided" by Madoka, at least one of them must be at least $m$, and b) Madoka can guarantee the winner is at most $m$ by firstly marking edges arbitrarily, *then* computing the list of candidate nodes, and only *then* fill them with numbers from $1$ to $m$ (and the other nodes arbitrarily).↵
</spoiler>↵
↵
---------------------------------------↵
↵
↵
<spoiler summary="Hint 1">↵
</spoiler>↵
↵
<spoiler summary="Hint 2">↵
$gcd(a, b)$
</spoiler>↵
↵
<spoiler summary="Hint 3">↵
Вспомните о существовании функции эйлера↵
</spoiler>↵
↵
<spoiler summary="Решение">↵
Давайте будем перебирать $c$, тогда $gcd(a, b) = gcd(a, a + b) = gcd(a, n - c)$. Значит $gcd(a, b)$ являются делителем числа $n - c$. Давайте тогда переберем все делители числа $n - c$. Пусть $d$ является делителем, тогда количество пар чисел $a, b$, где $a + b = n - c$ и $gcd(a, b) = d$ равно $\phi (\frac{n - c}{d})$, так как нам нужно $a$ кратное $d$ и при этом оно должно быть простым с $\frac{n - c}{d}$, чтобы $gcd$ был в точности равен $d$.↵
↵
А значит ответ на задачу равен $\sum{lcm(c, d) * \phi{\frac{n - c}{d}}}$, где $1 \leq c \leq n - 2$, а $d$ делит $n - c$
</spoiler>↵
↵
<spoiler summary="Hint 3">↵
Recall the existence of the Euler's totient function↵
</spoiler>↵
↵
<spoiler summary="Solution">↵
Let's bruteforce $c$, then we have $gcd(a, b) = gcd(a, a + b) = gcd(a, n - c)$. This means that $gcd(a, b)$ divides $n - c$, so let's just go through all divisors of $n - c$. For every factor $d$, the count of pairs $(a, b)$ satisfying $a + b = n - c$ and $gcd(a, b) = d$ is $\phi (\frac{n - c}{d})$, because we need $d$ to divide $a$ and be coprime with $\frac{n - c}{d}$, so that the $gcd$ is equal to $d$.↵
↵
Therefore, the answer to the problem is $\sum{lcm(c, d) * \phi{\frac{n - c}{d}}}$, where $1 \leq c \leq n - 2$ and $d$ is a factor of $n - c$.↵
</spoiler>↵
↵
↵
---------------------------------------↵
↵
↵
Coming soon↵
↵
