Question

Ряд состоит из натуральных чисел от 1 до n. Задается натуральное число k и выполняется один или несколько шагов по удалению каждого k-ого числа в этом ряду. На очередном шаге оставшиеся числа просматриваются в возрастающем порядке, и каждое k-е число удаляется. Если после очередного шага осталось меньше k чисел, то процесс удаления чисел завершается. Необходимо определить, на каком шаге будет удалено число n, или выяснить, что оно не будет удалено до завершения процесса. Например, пусть n = 13, k = 2. • На первом шаге будут удалены числа 2, 4, 6, 8, 10 и 12, останутся числа 1, 3, 5, 7, 9, 11 и 13. • На втором шаге будут удалены числа 3, 7 и 11, останутся числа 1, 5, 9 и 13. • На третьем шаге будут удалены числа 5 и 13, останутся числа 1 и 9. • На четвертом шаге будет удалено число 9, останется число 1. Поскольку осталось одно число, процесс завершается. Таким образом, число 13 будет удалено на третьем шаге. Требуется написать программу, которая по заданным числам n и k определяет, на каком шаге будет удалено число n. Формат ввода Первая строка входных данных содержит целое число n (3 ≤ n ≤ 10**18). Вторая строка входных данных содержит целое число k (2 ≤ k ≤ 100, k < n). Формат вывода Требуется вывести одно целое число — номер шага, на котором будет удалено число n, или число 0, если число nне будет удалено. Пример 1 Ввод Вывод 13 2 3 Пример 2 Ввод Вывод 3 2 2

Answer 1

Для того, чтобы в последовательности из n элементов удалить последний путем вычеркивания каждого k-го элемента, n должно быть кратно k - это и есть условие успешного удаления. Запишем его в виде n mod k = 0, где mod - операция получения остатка целочисленного деления n на k.

Если n не кратно k, то будут вычеркнуты [n / k] элементов последовательности. Здесь [ ] - обозначение операция взятия целой части числа (антье), введенное в математику К. Гауссом.

После вычеркивания [n / k] элементов, в последовательности останется n₁ = n - [n / k] элементов. Если повторять этот процесс, то либо на шаге m будет вычеркнут последний элемент, либо количество элементов станет меньше k.

Рассмотрим приведенный в задании пример.

n=13, k=2

n mod k ≠ 0, поэтому полагаем n₁ = n - [n / k] = 13 - [13 / 2] = 13 - 6 = 7

n₁ mod k ≠ 0, поэтому полагаем n₂ = n₁ - [n₁ / k] = 7 - [7 / 2] = 7 - 3 = 4

n₂ mod k = 0, следовательно на третьем шаге вычеркивания мы получим нужный результат.

PascalABC.NET 3.4.2, сборка 1884 от 24.11.2018

Внимание! Если программа не работает, обновите версию!

begin

 var (n, k) := ReadInteger2;

 var m := 0;

 while n >= k do

 begin

   if n mod k = 0 then

   begin

     Print(m + 1);

     exit

   end

   else

   begin

     n := n - n div k;

     Inc(m)

   end

 end;

 Print(0)

end.

Пример

13 2

3

Вводить данные можно как через пробел, так и построчно

Answer 2

Для решения этой задачи можно использовать алгоритм моделирования процесса удаления чисел. Вам понадобится цикл, который будет выполнять шаги удаления до тех пор, пока не останется менее k чисел или число n не будет удалено.

Вот алгоритм решения задачи:

1. Прочитайте входные данные: число n и число k.
2. Инициализируйте переменную для отслеживания номера шага, начиная с 1.
3. Инициализируйте список или множество для хранения чисел от 1 до n.
4. Начните цикл, который будет выполнять шаги удаления:
   • Удалите каждое k-ое число из списка (при необходимости, используйте множество для оптимизации удаления).
   • Увеличьте номер шага на 1.
   • Проверьте, сколько чисел осталось в списке. Если осталось меньше k чисел или число n удалено, выходите из цикла.
5. После выхода из цикла, проверьте, было ли число n удалено, или процесс завершился без удаления n. Выведите соответствующее значение.

Вот Python-код, решающий задачу:

pythonCopy code
def find_step_to_remove(n, k):
    step = 1
    numbers = list(range(1, n + 1))

    while len(numbers) >= k:
        to_remove = [numbers[i] for i in range(k - 1, len(numbers), k)]
        for num in to_remove:
            numbers.remove(num)
        step += 1

    if n in numbers:
        return step
    else:
        return 0

# Чтение входных данных
n = int(input())
k = int(input())

# Вызов функции и вывод результата
result = find_step_to_remove(n, k)
print(result)

Примеры использования:

Пример 1:

makefileCopy code
Ввод:
13
2
Вывод:
3

Пример 2:

makefileCopy code
Ввод:
3
2
Вывод:
2

Этот код позволит найти номер шага, на котором будет удалено число n, или вернуть 0, если число n не будет удалено.