Идеи

В ряд выписаны натуральные числа от 1 до n и задано натуральное число 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¹⁸).

Вторая строка входных данных содержит целое число k (2 ≤ k ≤ 100, k < n).

Требуется вывести одно целое число — номер шага, на котором будет удалено число n, или число 0, если число n не будет удалено.
 

Ввод	Вывод
13 2	3

 

Однажды, вернувшись в свою башню, Мерлин обнаружил, что Моргана наложила проклятие на

все его сосуды с эликсиром мудрости.

Мерлин знает, как снять проклятие, но соответствующее заклинание требует, чтобы во всех

сосудах, к которым оно применяется, было равное количество эликсира.

Чтобы добиться этого, Мерлин решил действовать следующим образом. Он выбирает несколько

сосудов и переливает весь эликсир из выбранных сосудов в оставшиеся. Он может распределить

переливаемый эликсир между оставшимися сосудами произвольным образом. После того, как весь

эликсир из выбранных сосудов перелит, Мерлин разбивает опустошенные сосуды (с них проклятие

уже не снять), выбрасывает осколки и применяет заклинание снятия проклятия к оставшимся

сосудам.

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

чтобы снять проклятие Морганы.

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

В первой строке входного файла находится число n (2 ≤ n ≤ 10⁵) — количество сосудов. Во

второй строке содержатся n чисел a₁, a₂, . . . , a_n (1 ≤ a_i ≤ 10⁹) — количество литров эликсира

мудрости в каждом сосуде.

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

Выведите в выходной файл минимальное количество сосудов, которые Мерлину придется

разбить.

Пример
Ввод

 

В первом примере можно, например, перелить 0.5 литра эликсира из первого сосуда во второй

и 1.5 литра в третий, после чего разбить первый сосуд.

Во втором сосуды исходно содержат равное количество эликсира, можно ничего не переливать.

В третьем примере можно, например, перелить 1 литр эликсира из первого сосуда во второй, по

2 литра из пятого во второй и третий, 1 литр из пятого в четвертый, после чего разбить первый и

пятый сосуды.

Кроме школы и математического кружка, Вася ходит на шахматный кружок. Но играть в шахматы на обычной доске 8 × 8 ему кажется не очень интересным. Недавно он придумал свою версию шахмат, в которой игра происходит на доске, имеющей другую форму. Васина доска состоит из n столбцов, i-й из которых содержит ai клеток. Нижние клетки всех столбцов образуют один  горизонтальный ряд, причем длины столбцов упорядочены слева направо по невозрастанию. На рисунке ниже приведен пример доски, в которой три столбца, содержащих 5, 2 и 1 клетку,  соответственно.