Seyaua's blog

By Seyaua, 14 years ago, In Russian
Задача A. Определите цвет

Здесь все понятно. Достаточно рассмотреть несколько случаев. Первый — когда расстояние от 
точки до начала координат — целое число, тогда ответ black. В противном случае, пусть d 
- это расстояние от нашей точки до начала координат. Тогда будем работать с [d]. Теперь 
осталось два случая: 1) если наша точка лежит в 1-ой, или 3-ей четверти; 2) точка лежит во 
2-ой, либо 4-ой четверти. В случае 1) имеем, если [d] нечетно, то ответ white, иначе 
black; в случае 2) если [d] четно, то ответ white, иначе black. Подразумевается, что 
[d] — целая часть d.

Задача B. Перекрашивания

Первое, что надо заметить, так это то, что на i-ом шаге все перекрашенные клетки будут 
лежать в прямоугольнике с вершинами в клетках (i,i), (n-i,m-i) (если считать, что (1,1) - 
левая верхняя клетка, а (n,m) — правая нижняя). Тогда отсюда уже следует решение: нужно 
подсчитать количество клеток такого типа, что минимальное расстояние до стороны в точности 
равняется x. То есть для клетки (a,b) должно выполняться 
min(min(a, b), min(n - a + 1, m - b + 1)) = x.

Задача C. Берляндская площадь

Идейно эта задача не очень сложная, но было много хитрых случаев. Авторское решение предполагало следующую идею. Сначала заметим, что наше множество окружностей на плоскости может быть несвязным. Тут есть два случая, когда есть хотя бы одна точка пересечения окружностей и когда нет ни одной. Если их нет, то ответ N+M+1. Иначе, если есть хотя бы одна точка пересечения, то мы можем удалить некоторые окружности таким образом, чтобы оставшаяся фигура из окружностей была связной. Тогда для этой фигуры можно применить формулу Эйлера. Таким образом, нам здесь нужно посчитать количество точек пересечения и количество дуг-ребер. Нетрудно видеть, что каждая точка пересечения добавляет две дуги. Таким образом, мы можем найти количество частей, на которые разделилась плоскость без удаленных окружностей. Теперь достаточно заметить, что каждая удаленная окружность добавляет ровно 1 к ответу. Весь вопрос в том, чтобы посчитать, сколько точек пересечения. Это можно сделать за O(N+M), если считать для каждой окружности, точки пересечения, которые принадлежат ей. Для этого достаточно заметить, что все окружности, с которыми наша окружность пересекается будут иметь радиусы l, l+1, ..., r. Также, с некоторыми из этих окружностей наша окружность будет иметь не две точки пересечения а одну. Это необходимо учесть в решении. После этого остается лишь аккуратно реализовать эту идею. 

Задача D. Интересная последовательность

Здесь нужно было погенерировать разные последовательности, которые могут получаться и внимательно смотреть на полученные значения. Основное наблюдение, это то, что каждое из чисел, которые встречаются в последовательности имеет вид 12k + 12m, при этом это число может встречаться лишь на позиции (k + m + 1). Теперь, когда известен общий вид, можно по методу математической индукции доказать, что на x-ой позиции могут встречаться все числа вида 12k + 12m, такие что, k + m + 1 = x. После этого можно было реализовать простое в написании решение за O(N3), где N — длина входного числа. Для этого перебираем все x от 1 до 600 и проверяем, существуют ли такие k и m, что k + m + 1 = x и 12k + 12m = A. Но также есть и решение со сложностью O(N2).

Задача E. Таблица из чисел

Первое, что должно было броситься в глаза, это то, что клеток, изначально не пустых — совсем мало. Из ограничений следует, что всегда есть пустая строка либо пустой столбец. Без ограничений общности можем считать, что у нас есть пустая строка и она последняя. Тогда выберем какой-либо столбец (к примеру, последний) и зафиксируем его одновременно с пустой строкой. Тогда по оставшейся таблице размера (n - 1) × (m - 1) клетки в последнем столбце и в последней строке заполняются однозначно. Но есть одно замечание, в последнем столбце уже стоят какие-то числа. Тогда нам надо для каждой строки, кроме последней подсчитать, сколько существует вариантов этой строки, таких, что произведение чисел в этой строке равно -1. В авторском решении, эта часть считалась при помощи динамического программирования. После этого нужно перемножить полученные ответы для каждой строки. Тогда ответ на задачу — это полученное произведение, либо 0 — если сумма n + m нечетна.


Разбор задач был подготовлен мной и sdya
  • Vote: I like it
  • +5
  • Vote: I do not like it

| Write comment?