Разбор очного этапа краевой олимпиады 2017

Faster than light (A)

В задаче требовалось найти количество клеток 1х1 раскрашенного в клетку прямоугольника a на b таких, что они не пересекаются главной диагональю.
Посчитаем количество клеток, которые пересекает эта диагональ, а потом вычтем это число из a * b (здесь стоит заметить, что величина a*b может достигать 10^18, поэтому необходимо использование 64-битных типов переменных aka long long в С++).

Подсказки:
1) Главная диагональ пересекает ровно a клеток по вертикали и b по горизонтали, так как проходит от одного угла к противоположному. Какие-то из этих клеток посчитаны 2 раза.
2) Клетка пересекается, если диагональ проходит через её сторону или угол.
3) Понятно, что два раза посчитаны только те клетки, которые пересекаются по углу (так как они пересекаются и по "верхней" стороне, и по "боковой").
4) Чему равно количество таких клеток? Если диагональ проходит через угол клетки (x, y), то можно взять треугольник с вершинами (0, 0), (x, y), (0, y) и приложить его к точке (x, y), и тогда мы получим новую точку, являющуюся углом клетки (Это так, общие мысли)
5) Клеток, пересекаемых в углу, ровно НОД(a, b). Таким образом, ответ на задачу равен a * b - a - b + НОД(a, b).

Обнимашки (B)

В задаче требовалось заменить в правильной скобочной последовательности (ПСП) подстроки ")(" на подстроки "()" и вывести конечную строку. Просто каждый раз заменять каждую подстроку, которую мы видим, пока таких не останется, слишком долго - задачу требуется решить за один проход по строке.

Подсказки:
1) Из чего состоит ПСП? Либо из ПСП, обёрнутой в скобки(1), либо из двух ПСП, написанных подряд(2).
2) Ответ не может представляться двумя ПСП(2), так как на их стыке найдётся подстрока ")(".
3) Значит, нужно взять пустую строку и применять к ней операцию (1). Иными словами, ответом к ПСП длины n является ПСП из n/2 открывающих скобок и n/2 закрывающих. ((........))

Cписывание на ИЗО (С)

В задаче требовалось вывести координаты многоугольника из n вершин такого, что все его стороны целые.

Подсказки:
0) n <= 15, значит, можно вручную нарисовать 15 ответов и получить 100 баллов.
1) Для n = 4 решение очевидно - какой-нибудь прямоугольник(квадрат). Возможно, теперь с помощью этого можно получить решения для больших n.
2) Для n = 3 решением является треугольник с целыми сторонами. Самый простой способ - это взять какой-нибудь прямоугольный (пифагорову тройку, например, со сторонами 300, 400, 500) треугольник и бросить его на сетку координат.Возможно, теперь с помощью этого можно получить решения для больших n.
3) Давайте научимся делать из многоугольника с n вершинами многоугольник с n + 2 вершинами: просто "вогнём" один угол многоугольника внутрь. Если взять угол с сторонами, параллельными осям координат, то это очень просто, вы справитесь сами.
4) Можно придумать ещё парочку подобных преобразований, попробуйте сами.
5) Давайте научимся делать из многоугольника с n вершинами многоугольник с n + 4 вершинами, не трогая предыдущие вершины, а просто добавляя новые. Для этого возьмём сторону и "вырежем" из многоугольника клетку.
6) Заметим, что с помощью таких операций мы можем получить любое значение n из нужного диапазона.

Беспредельный драм-н-басс (D)

Задачу сложно переформулировать :) Будем обозначать подзадачи как (1) и (2) (без дополнительной операции и с ней соответственно).

Подсказки:
1) (1) Во сколько раз больше ритмов длины n + 1, чем ритмов длины n? Как получить из ритма длины n ритм длины n + 1?
2) (1) Ритмов длины n + 1 ровно в 2 раза больше, ведь можно взять любой ритм длины n и поднять/опустить любую руку.
3) (1) Соответственно количество ритмов длины n равно 2^n.
4) (2) Попробуйте воспользоваться методом динамического программирования.
5) (2) Пусть dp[n][a][b] - количество ритмов длины n таких, что после их проигрыша левая рука находится в позиции a, а правая в позиции b. Пусть a, b = 0 обозначает опущенную руку, a, b = 1 обозначает поднятую руку.
6) (2) Тогда переходы выглядят как dp[n + 1][!a][b] += dp[n][a][b], dp[n + 1][a][!b] += dp[n][a][b], dp[n + 1][0][0] += dp[n][1][1].

Математика для младшеклассников (Е)

Требуется найти p: a^p = b с точностью до 6 знаков после запятой.

Подсказки:
1) Давайте научимся возводить число в нецелую степень.
Будем рассматривать только 6 знаков после запятой в числе p. Представим его как 10^6 * p / 10^6.
Будем возводить число a в степень 10^6 * p, беря корень 10^6 степени каждый раз, когда число перестаёт влезать в ограничения. Взять корень можно бинпоиском по ответу.
А можно и попроще: в С++ существует функция pow(a, p), которая возвращает искомый результат в double.
2) a^x - возрастающая функция при a >= 1.
3) Воспользуемся бинпоиском по ответу.
4) Пусть l - левая граница, r - правая. Положим m = (l + r) / 2; если a^m < p, сдвинем левую границу, иначе правую. Будем делать так до тех пор, пока |r - l| > 0.000001.
5) Если вы знаете, что такое логарифмы, то можно решить уравнение a^p = b. Тогда p будет равно log(b) / log(a) по любому основанию.

Если у вас остались вопросы или вы - участник сложного тура, пишите мне в ВК : vk.com/id36828780 (Плешаков Алексей)