Найти максимальное количество вариантов вырубки деревьев

@Lolu · Регистрация: 26.04.2016

Author24 — интернет-сервис помощи студентам

В ряд посажены N деревьев, расстояние между соседними деревьями одинаковое.
Нужно найти максимальное кол-во вариантов вырубки, при условии что должно остаться M деревьев, и после вырубки соседние деревья должны находится на одном расстоянии.
Есть пример:
Входные данные
5 3
Выходные данные
4
Я просто не могу представить как можно 4 раза вырубить деревья, так что бы осталось 3, на одинаковом расстоянии.
Допустим в числовом виде:
1 2 3 4 5 деревьев

1 2 3
2 3 4
3 4 5

1 3 4 - не правильно по идее ?
1 2 5 - и так вроде бы по условию не то что нужно.

@Puporev · 26.11.2018, 10:26

1 2 3
2 3 4
3 4 5
1 3 5

@кот Бегемот · 26.11.2018, 17:10

Олимпиадная задача 10-летней давности. Решений в сети - куча, в том числе и с разбором.

@Lolu 0 / 0 / 0 Регистрация: 26.04.2016 Сообщений: 5
		1
	Найти максимальное количество вариантов вырубки деревьев 25.11.2018, 23:09. Показов 871. Ответов 2 Метки нет (Все метки) В ряд посажены N деревьев, расстояние между соседними деревьями одинаковое. Нужно найти максимальное кол-во вариантов вырубки, при условии что должно остаться M деревьев, и после вырубки соседние деревья должны находится на одном расстоянии. Есть пример: Входные данные 5 3 Выходные данные 4 Я просто не могу представить как можно 4 раза вырубить деревья, так что бы осталось 3, на одинаковом расстоянии. Допустим в числовом виде: 1 2 3 4 5 деревьев 1 2 3 2 3 4 3 4 5 1 3 4 - не правильно по идее ? 1 2 5 - и так вроде бы по условию не то что нужно. 0

@Puporev Почетный модератор 64300 / 47595 / 32743 Регистрация: 18.05.2008 Сообщений: 115,181
	26.11.2018, 10:26	2
	1 2 3 2 3 4 3 4 5 1 3 5 0

@кот Бегемот Платежеспособный зверь 8926 / 4354 / 1642 Регистрация: 28.10.2009 Сообщений: 11,568
	26.11.2018, 17:10	3
	Олимпиадная задача 10-летней давности. Решений в сети - куча, в том числе и с разбором. 0