Вырубка деревьев

Вырубка деревьев

(Время: 1 сек. Память: 16 Мб Сложность: 46%)

Король Флатландии решил вырубить некоторые деревья, растущие перед его дворцом. Деревья перед дворцом короля посажены в ряд, всего там растет n деревьев, расстояния между соседними деревьями одинаковы.

После вырубки перед дворцом должно остаться m деревьев, и расстояния между соседними деревьями должны быть одинаковыми. Помогите королю выяснить, сколько существует способов вырубки деревьев.

Требуется написать программу, которая по заданным числам n и m определит, сколько существует способов вырубки некоторых из n деревьев так, чтобы после вырубки осталось m деревьев и соседние деревья находились на равном расстоянии друг от друга.

Входные данные

Входной файл INPUT.TXT содержит два целых числа n и m (0 ≤ m , n ≤ 1000).

Выходные данные

В единственную строку выходного файла OUTPUT.TXT нужно вывести одно целое число — искомое число способов.

Пример

INPUT.TXT      OUTPUT.TXT

5 3      4

Пояснение к примеру

Если обозначить условно исходное расположение деревьев перед дворцом как «TTTTT», то возможные результаты после вырубки следующие:

«TTT..», «.TTT.», «..TTT», «T.T.T».

Идея решения

Главная догадка состоит в том, что нужно представить финальный вариант вырубки в следующем виде:

[T <k>  T <k>  … T ]

1          2 ….        m

В результате вырубки оставлено m деревьев, между которыми вырублено k деревьев. Значение k может варьироваться от 0 до k_max.

Если k равно нулю, то это означает, что оставляются m подряд растущих деревьев. В этом случае можно оставить первые m деревьев, а  вырубить последние n – m деревьев. Можно вырубить первое дерево в ряду, затем m деревьев не вырубать, и затем вырубить n-m -1 дерево. Можно вырубить два дерева в начале ряда, а остальные в конце ряда. Число различных способов равно n – m + 1.

Для каждого k вариант вырубки может быть несколькими способами размещен в исходном ряду деревьев:

T          T         T [<финальный интервал]  T      T

1          2         3                                                       n-1   n

Зная k, нетрудно подсчитать Nk — число деревьев в исходном ряду, соответствующих финальному варианту, от первого оставленного дерева до последнего оставленного дерева.

Nk = m + (m-1) * k

Понятно, что Nk <= n

Нетрудно определить k_max, как максимальное k, при котором выполняется указанное ограничение:

k_max = (n – m) /  ( m – 1)

Остается понять, сколькими способами интервал из Nk деревьев может быть представлен в ряду из n деревьев.  Таких способов Pk:

Pk = n – Nk + 1

Алгоритм решения становится понятным. Зная n и m, считаем k_max. Затем в цикле по k от 0 до k_max, вычисляем Nk и Pk.

Сумма Pk по всем k дает ответ на поставленный в задаче вопрос.

Приведу возможную программу на C#, реализующую описанный алгоритм:

using System;

using System.Collections.Generic;

using System.Linq;

using System.Text;

using System.Threading.Tasks;

 

namespace Trees

{

class Program

{

/* Задача

* Король одного государства решил вырубить некоторые деревья.

* Деревья посажены в ряд, всего их n.

* Расстояния между деревьями одинаковы.

* После вырубки должно остаться m деревьев,

* расстояния между которыми должны оставаться одинаковыми.

* Предполагается, что n > m.

* Напишите программу, которая по заданным n и m

* определяет число возможных способов вырубки деревьев

* */

/* Идея решения

* Пусть k — число подряд вырубаемых деревьев

* между растущими деревьями.

* Значение k может меняться в пределах [0, k_max]

* Рассмотрим финальный вариант из m деревьев,

* между которыми вырублены k деревьев.

* Первоначальное число деревьев в этом интервале

* mk = m + (m-1) * k

* Так как mk не превосходит n, то

* k_max = (n — m)/(m-1)

* Финальный интервал помещается в

* исходный интервал из n деревьев

* Сделать это можно Pk способами, где

* Pk = n — mk + 1 способами.

* Общее число способов равно P = Sum(Pk)

* В цикле по k нужно вычислить

* и просуммировать значения Pk

* Особый случай m = 1;

* интервал между деревьями

*  не существует (дерево одно).

*  Нетрудно понять что в этом случае

*  P = n

* */

static void Main(string[] args)

{

Console.WriteLine(«Введите число деревьев»);

int n = int.Parse(Console.ReadLine());

Console.WriteLine(«Введите число деревьев после вырубки»);

int m = int.Parse(Console.ReadLine());

int P = 0;

if (m == 1)

P = n;

else

{

int k_max = (n — m) / (m — 1);

int Pk = 1;

for (int i = 0; i <= k_max; i++)

{

Pk = n — m — (m — 1) * i + 1;

P += Pk;

}

}

Console.WriteLine(«Число способов вырубки = » + P);

}

}

}

В программе ввод и вывод осуществляется с консоли, а не из файла. Учтен также особый случай, когда король решил оставить только одно дерево.