Вырубка деревьев король флатландии решил вырубить некоторые деревья

Задача Паскаль вырубка деревьев

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

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

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

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

В выходном файле OUTPUT.TXT должно содержаться одно число — искомое количество способов.Пример INPUT.TXT: OUTPUT.TXT для примера:
5 3 4

Ограничение времени: 1 сек на тест

РЕШЕНИЕ
program trees;
var
n, m : longint;

i, d, s : longint;
input_file, output_file : Text;

s := 0;
if m = 0 then s := 1
else if m = 1 then s := n
else for d := 1 to (n-1) div (m-1) do Inc(s,n-(m-1)*d);

Объясните решение плиз,вот эту строку вообще не понимаю else for d := 1 to (n-1) div (m-1) do Inc(s,n-(m-1)*d);
неясно что мы обозначаем переменной д что такое н-1 див м-1 про инк и далее вообще не понятно что там делается

короче говоря нужен разбор этой задачи

ага..очень только это не на конкурсе))про див я и сама всё знаю я не понимаю д получается расстояние между деревьями а что такое n-(m-1)*d

else for d := 1 to (n-1) div (m-1) do Inc(s,n-(m-1)*d);
означает:
иначе делаем цикл по переменной d, которая принимает значения от 1 до (n-1) div (m-1)
(div — это операция целочисленного деление, например, x div y означает x/y округлённое до ближайшего целого значения, например,
7 div 3 = 2;
28 div 5 = 5
100 div 33 = 3)
В цикле делаем yвеличение значения s на величину n-(m-1)*d

Интересная задача на конкурсе у вас. )))

Источник

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

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

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

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

Формат входных данных

Входной файл INPUT.TXT содержит два целых числа M и N (0

Формат выходных данных

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

Пример входных и выходных данных

Краткие методические рекомендации по решению задачи

Зафиксируем расстояние между деревьями после вырубки. Если оно равно d, то возможно
n – d(m – 1) – m + 1 способов вырубить деревья. Суммируя по всем d, получаем ответ.

Если у нас есть 0 деревьев и 0 деревьев должно остаться после вырубки, то существует один вариант вырубки — это надо учитывать при решении задачи.

Вариант 1 (с использованием цикла)

var n, m : longint; i, d, s : longint; input, output: text; begin Assign(input,'input.txt'); Reset(input); Assign(output,'output.txt'); Rewrite(output); Read(input,n,m); s := 0; if m = 0 then s := 1 else if m = 1 then s := n else for d := 1 to (n-1) div (m-1) do inc(s,n-(m-1)*d); Write(output,s); Close(input); Close(output); end.

Вариант 2 (без цикла)

var n, m ,k: longint; i, d, s : longint; input, output: text; begin Assign(input,'input.txt'); Reset(input); Assign(output,'output.txt'); Rewrite(output); read(input,n,m); if m=0 then s:=1 else if m=1 then s:=n else begin k:=(n-1) div (m-1); d:=m-1; s:=(2+(k-1)*d)*k div 2;  end; write(output, s); Close(input); Close(output); end. 

Источник

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

Вырубка деревьев
(Время: 1 сек. Память: 16 Мб Сложность: 46%)
Король Флатландии решил вырубить некоторые деревья, растущие перед его дворцом. Деревья перед дворцом короля посажены в ряд, всего там растет n деревьев, расстояния между соседними деревьями одинаковы.
После вырубки перед дворцом должно остаться m деревьев, и расстояния между соседними деревьями должны быть одинаковыми. Помогите королю выяснить, сколько существует способов вырубки деревьев.
Требуется написать программу, которая по заданным числам n и m определит, сколько существует способов вырубки некоторых из n деревьев так, чтобы после вырубки осталось m деревьев и соседние деревья находились на равном расстоянии друг от друга.

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

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

№	INPUT.TXT	OUTPUT.TXT
1	5 3	4

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

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

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

#include int main(){ std::fstream f("input.txt"),q("output.txt",2); int a,b,i=0; f>>a>>b; if(a==b){ q1; }else{ if(b==1){ qa; }else{ b=b-1; int k=a/b; int p=a-b; long long c=(b*((k*(k-1))/2)); int o=(k*p)-c; q(o0 ? 1 : o); } } }

Размер кода: 212
в топе лутшее решение (с++) 120 символов
как сократить код?

Добавлено через 8 минут

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17

#include int main(){ std::fstream f("input.txt"),q("output.txt",2); int a,b,i=0; f>>a>>b; if(a==b){ q1; }else{ if(b==1){ qa; }else{ b=b-1; int o=((a/b)*(a-b))-(b*(((a/b)*((a/b)-1))/2)); q(o0 ? 1 : o); } } }

Источник

Разбор олимпиадной задачи — Вырубка деревьев

Чтобы лучше понять суть задачи — рекомендую нарисовать на бумаге пример, а также рассмотреть другие примеры — для n=9 и m=3: Итак, нам нужно вычислить количество способов, которыми можно разместить деревья с заданными между ними интервалами. Если интервал равен нулю — то мы размещаем группу из M деревьев по N позиций.
Если интервал равен 1 — то мы размещаем группу из M+(M-1) элементов (потому что M деревьев, да еще (M-1) пропусков между ними.
Если интервал равен 2 — то нужно разместить группы по M + (M-1)*2 , т.к. пропусков в 2 раза больше чем в предыдущем случае.
И так далее. Тогда решение может быть сведено к перебору всех возможных интервалов. В простейшем случае — считать можно до тех пор, пока M + (M-1)*Distance не окажется больше N . Однако, при желании можно вычислить MaxDistance аналитически. Исходный код решения:

#include using namespace std; int variants(int all_trees, int remaining_trees) < if (0 == remaining_trees) return 1; if (1 == remaining_trees) return all_trees; if (all_trees < remaining_trees) return 0; int variants = 0; for (int distance = 0;true; distance++) < int usedPositions = remaining_trees + distance*(remaining_trees-1); if (usedPositions >all_trees) break; variants += all_trees — usedPositions + 1; > return variants; > int main() < std::ifstream ifst("input.txt"); std::ofstream ofst("output.txt"); int n, m; ifst >> n >> m; ofst

Видно, что отдельно пришлось обработать случай «когда нужно вырубить все деревья» и некоторые другие.

Источник