A. Бросок кубика

Пусть максимум из очков Якко и Вакко -- a. Тогда Дот выиграет, если выбросит не меньше a очков. Вероятность этого равна (6 - (a-1)) / 6. Поскольку a принимает всего 6 значений, ответы можно просто вычислить вручную.

B. Бегущий студент

Общее время, которое понадобится студенту, если он выйдет на i-й остановке, равно t_i = b_i + s_i, где b_i = x_i / v_b -- время, которое он проедет на автобусе, а -- время, которое он пройдет от остановки пешком. Нужно выбрать индексы с минимально возможным t_i, а среди них -- индекс с минимальным s_i, то есть, с максимальным b_i, то есть (поскольку координаты остановок упорядочены) с максимальным i.

Из-за возможных проблем с точностью условие t_i = t_j нужно записывать в виде |t_i - t_j| < ε для достаточно малого ε.

C. Числа Хексадесимал

Полный перебор чисел от 1 до n не пройдет по времени.
Заметим, что все хорошие числа состоят из не более, чем 10 цифр, а каждая цифра равна 0 или 1. Значит, нужно проверить 2¹⁰ бинарных строк. Каждая из них является числом от 1 до 2¹⁰ - 1 в двоичной записи. Получаем такой алгоритм: для каждого числа от 1 to 2¹⁰ - 1 запишем его двоичную запись, прочитаем ее так, как будто бы она была десятичной, и сравним результат с n.

D. Сколько деревьев?

Пусть t_nh -- число бинарных деревьев поиска высоты h на n вершинах. Выведем рекуррентное соотношение на t_nh. t₀₀ = 1 (пустое дерево), а при i>0 t_i0 = t_0i = 0.

Возьмем любое дерево высоты h на n вершинах. Пусть в корне записано число m, 1 ≤ m ≤ n. Левое поддерво является бинарным деревом поиска на m-1 вершине, а правое -- на n-m вершинах. Максимум из их высот должен быть равен h-1. Рассмотрим два случая:
1. Высота левого поддерева равна h-1. Таких деревьев t_{m - 1, h - 1}. Правое поддерево в этом случае может иметь любую высоту от 0 до h-1 -- всего таких деревьев . Поскольку правое и левое поддеревья мы выбираем независимо, получаем вариантов.
2. Высота левого поддерева меньше h-1. Таких деревьев ; правое поддерево в этом случае должно иметь высоту h-1, и всего получается вариантов.
Итак, рекуррентная формула такая: .

Значения t_nh вычисляются при помощи динамического программирования. Ответ на задачу -- .

E. Интересный граф и яблоки

Забавное кольцо состоит из n вершин и n ребер. Если есть еще какое-то ребро, кроме этих n, то вершины, которые оно соединяет, принадлежат более, чем одному циклу. Итак, интересный граф -- это просто забавное кольцо.
Граф является забавным кольцом если и только если выполнены следующие условия:
A1. Степерь каждой вершины равна 2.
A2. Граф связен.
 Теперь выясним, когда граф не является забавным кольцом, но может быть приведен к такому виду добавлением ребер. Очевидные необходимые условия:
B1. m < n.
B2. В графе нет циклов.
B3. Степени вершин не превосходят 2.
 Будем добавлять ребра так, чтобы эти условия сохранялись, а последовательность ребер была лексикографически минимальна. То есть, добавим ребро (i,j) такое, что:
1. i и j принадлежат разным связным компонентам. (Иначе нарушится B2).
2. Степени вершин i и j меньше 2. (Иначе нарушится B3).
3. Пара (i,j) лексикографически минимальна.
  Посмотрим, что получится, когда мы больше не сможем добавить ребро. Поскольку циклов нет, каждая связная компонента -- дерево, и в нем найдется вершина степени меньше 2. Если есть две связные компоненты, то их можно соединить ребром, не нарушив условий B1-B3. Итак, граф связен, не имеет циклов, и степень каждой вершины равна 2. Это значит, что полученный граф -- простая цепь, и можно соединить ее концы, получив забавный цикл.
 
 Итак, алгоритм:
 1. Проверить условия A1-A2. Если они выполнены, вывести "YES" и 0.
 2. Проверить условия B1-B3. Если они не выполнены, вывести "NO".
 3. Вывести "YES" и n-m.
 4. Добавить ребра описанным способом. При добавлении ребра (i,j) вывести "i j".
 5. Найти вершины i и j степени меньше 2 (они могут совпасть, если n=1). Вывести "i j".