Помогите пожалуйста
В одном правительственном здании установили инновационный лифт. Известно, что здание имеет как наземные этажи, нумерующиеся 1, 2, ..., так и подземные этажи, нумерующиеся -1, -2, .... Лифт изначально находится на нулевом этаже, а этаж, на который нужно подняться, кодируется нажатием на кнопки "A" и "B". Нажатие на кнопку "A" прибавляет к текущему запрошенному этажу некоторое фиксированное число (обозначим его A), а нажатие на кнопку "B" умножает текущий запрошенный этаж на некоторое другое фиксированное число (обозначим его B). При этом требуется, чтобы выбор этажа выполнялся за минимальное число нажатий, иначе лифт никуда не поедет.
Значения A и B могут быть как положительными, так и отрицательными, но не равны 0.
Например, пусть нам требуется попасть на 9 этаж, а значение A равно 1, а B равно 2. Тогда необходимо последовательно нажать на кнопки A, B, B, B, A: (0+1)*2*2*2+1.
Формат входных данных
На вход поступает число N (0 < N < 1000) — число запросов, затем целое число A (-1000 < A < 1000, A ≠ 0), затем целое число B (-1000 < B < 1000, B ≠ 0), затем N целых чисел X (-1000 < X < 1000, X ≠ 0) — запрашиваемый этаж.
Запросы не зависят друг друга, то есть каждый раз лифт едет с нулевого этажа.
Формат результата
Если заданное число получить невозможно, выведите 0. В противном случае выведите последовательность минимальной длины из символов A и B, где A означает операцию сложения с A, а B — умножения на B, которая позволяет получить заданное число из начального значения 0. Каждый символ выводите на отдельной строке. Если подходящих последовательностей несколько, выведите любую.
Ответы
Код на Python:
def find_operations(N, A, B, X):
result = []
for target in X:
operations = []
current = 0
while current != target:
if current + A == target:
operations.append('A')
current += A
elif (target - current) % B == 0:
operations.append('B')
current *= B
else:
operations.append('A')
current += A
result.append(operations)
return result
# Зчитуємо вхідні дані
N = int(input())
A = int(input())
B = int(input())
X = list(map(int, input().split()))
# Знаходимо послідовності операцій
sequences = find_operations(N, A, B, X)
# Виводимо результат
for sequence in sequences:
print('\n'.join(sequence))