Король флатландии решил вырубить некоторые деревья растущие перед его дворцом

Содержание

Король флатландии решил вырубить некоторые деревья растущие перед его дворцом
Вырубка деревьев
Разбор олимпиадной задачи — Вырубка деревьев
Задача Паскаль вырубка деревьев
Вырубка леса

Король флатландии решил вырубить некоторые деревья растущие перед его дворцом

Задача Паскаль вырубка деревьев
Король Флатландии решил вырубить некоторые деревья, растущие перед его дворцом. Деревья перед дворцом короля посажены в ряд, всего там растет 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; begin Assign(input_file,'INPUT.TXT'); Assign(output_file,'OUTPUT.TXT'); Reset(input_file); ReWrite(output_file); ReadLn(input_file,n,m); Close(input_file); 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_file,s); Close(output_file); end.

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

короче говоря нужен разбор этой задачи..объясните ничего не понимаю смысл сам решения не понимаю. откуда берётся этот н-1 див м-1 и что это такое..почему мы увеличиваем с именно на n-(m-1)* д ХЭЛППП. confu sed:

Else — ложная ветвь условия. d — это счетчик шагов в цикле. То есть d принимает значение с каждым шагом от 1 до (n-1) div (m-1)
(n-1) и (m-1) скорее всего от того, что это того что нумерация начинается от нуля (хотя здесь может быть и другой прикол)
div — деление нацело. Нельзя использовать (n-1) / (m-1) поскольку результат получится дробным (точнее может получиться), а это не есть хорошо поскольку d может принимать только целые значения (в свою очередь это связано с тем, что это переменная цикла — а она всегда целое число, без всяких запятых). Инк — это операция сложения к s c каждым шагом прибавляется n-(m-1)*d.
Почему именно это выражение? Наверно это задано условием задачи:
там растет N деревьев, расстояния между соседними деревьями одинаковы.

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

Всего деревьев N каждый раз рубим М (здесь каждый раз и есть d)

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

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

Всего деревьев N каждый раз рубим М (здесь каждый раз и есть d)

При чем здесь это? Нам надо не сколько рубим, а количество вариантов. Это задача на комбинаторику. Чтоб понять откуда что берется, порешайте вручную при небольших N, например при N=7 и просмотрите все варианты М от 1 до 7. Вы сами увидите последовательность, которую Вам и выразили формулой.

Может так понятнее будет. В принципе количество вариантов считается как сумма членов арифметической прогрессии, у которой первый член равен 1, а количество членов и шаг зависят от N и M, как это написано в приведенном варианте, просто решение из цикла переходит в линейный алгоритм. Пример без файла, просто так тестировать быстрее.

program trees; uses crt; var n, m ,k: longint; i, d, s : longint; begin clrscr; write('n=');readln(n); write('m=');readln(m); s := 0; k:=(n-1) div (m-1); d:=m-1; s:=(2+(k-1)*d)*k div 2; write(s); readln; end.

Кстати без цикла должно быстрее работать. У меня при значениях 1000 и 2 программа работает доли секунды, почти мнгновенно.

Источник

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

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

Требуется написать программу, которая по заданным числам 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.

Источник

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

Чтобы лучше понять суть задачи — рекомендую нарисовать на бумаге пример, а также рассмотреть другие примеры — для 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

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

Источник

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

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

Ограничение времени: 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);

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

ага..очень только это не на конкурсе))про див я и сама всё знаю я не понимаю д получается расстояние между деревьями а что такое 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

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

Источник

Вырубка леса

Фермер Николай нанял двух лесорубов: Дмитрия и Федора, чтобы вырубить лес, на месте которого должно быть кукурузное поле. В лесу растут X деревьев.

Дмитрий срубает по A деревьев в день, но каждый K-й день он отдыхает и не срубает ни одного дерева. Таким образом, Дмитрий отдыхает в K-й, 2K-й, 3K-й день, и т.д.

Федор срубает по B деревьев в день, но каждый M-й день он отдыхает и не срубает ни одного дерева. Таким образом, Федор отдыхает в M-й, 2M-й, 3M-й день, и т.д.

Лесорубы работают параллельно и, таким образом, в дни, когда никто из них не отдыхает, они срубают A+B деревьев, в дни, когда отдыхает только Федор — A деревьев, а в дни, когда отдыхает только Дмитрий — B деревьев. В дни, когда оба лесоруба отдыхают, ни одно дерево не срубается.

Фермер Николай хочет понять, за сколько дней лесорубы срубят все деревья, и он сможет засеять кукурузное поле.

Требуется написать программу, которая по заданным целым числам A, K, B, M и X определяет, за сколько дней все деревья в лесу будут вырублены.

Входные данные содержат пять целых чисел, разделенных пробелами: A, K, B, M и X (1≤A,B≤109 , 2≤K,M≤1018, 1≤X≤1018).

Выведите одно целое число — искомое количество дней.

В приведенном примере лесорубы вырубают 25 деревьев за 7 дней следующим образом:

1-й день: Дмитрий срубает 2 дерева, Федор срубает 3 дерева, итого 5 деревьев;
2-й день: Дмитрий срубает 2 дерева, Федор срубает 3 дерева, итого 10 деревьев;
3-й день: Дмитрий срубает 2 дерева, Федор отдыхает, итого 12 деревьев;
4-й день: Дмитрий отдыхает, Федор срубает 3 дерева, итого 15 деревьев;
5-й день: Дмитрий срубает 2 дерева, Федор срубает 3 дерева, итого 20 деревьев;
6-й день: Дмитрий срубает 2 дерева, Федор отдыхает, итого 22 дерева;
7-й день: Дмитрий срубает 2 дерева, Федор срубает оставшееся 1 дерево, итого все 25 деревьев срублены.
Примеры
Ввод
Вывод
2 4 3 3 25
7
Вот мой код, он работает, но превышает время работы

1 2 3 4 5 6 7 8 9 10 11 12

a, k, b, m, x = map(int, input().split()) days = 0 while x > 0: days += 1 if days % k != 0 and days % m == 0: x -= a elif days % m != 0 and days % k == 0: x -= b elif days % m != 0 and days % k != 0: x -= a x -= b print(days)

Источник