Задача 1. Красные человечки Заметим, что пересечение всех кубов – это прямоугольный параллелепипед. Будем задавать каждый параллелепипед шестью числами – x0, y0, z0, x1, y1, z1, где x0, y0, z0 – координаты вершины с минимальной суммой координат, а x1, y1, z1 – координаты вершины с максимальной суммой координат. Выберем очень большой параллелепипед, такой, чтобы все кубы полностью в нём лежали. Если взять параллелепипед, у которого x0 = y0 = z0 = -10000 и x1 = y1 = z1 = 10000, то все кубы будут лежать внутри него. Назовём этот параллелепипед ответом. Будем задавать каждый куб из входных данных тоже этими шестью числами. Нам даны x0, y0, z0 и d – длина ребра куба. Тогда для этого куба x1 = x0 + d, y1 = y0 + d, z1 = z0 + d. Переберём все кубы. Когда мы будем перебирать очередной куб, то будем отрезать от ответа ту область, которая не принадлежит текущему кубу. Пусть 6 чисел, задающие ответ – это xa1, ya1, za1, xa2, ya2, za2, а 6 чисел, задающие куб – это xi1, yi1, zi1, xi2, yi2, zi2. Заметим, что если xa1 меньше, чем xi1, то нижняя часть ответа не принадлежит очередному кубу, тогда её стоит отрезать, увеличив xa1 до xi1. Если же xa1 было больше, чем xi1, то ничего делать не надо. Это можно реализовать так: xa1 = max(xa1, xi1). То же самое стоит сделать и с оставшимися 5-ю числами: ya1 = max(ya1, yi1); za1 = max(za1, zi1); xa2 = min(xa2, xi2); ya2 = min(ya2, yi2); za2 = min(za2, zi2). Перебрав все кубы, мы отрезали от нашего ответа всё, что не принадлежит хотя бы одному из кубов, тогда в ответе остался параллелепипед, являющийся пересечением всех кубов. Заметим, что если xa1 не меньше, чем xa2 или ya1 не меньше чем ya2, или za1 не меньше, чем za2, то площадь пересечения равна нулю. Если она не равна нулю, то её можно посчитать по формуле площади прямоугольного параллелепипеда, как (xa2 – xa1) * (ya2 – ya1) * (za2 – za1). Это решение работает за O(n) памяти, где n – количество кубов и O(n) или O(1) памяти в зависимости от реализации. Задача 2. Первоклассник Робин Гуд Пусть нам надо набрать Х очков. За один бросок мы можем набрать любое количество очков не больше 20, любое количество очков не больше 40 и кратное двум – попав в удвоение сектора, любое количество очков не больше 60 и кратное трём – попав в утроение сектора, а также 50 очков – попав в центр мишени. Будем перебирать все три броска, считая, что второй бросок был не хуже первого, а третий – не хуже второго. Если сумма очередных трёх бросков равна Х, то мы нашли новую комбинацию, тогда увеличим счётчик количества комбинаций на один. Осталось посчитать, сколько новых перестановок мы нашли. Заметим, что если все три броска одинаковы (все они набирают одинаковое количество очков), то мы нашли лишь одну новую перестановку. Если из этих трёх два броска равны (1-й и 2-й или 2-й и 3-й), то мы нашли 3 перестановки, например если три броска набирают 10, 10 и 16 очков соответственно, то может быть 3 перестановки: (10, 10, 16), (10, 16, 10) и (16, 10, 10). Если все три броска различны, например, они набирают 10, 16 и 30 очка соответственно, то мы нашли 6 перестановок. В данном случае это: (10, 16, 30), (10, 30, 16), (16, 10, 30), (16, 30, 10), (30, 10, 16) и (30, 16, 10). Увеличим счётчик количества комбинаций на соответствующее число и продолжим перебор. Когда мы всё перебрали, то если мы не нашли ни одной комбинации, то число Х нельзя получить с помощью трёх дротиков, иначе можно и мы посчитали количество комбинаций и перестановок, которыми можно получить Х очков. Время работы O(n^3), где n – количество различных результатов одного броска. Так как n < 100, то решение будет работать очень быстро. Данное решение тратит О(1) памяти. Задача 3. Логическая схема Будем хранить двумерный массив символов, который будет показывать, что находится в соответствующей клетке схемы. Когда мы будем считывать строки, задающие схему, запомним два числа х1 и у1 – координаты символа ‘?’. Запустим DFS, где в качестве вершины будем передавать координаты клетки. Изначально мы запускаемся от клетки со знаком вопроса, то есть от x1 и y1. Если в клетке, которую мы рассматриваем на очередном шаге DFSа записана какая-то переменная, то мы возвращаем её значение. Если в одной из соседних клеток, не являющейся предыдущей (предыдущая клетка – та клетка, из которой мы пришли в текущую), стоит символ ‘-‘, ‘|’ или ‘+’, то запускаемся от этой клетки. Иначе значение нашей клетки получено в результате логической операции И или ИЛИ. Тогда мы рекурсивно запускаемся от двух клеток, координаты которых можно посчитать, обработав наличие отрицаний. Этот алгоритм стоит запустить для каждой строчки, задающей значения переменных. Заметим, что граф, по которому мы запускаем поиск является деревом, когда DFS будет работать корректно. Время работы решения в худшем случае О(n * m * k), где n, m – размеры поля, а k - количество строк со значениями переменных. Эта задача, на мой взгляд, была самой сложной. Задача 4. Словесное ориентирование Пусть мы ищем строку S. Будем перебирать все клетки и направления в том порядке, в котором нас просят вывести ответ. Если очередная клетка с направлением нам подходят, то запомним, что мы нашли хотя бы один ответ, и выведем его. Если в процессе алгоритма ни один ответ не найдет, выведем «not found». Как проверять, что текущая клетка с направлением нам подходит: Заведём вектор скорости. Если направление - N, то он равен (0, -1), потому что при движении на север координата х остаётся неизменной, а у – уменьшается. Если направление - NE, то вектор равен (1, -1) и так далее. Пусть мы наша клетка имеет координаты (x0, y0). Будем записывать символ в текущей клетке (если клетка его содержит) в конец некоторой строки и перемещаться на вектор скорости, пока не выйдем за границы поля. Если строка S является её префиксом, то клетка с кордитами (x0, y0) и соответствующим направлением нам подходит, иначе – нет. Проверка одной клетки с направлением работает за О(n), где n – размер таблицы. Всего у нас n^2 клеток и 8 направлений, тогда решение работает за O(8 * n^3). И тратит О(n^2) памяти. В этой задаче у участников, использующих язык C++, могли возникнуть трудности в реализации, так как стандартный оператор считывания строк (std::cin) считывает строки до первого пробела или перевода строки. Можно было воспользоваться функцией getline. Чтобы с его помощью прочитать строку s надо написать getline(cin, s); |
| |||||||||