Question

Условие
Дано число N и массив из S целых чисел Ai.
За одну операцию можно заменять число N на любое из чисел N+Ai, N−Ai, N×Ai, N/Ai.
Второй операнд может быть любым элементом массива A.
Деление выполняется нацело, с округлением вниз.
Необходимо рассчитать минимальное количество операций, необходимых, чтобы получить из числа N число 0.
Формат входных данных
Первая строка входных данных содержит целое число N.
Вторая — целое число S.
Третья — S целых чисел, массив A.
Формат выходных данных
Выходные данные должны содержать одно целое число — минимальное количество операций.
Ограничения
0≤N
Ai≤2∗10^9
1≤S≤100

Answer 1

• Если N = 0, то ответ 0: никаких операций с числом проводить не надо.
• Если одно из чисел в массиве равно 0 (и само число не 0), то ответ 1: можно просто умножить на ноль и получить ноль.
• Если все числа равны 1, то ответ N: единственное, что можно сделать, это N раз вычесть 1.

Утверждение: если всё вышеперечисленное не выполнено, можно просто много раз делить на максимальное из чисел; на последнем шаге, возможно, надо будет вычесть максимальное, а не разделить на него. При этом будет получен 0 за минимальное число шагов. Это можно показать и строго, но "на пальцах" это верно, так как деление на максимальное из чисел - операция, с которой число уменьшается быстрее всего.

Код (Python 3):

N = int(input())

_ = int(input())

A = list(map(int, input().split()))

if N == 0:

   print(0)

elif 0 in A:

   print(1)

elif all(elem == 1 for elem in A):

   print(N)

else:

   M = max(A)

   count = 0

   while N != 0:

       if N != M:

           N //= M

       else:

           N -= M

       count += 1

   print(count)