Тренировка #15 [Меньшиков]

[Условия задач]                   [Список тренировок]

15A. Игра с калькулятором
[calcgame]
Пожалуй самая сложная задача на тему последовательности в данном задачнике. Самый интересный момент – это как определить, что нужно выводить “Impossible”. Один из подходов – искать решение, пока позволяет TLE, и если такого ответа не найдено за отведенное время, то считаем, что решений нет. Как показывает практика, если асимптотика решения допустимая, то такой подход “канает”. Но все равно остается чувство сомнения и неуверенности. Вот чтобы такого чувства не было, сводим решение к поиску остатков от деления. Решение соответствует первому разбору на эту задачу.
15B. Площадь треугольника
[tria-abm]
Очень интересная задача. Немножко поколдовав сводим решение к бинарному поиску по ответу.
15C. Формирование поезда
[train-ab]
Пожалуй самая сложная задача на ДП, если пытаться решить способом, который предложил Никита Рыбак. Это способ, в котором все ответы на подзадачи для заданной длины храним в матрице [40][40][2].
15D. Стена
[wall]
Очередная задача на выпуклую оболочку. В предложенной реализации был использован алгоритм Грехема-Эндрю. Реализация самого алгоритма, была взята здесь. Она потрясла меня своей лаконичностью.
15E. Семечки
[seeds]
Признаюсь долго придумывал решение. Хотя задача по хорошему вообще несложная. И отсечение перебора довольно легко придумать.
15F. Умножение многочленов
[polymul]
Такие задачи для нас уже не должны представлять серьезной угрозы =).

[Все решения]

P.S: 17 января 2011 года в 02:43:58 по серверному времени была зачтена последняя нерешенная задача. Ну чтож, СПАСИБО автору за столь шикарный задачник.