359A - Таблица

Давайте рассмотрим все ячейки, которые расположены в первой строке. Очевидно, что если хотя бы одна из них хорошая, то ответ равен двум. Аналогично, если хорошая ячейка расположена в первом столбце, либо в последней строчке или в последнем столбце, ответ также два. Иначе, ответ равен четырем.

Авторское решение: 4968279

359B - Перестановка

Ответом будет являться немного изменненая перестановка 1, 2, ..., 2n. Для каждого 1 ≤ i ≤ k поменяем местами числа 2i - 1 и 2i. Не трудно проверить, такая перестановка будет хорошей.

Авторское решение: 4968385

359C - Простое число

Очевидно, что ответ это x^v. Пусть sum = a₁ + a₂ + ... + a_n. Тогда рассмотрим все числа вида s_i = sum - a_i. Тогда, чтобы узнать, чему равно v мы поступим так: Рассмотрим систему счисления по основанию x, где s_i — разряд. Тогда, когда мы выполним все переносы по степеням, нужно найти минимальный разряд, в котором стоит не ноль. Тогда v будет равно именно этому разряду. Чтобы выполнить переносы, можно было бы поступить так. Рассмотрим последовательность степеней как убывающую последовательность. Теперь будем выполнять следующее "пока можно". Возьмем минимальную степень v, посчитаем количество слагаемых cnt, которые имеют такую же степень. Если cnt кратно x, тогда мы их заменим cnt / x слагаемых вида v + 1. Поскольку последовательность степеней была убывающей, мы можем просто приписать их в конец. Если же cnt не кратно x, тогда мы нашли нужную минимальную степень v. Также стоит не забывать, что v = min(v, sum).

Авторское решение: 4968346

359D - Пара чисел

Достаточно очевидное замечание: если пара (l, r) удовлетворяет условию 1, тогда min(l, r) = НОД(l, r). Где min(l, r) — минимум на подотрезке (l, r). Аналогично, НОД(l, r) — НОД всех чисел на подотрезке (l, r). Посчитаем структуру данных, которая позволит нам быстро отвечать на запросы минимума на отрезке и НОД на отрезке, например за O(1). Это можно достичь используя структуру данных Sparce Table. Конечно, на запрос НОД(l, r) мы не сможем отвечать за O(1), однако будет достаточно быстро работать. Также стоит отметить, что решение, которое использует дерево отрезков, очень вероятно получит TL. Воспользуемся бинарным поиском для того, чтобы найти максимальное возможное значение r - l:

lf = 0;  //левая граница поиска
rg = n;  //правая граница поиска
while (rg - lf > 1) {
  int mid = (lf + rg) / 2;
  if (ok(mid))   //ok(mid)
    lf = mid;
  else
    rg = mid;
}

ok(mid) — функция, которая определяет, существует ли отрезок который удовлетворяет условию min(l, r) = НОД(l, r) и mid = r - l. Если таковой есть, то обновим границы бинпоиска. После того, когда мы узнаем величину r - l восстановить ответ не составит труда.

Здесь есть информация про Sparce Table

Авторское решение: 4968587

359E - Порядок

Запустим рекурсивную функцию, которая включит свет во всех комнатах, где это возможно. Кроме того, она посетит все комнаты, среди тех, которые возможно посетить. Пусть эта функция называется paint(x, y), где x, y — текущая комната. Эта функция будет работать так: Посмотрим во все 4 направления. Если в заданном направлении идти можно по правилу 3 из условия, и клетка (nx, ny) еще не посещена, рекурсивно пойдем именно в эту клетку. Кроме этого, будем включать свет везде, где можно. Если мы не посетили нашей функцией некоторую клетку, где есть свет, то ответ NO. Иначе ответ есть. Далее с помощью обхода в ширину посчитаем для каждой комнаты, в которой включен свет, расстояние от старта, причем разрешается ходить только по тем комнатам, где свет горит. Пусть для комнаты (x, y) это значение равно dist(x, y). Теперь запустим похожую рекурсивную функцию, которая будет выключать свет. Эта функция будет работать так: Посмотрим во все 4 направления. Если в заданном направлении в комнате (nx, ny) еще горит свет, а dist(nx, ny) > dist(x, y), то запустим нашу функцию рекурсивно от (nx, ny), а потом вернемся в текущую комнату. Если такой соседней клетки нет, выключим свет. Более подробно детали можно изучить в моем решении.

Авторское решение: 4968657