Довжина найбільшого числа — \(\left \lceil \frac{n}{k} \right \rceil\).
Будемо будувати найбільше число зліва направо. При цьому підтримуватимемо \(c\) — кількість чисел, які ще можуть бути найбільшим. Початково \(c\) — кількість чисел завдовжки \(\left \lceil \frac{n}{k} \right \rceil\). \(c = n \% k\), якщо це значення ненульове, інакше \(c=k\).
\(\left \lceil \frac{n}{k} \right \rceil\) разів треба дописати до поточного найбільшого числа якомога меншу цифру. Маємо \(c\) чисел, які поки що є найбільшими. Візьмемо \(c\) найменших невикористаних цифр. Допишемо їх до цих найбільших чисел. Нехай найбільша цифра, яку ми щойно використали — \(d\), і ми використали її \(c'\) разів. \(c'\) буде новим значенням \(c\). Виведемо цифру \(d\).
Якщо Кирило першим ходом узяв паличку завдовжки \(a_i\), то Змій повинен узяти паличку завдовжки \(a_j\), щоб незалежно від того, яку третю паличку завдовжки \(a_k\) вибере Кирило, з них можна було скласти невироджений трикутник. Для всіх \(k \ne i, k \ne j\) повинні виконуватися нерівності трикутника: \(a_i < a_j + a_k, a_j < a_k + a_i, a_k < a_i + a_j\). Перепишемо ці нерівності так: \[a_j > a_i - a_k, a_j > a_k - a_i, a_j < a_k + a_i.\]
Нехай найкоротша паличка, крім \(i\)-ої, має довжину \(a_{min}\), а найдовша — \(a_{max}\). Перевіримо, чи існує таке \(j\), що \[a_j > a_i - a_{min}, a_j > a_{max} - a_i, a_j < a_{min} + a_i.\] Якщо існує, то таке \(j\) і буде виграшним ходом для Змія.
Нерівності \((1)\) мають виконуватися для \(k \ne j\), а в перевірці ми цього не забезпечуємо й маємо сильнішу умову \((2)\). Можна просто окремо перевірити, чи виграє Змій якщо візьме паличку \(a_{min}\) чи \(a_{max}\).
Однак можна показати, що цих додаткових перевірок не потрібно. Для цього достатньо довести такі дві леми.
Якщо Змій може виграти, взявши паличку \(a_{min}\), то він може виграти, взявши паличку \(a_{max}\).
Якщо Змій може виграти, взявши паличку \(a_{max}\), то для неї будуть виконуватися нерівності \((2)\).
Доведення залишаємо вправою.
Скористаємося підходом динамічного програмування. Детальніше про динамічне програмування можна дізнатися у відео.
Нехай \(dp[i][j][c]\) — мінімальна кількість клітинок, яку повинна подолати Коза, щоб опинитися в клітинці \((i, j)\), відвідавши \(c\) клітинок з травою. Зі стану \((i, j, c)\) є перехід у стан \((i+1, j, c)\), якщо в клітинці \((i+1, j)\) нема трави, і в стан \((i+1, j, c + 1)\) в іншому разі. Так само є переходи в клітинку \((i, j+1)\).
Відповіддю на задачу є \(\min_{i, j} dp[i][j][k]\).
Для кожного запиту будемо підтримувати кінці шляху \(a\), \(b\). Початково це дві перші вершини шляху.
Розглядаємо відвідану Колобком вершину \(p\).
Якщо \(p\) лежить на шляху від \(a\) до \(b\), то нічого не порушується, у цьому разі нічого не робимо.
Якщо \(b\) лежить на шляху від \(a\) до \(p\), то \(p\) стає новим кінцем шляху, присвоюємо \(b:=p\).
Якщо ж \(a\) лежить на шляху від \(b\) до \(p\), то аналогічно \(a:=p\).
Якщо не виконується жодна з трьох вищенаведених умов, то Колобок не міг відвідати на одному шляху вершини \(a\), \(b\) й \(p\). У цьому разі виведемо
Ni.
Якщо ми розглянули всі вершини й не вивели Ni, то
Колобок міг їх відвідати. Тоді виведемо Tak.
Залишилося навчитися перевіряти, чи лежить деяка вершина \(x\) на шляху від \(a\) до \(b\). Підвісимо дерево за довільну вершину. Нехай \(c\) — найменший спільний предок вершин \(a\) й \(b\). Критерій того, що \(x\) лежить на шляху від \(a\) до \(b\) — \(c\) є предком \(x\) і (\(x\) є предком \(a\) або \(x\) є предком \(b\)).