Олипиадная задача по информатике "Вырубка деревьев" с решением на Паскале
 
Информатика в школе


Видео курсы для чайников фотошоп, joomla, wordpress, php, css 
  Главная  ●  Карта сайта
 
 

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

[к списку задач]

 

Имя входного файла: input.txt
Имя выходного файла: output.txt
Максимальное время работы на одном тесте: 1 секунда
Максимальный объем используемой памяти: 64 мегабайта

 

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

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

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

 

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

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

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

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

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

input.txt output.txt

5 3

 

4

 

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

Зафиксируем расстояние между деревьями после вырубки. Если оно равно 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.

 

[к списку задач]

 

Книжные новинки
Как сделать свой сайт и заработать на нем Е. Мухутдинов
Копилка
Рабочие программы
Проекты MS Office
Презентации
Открытые уроки
Экзаменационные билеты
Элективные курсы
Бесплатный soft
 Инструкции по ТБ
Подготовка к олимпиадам по информатике
Методика подготовки
"Золотые" алгоритмы
Простые задачи для начинающих
Олимпиадные задачи с решениями
Книги
Среда программирования
Обучение программированию на С++
Справочник по языку Pascal
Обучение
Подготовка к ЕГЭ
Создание сайтов
Уроки FrontPage
Уроки Word 2003
Создание игр на Delphi
Печатаем вслепую

Информация

Наши интервью
Книга почета
Курсы повышения квалификации
Электронная библиотечка
Книжная полка
Статьи
Полезные ссылки
Обратная связь

Конкурсы

Олимпиада
Фотоконкурс
VIP
Персональный раздел профессора
Макаровой Н.В.
Персональный раздел профессора
Смыковской Т.К.