Задача A
Один из возможных путей решения задачи - сравнивать каждый листик с уже взятыми. Если он совпал с одним из них, тогда его не нужно брать. Поскольку порядок листьев неважен, можно просто отсортировать их (например, как пары строк) и удалить одинаковые листья.
Задача B
Задача заключается в нахождении количества троек (x, y, z), таких что 0 <= x <= a, 0 <= y <= b, 0 <= z <= c и 0.5 * x + y + 2 * z = n. Перебор всех троек работает долго, однако все возможные значения x и y, удовлетворяющие неравенствам 0 <= x <= a, 0 <= y <= b перебрать можно. Когда x и y фиксированы, значение z определяется однозначно. Получаем решение за O(a*b).
Задача C
Самое простое решение - перебрать все дни с 1 до n и для каждого дня проверить, что он покрывается ровно одним отрезком [ai, bi]. Если обнаружен день, который покрывается меньшим или большим количеством отрезков, выведите этот день.
Задача D
Будем называть корабли, созданные с самого начала, ''кораблями первого поколения''. Когда корабль первого поколения достигает планеты и на ней строятся новые корабли, будем называть их ''кораблями второго поколения'' и т.д.
Докажем, что первое столкновение произойдет между двумя кораблями второго поколения, движущимися навтречу друг другу. Действительно, корабли первого поколения движутся в разных направлениях (никакие три точки не лежат на одной прямой), поэтому они не могут столкнуться. Если корабль первого поколения столкнулся с кораблем второго поколения, линии их движения образуют треугольник OAC, где O - первая планета, A - планета, на которой был создан корабль второго поколения, C - точка столкновения. Но ясно, что OA + AC > OC, и корабли движутся с одинаковой скоростью, поэтому такое столкновение не может произойти.
Если говорить о короблях третьего поколения, то они просто не могут быть созданы! Предположим, корабль с первой планеты достиг планеты A, затем корабль с планеты A достиг планеты B. Но в силу неравенства треугольника, корабль с первой планеты достигнет планеты B раньше, на планете B будут созданы новые корабли, один из них будет отправлен на планету A и столкнется с кораблем, движущимся от A к B.
По аналогичным причинам два корабля не могут столкнуться, если один из них движется от A к B, а другой - от C к D. Корабли, движущиеся от A к C и от C к A, столкнутся раньше.
Таким образом, решение заключается в том, чтобы для каждой пары планет A, B посчитать периметр треугольника OAB и выбрать минимум.
Задача E
Существует много возможных способов разбиения строки. Один из них - разбить ее на части длиной n / k и n / k + 1, если n не делится на k. Здесь n - длина заданной строки. Если длины частей не меньше a и не больше b, ответ найден. Иначе решения не существует.
Задача H
Ответ может быть достаточно большим, потому что он растет экспоненциально с ростом n, но он умещается в int64. Действительно, существует 10 способов выбрать первую цифру, потом 1 или 2 способа выбрать вторую, 1 или 2 - третью и т.д. Поэтому количество способов не превосходит 10· 2n - 1.
Задачу можно решить методом динамического программирования. Пусть dij - количество способов получить первые i цифр корректного номера с i-й цифрой, равной j. Из такой части номера можно получить часть размера i + 1 с (i + 1)-й цифрой, равной (j + ai + 1) / 2 или (j + ai + 1 + 1) / 2, где ai - i-я цифрма Машиного номера. Поэтому если мы уже посчитали dij для всех j, то можно вычислить di + 1, j.
Не забудьте вычесть 1, если Маша может получить свой собственный номер. Это случится в том случае, когда каждые две последовательные цифры в заданном номере отличаются не более, чем на 1.
Задача J
Во-первых, если замощение возможно, оно единственное. Рассмотрим самую верхнюю-левую клетку (x, y), которая не вырезана. Если она черная, замощение невозможно. Если она белая, посмотрим на следующую клетку (x, y + 1). Если она вырезана, единственный способ положить триминошку - положить ее вертикально. Иначе мы обязаны положить триминошку горизонтально, потому что если мы положим ее вертикально, мы не сможет покрыть следующую черную клетку (x, y + 1). Эти рассуждения дают алгоритм решения.
Четырех символов a, b, c, d всегда достаточно для представления замощения, потому что триминошка может иметь общие стороны не более чем с тремя триминошками, расположенными левее или выше. Поэтому даже если все эти 3 триминошки обозначены 3 различными символами, следующую триминошку можно обозначить 4-м символом.
А основная идея моего решения такая. Для каждой точки будем искать битовую маску по прямоугольникам, в которой на соответствующей позиции стоит 0, если точка лежит внутри прямоугольника, и 1 иначе. Для этого найдём:
1) маску множества прямоугольников, у которых правая граница левее текущей точки;
2) ... у которых левая граница правее текущей точки;
3) ... верхняя ниже;
4) ... нижняя выше.
Объединив эти маски, получим искомую.
А найти, к примеру, маску 1) можно так (остальные аналогично). До обработки точек отсортируем все прямоугольники по возрастанию правой границы и занесём в какой-нибудь массив. Теперь, когда задаётся некоторая точка, нас интересует битовая маска какого-то количества первых прямоугольников из этого массива (какого именно - можно найти бинарным поиском). Чтобы быстро искать необходимую маску, хотелось бы сразу запомнить маски для каждого префикса этого массива, но это займёт слишком много памяти, поэтому запоминаем маску для каждого префикса с длиной, кратной 1000. А теперь уже несложно найти маску для любого префикса.
Имея объединение этих битовых масок, можно быстро найти первый 0 в ней - это и будет искомый прямоугольник (прямоугольники сразу отсортированы по z-координате). Для удаления прямоугольника нужно пройтись по всем запомненным битовым маскам и в соответствующих ему позициях поставить 1.
Интересно, что это решение должно работать даже в случае, если выстрелы - это тоже прямоугольники :)
А как в задаче J замостить доску
..wbw..
...w...
wbwbwbw
...w...
..wbw..
используя только 4 символа?
I got accept problem E.Anfisa the Monkey. and I found corner case of my code. corner case :5 1 2 abcdefghi
My submission