Алгоритмы на Python

Question

Попробовал решить такую задачу:

Улица, на которой хочет жить Тимофей, имеет длину n, то есть состоит из n одинаковых идущих подряд участков. На каждом участке либо уже построен дом, либо участок пустой. Тимофей ищет место для строительства своего дома. Он очень общителен и не хочет жить далеко от других людей, живущих на этой улице. Чтобы оптимально выбрать место для строительства, Тимофей хочет для каждого участка знать расстояние до ближайшего пустого участка. (Для пустого участка эта величина будет равна нулю –— расстояние до самого себя). Ваша задача –— помочь Тимофею посчитать искомые расстояния. Для этого у вас есть карта улицы. Дома в городе Тимофея нумеровались в том порядке, в котором строились, поэтому их номера на карте никак не упорядочены. Пустые участки обозначены нулями.

Формат ввода: В первой строке дана длина улицы —– n (1 ≤ n ≤ 106). В следующей строке записаны n целых неотрицательных чисел — номера домов и обозначения пустых участков на карте (нули). Гарантируется, что в последовательности есть хотя бы один ноль. Номера домов (положительные числа) уникальны и не превосходят 109.

Формат вывода Для каждого из участков выведите расстояние до ближайшего нуля. Числа выводите в одну строку, разделяя их пробелами.

Пример 1:

Ввод:

5

0 1 4 9 0

Вывод:

0 1 2 1 0

Пример 2:

Ввод:

6

0 7 9 4 8 20

Вывод:

0 1 2 3 4 5

Python | Ограничение времени: 3 сек | Ограничение памяти: 256 мб.

Учитель попросил сделать её по следующему т/з:

Создать выходной список и заполнить нулями.
Получить позиции всех нулевых в виде списка.
Создать простой цикл по позициям домов "до первого нулевого".
Сохранить результат явной формулы для расстояния между домом и первым нулевым.
Создать цикл по парам соседних нулевых.
Внутри него простой цикл по всем домам "между этой парой".
Сохранить результат явной формулы для минимального расстояния между домом и этими нулевыми.
Создать простой цикл по позициям домов "после последнего нулевого".
Сохранить результат явной формулы для расстояния между домом и последним нулевым.

Я сделал, но алгоритм не работает, ошибку найти не могу. Прошу вашей помощи(если несложно, можно побольше объяснений).
Мой код:

n=int(input())
street=list(map(int, input().split()))
null_address = [0] * len(street)
null_address = [position for position, null_address in enumerate(street) if null_address == '0'] # делаем список нулевых адресов с адресами улицы
for street_position in range(0, len(street), 1): # проходим по улице
    if street[street_position]==0: # если находим первый ноль
        for position_null_address in range(0, len(null_address), 1): # проходимся по списку содержащим адреса нулей
            null_address[position_null_address] = (null_address[position_null_address] - street_position) # значит зная где нули ты идешь от начала улицы до первого нуля и и вычисляешь расстояние до первого нуля
    elif street[street_position + 1]==0: # если находим следующий ноль
        for position_null_address in range(0, len(null_address), 1):
            null_address[position_null_address] = min(street_position - null_address[position_null_address], null_address[position_null_address + 1] - street_position)
    else: # если нулей больше нет или пока нет когда идём сначала
        for position_null_address in range(0, len(null_address), 1):
            null_address[position_null_address] = min(abs(street_position - null_address[position_null_address]), abs(null_address[position_null_address] - street_position))
print(*null_address)

UPD. Отредактировал код по совету из комментариев, ещё немного осталось недочётов.

Вычисление zeros[0] будет давать одинаковый результат на всех проходах. Лучше избегать лишних действий. (строка 6)
Вычисления zeros[k-1] и zeros[k] будут давать одинаковый результаты.(строка 9)
Вычисление zeros[-1] повторяется. (строка 11)

Новый код

def empty_houses(houses, vlu = '0'):
    n = len(houses)
    answer = [0] * n
    zeros = [position for position, vlue in enumerate(houses) if vlue == vlu]
    for position in range(zeros[0]):
        answer[position] = zeros[0] - position
    for pair in range(1, len(zeros)):
        for position in range(zeros[pair - 1] + 1, zeros[pair]):
            answer[position] = min(position - zeros[pair - 1], zeros[pair] - position)
    for position in range(zeros[-1] + 1, n):
        answer[position] = position - zeros[-1]
    return answer
if __name__ == '__main__':
    input()
    print(*empty_houses(input().split()))

Answer 1

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

a = [0, 1, 4, 9, 0]
#a = [0, 7, 9, 4, 8, 20]
#a = [3, 7, 9, 4, 8, 0]
#a = [7, 9, 4, 0, 8, 20]
n = len(a)
b = [0]*n
lastzero = -n
for i in range(len(a)):
    if a[i]:
        b[i] = i - lastzero
    else:
        lastzero = i
lastzero = 2*n
for i in reversed(range(len(a))):
    if a[i]:
        b[i] = min(lastzero-i, b[i])
    else:
        lastzero = i
print(b)

Answer 2

Ваш код не работает так как вы ищете нулевые адреса сравнивая номера домов (целые числа в списке street) cо строкой '0'. Равенство никогда не выполняется - ваша программа не видит нули.

Переменная null_address используется два раза (три на самом деле, но третий я опускаю) - для ответа и для списка нулевых участков.

Дальше я не смотрел и сразу перешёл к исполнению программы изложенной вашим преподователем. Вот результат:

n = int(input())
houses = input().split()

# Создать выходной список и заполнить нулями.
answer = [0] * n

# Получить позиции всех нулевых в виде списка.
zeros = [i for i, v in enumerate(houses) if v == '0']

# Создать простой цикл по позициям домов "до первого нулевого".
for i in range(zeros[0]):
    # Сохранить результат явной формулы для расстояния между домом и первым нулевым.
    answer[i] = zeros[0] - i

# Создать цикл по парам соседних нулевых.
for k in range(1, len(zeros)):
    # Внутри него простой цикл по всем домам "между этой парой".
    for i in range(zeros[k - 1] + 1, zeros[k]):
        # Сохранить результат явной формулы для минимального расстояния между домом и этими нулевыми.
        answer[i] = min(i - zeros[k - 1], zeros[k] - i) 

# Создать простой цикл по позициям домов "после последнего нулевого".
for i in range(zeros[-1] + 1, n):
    # Сохранить результат явной формулы для расстояния между домом и последним нулевым.
    answer[i] = i - zeros[-1]

print(*answer)

Это рабочий код. Он немного не в стиле Питона. А в стиле Питона не записывать ответ в массив а сразу его выдавать наружу (yield). Осторожнее, здесь водятся генераторы:

def answer(n, zeros):
    yield from range(zeros[0], 0, -1)
    it = iter(zeros)
    next(it)
    for i, j in zip(zeros, it):
        h = (j - i) // 2
        yield from range(h + 1)
        yield from range(j - i - h - 1, 0, -1)
    yield from range(n - zeros[-1])


n = int(input())
houses = input().split()
zeros = [i for i, v in enumerate(houses) if v == '0']
print(*answer(n, zeros))

БЛОГ НА HUSL

Алгоритмы на Python

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