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

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

9A. Диалог компьютеров
[dialogue]
Первая задача на моделирование процесса. Большое, немного непонятное условие(на первый взгляд), поэтому советую его читать несколько раз. Тщательно продумываем структуры данных перед тем, как начинать писать.
9B. Бросание кубика
[die]
Первая задача на теорию вероятностей. Для начала вспомним правило сложение вероятностей, и когда его нужно применять. Здесь изложена суть. Понятно, что если с двух бросков шестигранного кубика было набрано 8 очков, то это могло случиться, если выпала одна из комбинаций: 2-6, 3-5, 4-4, 5-3, 6-2. Находим вероятность каждой из этой комбинации и плюсуем в итоговую.

9C. Игра с монетами
[coingame]
Пожалуй самая сложная из первых 9 тренировок, от этого самая интересная задача на антагонистические игры. Решаем методом двумерного ДП. Заполняем матрицу ответов справа налево, сверху вниз. На каждом шаге находим оптимальный среди ходов, когда оставляем K неизменным, либо уменьшаем до значения не меньше 1.
9D. Бассейн реки
[basin]
Любопытная задача. DFS+ConvexHull. В качестве алгоритма построения выпуклой оболочки можно использовать, рассмотренный ранее алгоритм Джарвиса, либо быструю оболочку. Я выбрал второй вариант.
9E. Ближайшее число
[nearnum]
Задача, над которой стоит подумать. Надеюсь Вы это читаете уже после таких раздумий. Первое, что при пришло в голову пускать bfs из каждой нулевой точки. Оцениваем сложность: O(N^4). Что-то совсем плохо. Думаем дальше. Можно обойтись одним bfs и последовательно находить нулевые точки, достижимые на 0, 1,.. i-ом шаге. Если какая-то нулевая точка была достигнута на каком-то шаге – она выбывает из рассмотрения. Для этого в начальный момент помещаем в очередь рассмотрения все ненулевые клетки. Затем по мере опустошения этой очереди формируем новую очередь нулевых точек, которые будем рассматривать на следующем шаге. И т.д. пока нулевые точки не закончатся. Не забудьте грамотно рассмотреть случай, когда существует несколько равноудаленных ненулевых точек.
9F. Прямоугольное деление
[rectpart]
Здесь нужно рассмотреть прием построения сетки, который мы использовали в задаче 6D. Затем последовательно рассмотреть каждый прямоугольник сетки и определить к каким начальным прямоугольниках он относится. Затем пускаем dfs/bfs, пользуясь правилом, что если два смежных прямоугольника сетки принадлежат одному набору начальных прямоугольников, то они образуют одно пространство(без перегородок)


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