Найти количество чисел, которые можно образовать из заданных путем их сложения

Question

Задача:

Дизайн-студия Артемия Индюкова получила заказ на разработку очень пафосного лифта для нового небоскреба. За работу взялся сам Артемий, отличающийся редкой неадекватностью. У него есть идея-фикс: для управления лифтом должно быть достаточно следующих четырёх кнопок:

Подняться на A этажей вверх;

Подняться на B этажей вверх;

Подняться на C этажей вверх;

Спуститься на первый этаж.

Изначально лифт находится на первом этаже. Пассажир лифта использует первые три кнопки, чтобы попасть на тот этаж, на который он хочет. Если пассажир пытается подняться вверх на A, B или C этажей, а такого этажа в здании не существует (то есть пассажир хочет подняться выше N-го, последнего, этажа), то лифт никуда не едет.

Заказчики проекта оказались с юмором и вместе с отказом от футуристичного дизайна решили оценить адекватность Артемия по шкале от 1 до N. Оценка адеватности равна количеству этажей, на которые можно попасть с первого с помощью такого лифта. Помогите им в этом.

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

Первая строка содержит число N — высоту небоскреба (0 < N < 500001) Вторая строка содержит три числа A, B и C задающие параметры кнопок (0 < A, B, C < 100001).

Формат результата

Выведите единственное число — оценку адекватности Артемия Индюкова.

Примеры Входные данные

15

4 7 9

Результат работы

9

Мой код:

floors = int(input())
a, b, c = map(int, input().split())
new_floors = {a + 1, b + 1, c + 1}

for _ in range(floors):
    cop = new_floors.copy()
    for abc in [a, b, c]:
        for floor in cop:
            num = abc + floor
            if num < floors + 1:
                new_floors.add(num)

print(len(new_floors) + 1)

Суть:

Не проходят некоторые тесты, например:

Тест 6:

Входные данные:

10

1 3 5

Ожидаемый результат:

9

У меня выводит 10. Где ошибка?

Answer 1

Решил задачу таким способом:

Логика: 1 - этаж не берем, так как с него начинаем подниматься и доступ к нему есть по умолчанию. Далее перебираем все возможные комбинации складывая кнопки этажей и добавляем результаты в список, если значение больше заданной высоты здания, то добавляем в список указанную высоту. По итогу выводим количество уникальных элементов списка


floors = int(input()) # высота здания
buttons = list(map(int, input().split())) # кнопки лифта


# список всех комбинаций сложения
results = []

for i in buttons:
    # если 1 этаж, то не добавляем
    if i != 1:
        results.append(i)

    for u in buttons:
        result = i + u
        
        if result >= floors:
            results.append(floors)
        else:
            results.append(result)

        while result < floors:
            result = result + u
            if result >= floors:
                results.append(floors)
            else:
                results.append(result)

# вывод уникальных значений списка
print(f'{list(set(results))=}')
# итоговый результат
print(f'{len(list(set(results)))=}')

Тест 1:

Ввод:

15 4 7 9

Результат работы:

list(set(results))=[4, 7, 8, 9, 11, 12, 13, 14, 15]

len(list(set(results)))=9

Тест2:

Ввод:

10 1 3 5

Результат работы:

list(set(results))=[2, 3, 4, 5, 6, 7, 8, 9, 10]

len(list(set(results)))=9

Answer 2

import os

def calculate_accessible_floors(N, A, B, C):
    # Создаем множество для хранения достижимых этажей:
    accessible_floors = set()
    # Начинаем с первого этажа (1) или с нуля, если 1 нет в списке кнопок:
    queue = [1] if 1 in [A, B, C] else [0]
    
    while queue:
        # Извлекаем текущий этаж из очереди:
        current_floor = queue.pop(0)
        
        # Проверяем все возможные варианты подъема на A, B и C этажей:
        for move in [A, B, C]:
            next_floor = current_floor + move
            # Если новый этаж находится в пределах здания и еще не был посещен...
            if next_floor <= N and next_floor not in accessible_floors:
                # Добавляем новый этаж в множество достижимых этажей:
                accessible_floors.add(next_floor)
                # Добавляем новый этаж в очередь для дальнейшей обработки:
                queue.append(next_floor)
    
    # Возвращаем количество уникальных достижимых этажей:
    return len(accessible_floors)

# Примеры:
N = 15
A, B, C = 4, 7, 9
result = calculate_accessible_floors(N, A, B, C)
print(f"Оценка адекватности для {N} этажей и кнопок {A}, {B}, {C}:", result)
N = 10
A, B, C = 1, 3, 5
result = calculate_accessible_floors(N, A, B, C)
print(f"Оценка адекватности для {N} этажей и кнопок {A}, {B}, {C}:", result)

os.system("pause")

Answer 3

Решение без множеств

# Получение данных
N = int(input())
A, B, C = [int(_) for _ in input().split()]

# Для каждого этажа проверяем, можно ли до него добраться
floors = []
for i in range(N):
    # Сначала мы находимся на первом этаже
    if i == 0:
        floors.append(True)
        continue
    flag = False
    # Проверяем, можно ли добраться до этажей i - A, i - B, i - C
    if i - A >= 0 and floors[i - A]:
        flag = True
    if i - B >= 0 and floors[i - B]:
        flag = True
    if i - C >= 0 and floors[i - C]:
        flag = True
    floors.append(flag)

# Вывод
print(sum(floors))

БЛОГ НА HUSL

Найти количество чисел, которые можно образовать из заданных путем их сложения

Задача:

Мой код:

Ответы (3 шт):