Ближайший ноль

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

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

Ваша задача – помочь Тимофею посчитать искомые расстояния. Для этого у вас есть карта улицы. Дома в городе Тимофея нумеровались в том порядке, в котором строились, поэтому их номера на карте никак не упорядочены. Пустые участки обозначены нулями.

Формат ввода

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

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

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

def data_input():
    length_street = int(input())
    street = [int(num) for num in input().split(' ')]
    return length_street, street

def calculations():
    length_street, street = data_input()
    distance = []
    zero_position = None
    for i, elem in enumerate(street):
        if elem == 0:
            zero_position = i
            distance.append(0)
            continue
        if (elem != 0 and zero_position != None):
            distance.append(i - zero_position)
        else:
            distance.append(length_street)
    zero_position = None
    for i, elem in reversed(list(enumerate(street))):
        if elem == 0:
            zero_position = i
            continue
        if (elem != 0 and zero_position != None and distance[i] > zero_position - i):
            distance[i] = (zero_position - i)
    print(*distance)

if __name__ == '__main__':
    calculations()


Вы можете оставить комментарий, или Трекбэк с вашего сайта.

Оставить комментарий