Olymp6
.pdf
Ёжики
Карта леса задана массивом NxM. Точки - деревья, звездочки - ёжики.
Посчитать, сколько ёжиков в лесу.
Входные данные
Вводятся два натуральных числа N, M (2 ≤ N, M ≤ 200) И матрица из * и .
Выходные данные
Требуется вывести одно число - количество звёздочек в массиве.
Мат-мех 2015 |
41 |
Ёжики. Статический массив.
Как оптимизировать?
Сразу проверять, уже при чтении
Мат-мех 2015 |
42 |
Ёжики. Динам. массив
То же самое, но с динамическим массивом
Мат-мех 2015 |
43 |
Ёжики. Лаконично.
Мат-мех 2015 |
44 |
Ломаные
На окружности отметили N точек и пронумеровали их последовательно числами от 1 до N. Требуется найти количество различных простых ломаных с вершинами в некоторых из отмеченных точек и с концами в точках с номерами i и j.
Ломаная называется простой, если она не проходит дважды через одну точку (и не содержит самокасаний и самопересечений).
Входные данные
Вводятся три натуральных числа N, i, j (2 ≤ N ≤ 2 000, 1 ≤ i < j ≤ N)
Выходные данные Требуется вывести остаток от деления количества ломаных на 109.
Мат-мех 2015 |
45 |
Разбор
Задача на динамическое программирование.
Будем в дальнейшем считать, что нумерация от 0 до n-1. Фиксируем n, тогда для пары вершин (S, T) ответ будет такой же,
как и для пар (S-1, T-1), (S-2, T-2), ...(0, T-S)
Мат-мех 2015 |
46 |
Пусть a[М][K] - количество ломанных между вершинами 0 и К на окружности с М точками. 0<K<M
Посчитаем сначала кол-во только тех ломанных, второе звено которых равно L, где 0<L<K.
Тогда среди их звеньев(начиная с третьего) не могут встречаться вершины меньшие L-1, ведь иначе самопересечение
Эти точки удаляем с окружности Таким образом, искомое число равно количеству ломаных между
вершинами L и К на окружности из M-L вершин, что равно по определению a[M-L][K-L]
Мат-мех 2015 |
47 |
Пусть теперь M>L>K. Заметим, что a[M][K]=a[M][M-K]
По тем же соображениям случай L>K сводится к уже разобранному случаю L<M-K, откуда получается ответ: a[L][M+K-L].
Просуммировав результаты по L, получим a[M][K].
Рекурентная формула:
a[M][K]= 1+(a[M-1][K-1]+...+a[M-K+1][1])+ (a[M-1][M-K-1]+...+a[K+1][1])
Мат-мех 2015 |
48 |
Ломаные. Последнее улучшение.
Мат-мех 2015 |
49 |
Мат-мех 2015 |
50 |