B. Подарки от Комарика для Мухи-Цокотухи Ограничение времени 1 секунда Ограничение памяти 64Mb Ввод стандартный ввод или input.txt Вывод стандартный вывод или output.txt На день…

Чтобы решить задачу о возможности создания компонента с заданной мощностью Z из двух начальных компонент с мощностями X и Y, мы можем использовать метод обхода. Основная идея заключается в том, чтобы реализовать набор всех возможных мощностей, которые можем получить, начиная с X и Y, и проверять, можем ли мы получить Z.

Для начала, мы создаем очередь, в которую помещаем текущие известные мощности (X и Y) и будем поочередно извлекать элементы из очереди для генерирования новых мощностей. Мы продолжаем этот процесс до тех пор, пока не либо не исчерпаем все возможности, либо не достигнем необходимой мощности Z.

Вот пример кода на Python, который реализует описанный выше алгоритм:

from collections import deque

def can_create_component(X, Y, Z):
    if Z == X or Z == Y:
        return True
    
    # Множество для хранения уникальных мощностей
    seen = set()
    seen.add(X)
    seen.add(Y)
    
    # Очередь для обработки
    queue = deque([X, Y])
    
    while queue:
        current = queue.popleft()
        
        # Генерируем новые мощности
        new_power1 = current * X + current + X
        new_power2 = current * Y + current + Y
        
        # Проверяем новую мощность
        if new_power1 == Z or new_power2 == Z:
            return True
        
        # Добавляем в очередь, если ее еще не обработали
        if new_power1 <= 1000000 and new_power1 not in seen:
            seen.add(new_power1)
            queue.append(new_power1)
        
        if new_power2 <= 1000000 and new_power2 not in seen:
            seen.add(new_power2)
            queue.append(new_power2)
    
    return False

# Чтение входных данных
X, Y, Z = map(int, input().split())

# Проверяем возможность создания компонента Z
if can_create_component(X, Y, Z):
    print("Yes")
else:
    print("No")

Объяснение кода:

1. Очередь и множество: Мы используем очередь (deque) для хранения всех мощностей, которые можно получить, и множество под названием seen для отслеживания тех мощностей, которые мы уже обработали, чтобы избежать повторений.

2. Генерация новых мощностей: Мы создаем две новые мощности на каждой итерации (используя текущую мощность и каждый из начальных компонентов) и проверяем, равны ли они Z.

3. Проверка границ: Если новая мощность превышает 1,000,000, мы не добавляем её в очередь, так как нас это не интересует (прекращаем дальнейшие вычисления).

4. Вывод результата: В зависимости от того, сможем ли мы получить компонент Z, выводим "Yes" или "No".

Таким образом, мы используем итеративный подход для вычисления всех возможных мощностей, генерируемых из начальных компонент, и проверяем, достигаем ли мы целевой мощности Z.