Question

На летних каникулах Вася с одноклассниками поехали отдыхать в Приэльбрусье. В один погожий день они решили подняться на вершину Эльбруса. Для этого им нужно набрать H метров высоты. Физическая подготовка ребят оказалась далеко не на высоте, из-за чего после каждого подъема на T метров половина школьников возвращалась вниз в лагерь. Если группа не делилась на две равные части — один школьник мог как спуститься, так и остаться.Зная, что в начале восхождения группа состояла из N человек, определите, какое наименьшее и наибольшее количество ребят смогло бы подняться на вершину Эльбруса.Формат вводаЗаданы три натуральных числа H, T и N (1 ≤ H, T, N ≤ 10**9).Формат выводаВыведите два числа — наименьшее и наибольшее количество ребят.На паскале

Answer 1

Ответ вот получите распишитесь

Answer 2

Для решения данной задачи можно использовать бинарный поиск. Будем искать ответ в интервале [1, N], так как наименьшее количество ребят не может быть меньше 1 и не может быть больше N.

Пусть left = 1, right = N.

1. Начинаем бинарный поиск. Пока left ≤ right, выполняем следующие шаги:

   1.1. Полагаем mid = (left + right) // 2 - это количество ребят, которые поднимутся на высоту T метров.

   1.2. Если mid + (mid // 2) ≥ N, значит, количество ребят, оставшихся наверху, достаточно большое, чтобы продолжить восхождение ещё на T метров. Значит, можем увеличить left, чтобы попробовать большее количество поднявшихся ребят.

   1.3. Иначе, если mid + (mid // 2) < N, значит, количество ребят, оставшихся наверху, недостаточно, чтобы продолжить восхождение ещё на T метров. Значит, нужно уменьшить right, чтобы попробовать меньшее количество поднявшихся ребят.

2. После завершения бинарного поиска, left будет представлять наименьшее количество ребят, которые поднялись на вершину Эльбруса.

3. Теперь, чтобы найти наибольшее количество ребят, возможно поднявшихся на вершину, нужно учесть тех, кто вернулся вниз после каждого подъема на T метров. Для этого можно пройтися по всем предыдущим итерациям бинарного поиска и найти максимальное значение mid + (mid // 2).

Давайте реализуем этот алгоритм на Pascal:

pascalCopy code
function MinMaxClimbers(H, T, N: Int64): string;
var
  left, right, mid, maxClimbers, climbers: Int64;
begin
  left := 1;
  right := N;
  maxClimbers := 0;

  while left <= right do
  begin
    mid := (left + right) div 2;
    climbers := mid + (mid div 2);

    if climbers >= N then
    begin
      maxClimbers := Max(maxClimbers, N);
      right := mid - 1;
    end
    else
    begin
      maxClimbers := Max(maxClimbers, climbers);
      left := mid + 1;
    end;
  end;

  Result := IntToStr(left - 1) + ' ' + IntToStr(maxClimbers);
end;

// Пример использования функции:
var
  H, T, N: Int64;
  resultStr: string;
begin
  // Считываем входные данные
  ReadLn(H, T, N);

  // Вызываем функцию и выводим результат
  resultStr := MinMaxClimbers(H, T, N);
  WriteLn(resultStr);
end.

Здесь функция MinMaxClimbers находит наименьшее и наибольшее количество ребят, которые могли бы подняться на вершину Эльбруса с заданными условиями. Обратите внимание, что она возвращает результат в виде строки, где первое число - наименьшее количество ребят, а второе число - наибольшее количество ребят.