сайт учителя информатики

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

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

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

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

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

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

В выходном файле 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.