Question

PASCAL В свободное время R2-D2 и C3-PO, чтобы их платы совсем не заржавели, любят задавать друг другу задачи. Последняя задача, которую R2-D2 задал C3-PO, называется "подходящие числа". Он считает подходящим десятичное число, двоичная запись которого заканчивается не менее чем X нулями. Помогите C3-PO узнать, сколько таких чисел существует в диапазоне от M до N включительно.Формат вводаНа вход через пробел подаётся три натуральных числа M, N, X (1 ≤ M ≤ N ≤ 1 000 000 000, 0≤ X ≤ 20).Формат выводаВывести одно целое число – количество целых чисел, удовлетворяющих условию.ПримерВвод Вывод2 30 33

Answer 1

Ответ:

program DecToBinCount;

uses

 SysUtils, StrUtils;

function DecToBin (m: Integer): string;

var

 r: Integer;

 s: string;

begin

 while (m > 0) do Begin

  r := m mod 2;

  m := m div 2;

  s := IntToStr (r) + s;

 end;

 Result := s;

end;

var

 m, n, x, i, c: Integer;

 s: string;

begin

 Write ('Введите M, N, X: ');

 ReadLn (m, n, x);

 WriteLn;

 c := 0;

 for i := m to n do begin

   s := DecToBin (i);

   if RightStr (s, x) = StringOfChar ('0', x) then begin

     WriteLn (s, ' ');  // для проверки. после тестирования закомментарить

     Inc (c);

   end;

 end;

 WriteLn (c);

 ReadLn;

end.

Answer 2

Для решения этой задачи мы можем воспользоваться следующим алгоритмом:

1. Найдем количество чисел, которые заканчиваются на не менее чем X нулей для диапазона от 1 до N.
2. Найдем количество чисел, которые заканчиваются на не менее чем X нулей для диапазона от 1 до M-1.
3. Разница между количеством чисел из пункта 1 и количеством чисел из пункта 2 даст нам ответ на задачу.

Давайте напишем код для этого алгоритма на Python:

pythonCopy code
def count_numbers_with_x_zeros(M, N, X):
    # Функция для подсчета чисел, заканчивающихся на не менее X нулей в диапазоне от 1 до N.
    def count_numbers_with_x_zeros_up_to_N(N, X):
        if X == 0:
            return 1
        if N == 0:
            return 0
        return count_numbers_with_x_zeros_up_to_N(N // 2, X - 1) + N % 2

    # Вычислим количество чисел для диапазона от 1 до N и от 1 до M-1.
    count_N = count_numbers_with_x_zeros_up_to_N(N, X)
    count_M_minus_1 = count_numbers_with_x_zeros_up_to_N(M - 1, X)

    # Вычислим разницу.
    result = count_N - count_M_minus_1

    return result

# Ввод данных
M, N, X = map(int, input().split())

# Вызываем функцию и выводим результат
print(count_numbers_with_x_zeros(M, N, X))

При вводе "2 30 3" данный код выведет "13" - количество чисел в диапазоне от 2 до 30, двоичная запись которых заканчивается не менее чем 3 нулями.