\begin{tutorial}{Defense Distance}

{
    \parindent=1cm
    \begin{tabular}{l@{\extracolsep{1cm}}l}
         Идея: & Артем Васильев\\
         Разработка: & Михаил Первеев\\
     \end{tabular}
}

Для начала заметим, что расстояние Левенштейна является метрикой, а значит для него выполняется неравенство треугольника. Поэтому, если $a > b + c$ или $b > a + c$ или $c > a + b$, построить требуемые строки невозможно.

Во всех остальных случаях, когда неравенство треугольника выполняется, построить требуемые строки возможно. Рассмотрим один из способов, как это можно сделать.

Для удобства будем строить строки $s$, $t$ и $u$ одинаковой длины. Разобьем каждую из трех строк на блоки длины $x$, $y$ и $z$. Для удобства пронумеруем эти блоки слева-направо числами от $1$ до $3$. Таким образом, строки можно представить как конкатенации блоков: $s = s_1 + s_2 + s_3$, $t = t_1 + t_2 + t_3$, $u = u_1 + u_2 + u_3$, где $\lvert s_1 \rvert = \lvert t_1 \rvert = \lvert u_1 \rvert = x$, $\lvert s_2 \rvert = \lvert t_2 \rvert = \lvert u_2 \rvert = y$ и $\lvert s_3 \rvert = \lvert t_3 \rvert = \lvert u_3 \rvert = z$.

Теперь построим строки по следующим правилам:

\begin{itemize}
\item Строки $s$ и $t$ будут различаться в каждом символе блоков $1$ и $2$, но совпадать в каждом символе блока $3$;
\item Строки $s$ и $u$ будут различаться в каждом символе блоков $1$ и $3$, но совпадать в каждом символе блока $2$;
\item Строки $t$ и $u$ будут различаться в каждом символе блоков $2$ и $3$, но совпадать в каждом символе блока $1$.
\end{itemize}

Нетрудно заметить, что в таком случае $\operatorname{dist}(s, t) = x + y$, $\operatorname{dist}(s, u) = x + z$ и $\operatorname{dist}(t, u) = y + z$, где $\operatorname{dist}$~--- расстояние Левенштейна.

Таким образом, осталось выбрать числа $x$, $y$ и $z$ таким образом, чтобы получились требуемые расстояния между строками. Для этого нужно решить систему из трех уравнений:

\begin{equation}
\left\{ \begin{aligned} 
  x + y &= a\\
  x + z &= b\\
  y + z &= c
\end{aligned} \right.
\end{equation}

Решение системы выглядит следующим образом:

\begin{equation}
\left\{ \begin{aligned} 
  x &= \frac{a + b - c}{2}\\
  y &= \frac{a + c - b}{2}\\
  z &= \frac{b + c - a}{2}
\end{aligned} \right.
\end{equation}

Если сумма $a + b + c$ четна, то $x$, $y$ и $z$ получатся целыми. В этом случае можно построить строки следующим образом: $s = a^x b^y b^z$, $t = b^x a^y b^z$, $u = b^x b^y a^z$, где $a$ и $b$~--- произвольные различные символы, а запись $c^p$ означает строку, равную символу $c$, повторенному $p$ раз.

Теперь рассмотрим случай, когда сумма $a + b + c$ нечетна. В этом случае построим аналогичную конструкцию, округлив $x$, $y$ и $z$ вниз. Заметим, что теперь каждое из трех расстояний Левенштейна на $1$ меньше, чем требуемое. Исправим это, дописав в конец каждой строки произвольный уникальный символ.

Также нужно не забыть о том, что строки должны быть непустыми, а $x$, $y$ и $z$ могут получиться равными нулю при $a = b = c = 0$. В этом случае достаточно вывести произвольные три непустые равные строки.

\end{tutorial}
