Найти ближайший ноль

@Taron8117 · Регистрация: 01.09.2013

Студворк — интернет-сервис помощи студентам

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

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

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

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

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

Пример:
5
0 1 4 9 0
ответ: 0 1 2 1 0

Пример:
6
0 7 9 4 8 20
ответ: 0 1 2 3 4 5

Мой код:

Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
def nearest_zero(street_length, street_num):
    range_num = 10 ** 9
    result = [range_num] * street_length
    greater = range_num
    for x in range(street_length):
        if not street_num[x]:
            greater = 0
        result[x] = min(result[x], greater)
        greater += 1
 
    greater = range_num
    for x in range(street_length - 1, -1, -1):
        if not street_num[x]:
            greater = 0
        result[x] = min(result[x], greater)
        greater += 1
    return ' '.join(map(str, result))
 
 
street_length = int(input())
street_num = list(map(int, input().split()))
 
if __name__ == "__main__":
    print(nearest_zero(street_length, street_num))

Код работает, но от меня требуют более примитивное решение. Дайте подсказки пожалуйста, как можно примитивнее сделать?

@Gdez · 21.08.2021, 21:14

Taron8117,

Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
a = [0, 9, 1, 6, 0, 7, 3, 5, 2, 0, 0, 8, 4, 1, 0]
 
n = len(a)
zero_i = [i for i in range(n) if a[i] == 0]
 
i0 = zero_i[0]
i1 = zero_i[-1] if len(zero_i) == 1 else zero_i[1]
for i in range(i0):
    a[i] = i0-i
 
m = 1
for i in range(i0+1, zero_i[-1]):
    if a[i]:
        a[i] = min(i - i0, i1 - i)
    else:
        m += 1
        i0 = i1
        i1 = zero_i[m]
 
for i in range(i1+1, n):
    a[i] = i - i1
print(a)

Добавлено через 8 минут

Проще оказывается

Python
1
2
3
4
5
6
7
8
9
a = [0] + [0, 9, 6, 0, 7, 3, 6, 5, 2, 0, 0, 8, 4, 1] + [int(1e9)]
n = len(a)
for i in range(n-2,-1,-1):
    if a[i]:
        a[i] = a[i+1] + 1
for i in range(2, n):
    if a[i]:
        a[i] = min(a[i-1] + 1, a[i])
print(a[1:-1])

Добавлено через 1 час 4 минуты
...

@eaa · 21.08.2021, 21:52

Расстояния до нуля

Не по теме:

слышал звон, да не знает, где он

@u235 · 21.08.2021, 22:13

Еще вариант, но особо не тестировал..

Python
1
2
3
4
5
from itertools import accumulate
a = [5, 9, 1, 6, 0, 7, 3, 5, 2, 0, 0, 8, 4, 1, 0]
f=lambda x, y: (x+1)*(y>0)
ans=[min(i,j) for i,j in zip(list(accumulate(a, f)), list(accumulate(a[::-1], f))[::-1])]
print(ans)

@Taron8117 · 22.08.2021, 14:41 **[ТС]**

Gdez, u235, спасибо за помощь вам!

@Taron8117 · 05.09.2021, 20:23 **[ТС]**

привет! чтобы новую тему не создавать по этой же задаче, помогите пожалуйста разобраться с замечаниями.

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

Я не понимаю что значит сохранение результата явной формулы
мне нужно исправить задачу по этим замечаниям.

Основные пункты сделал, но просто с print(), но в функцию и в гтовую задачу собрать не могу, если не сложно помогите пожалуйста.

Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
houses = ['9', '9', '0', '9', '0', '9', '0', '9', '9']
zeroes = [i for i in range(len(houses)) if houses[i] == '0']
print(zeroes)
 
"""Цикл по домам до первого нулевого"""
for pos in range(zeroes[0]):
    print(pos)
 
 
"""Цикл по парам нулевых"""
for k in range(len(zeroes)-1):
    print(zeroes[k])
    """Цикл по домам между соседними нулевыми"""
    for pos in range(zeroes[k]+1, zeroes[k + 1]):
        print(pos)
 
 
"""Цикл по домам после последнего нулевого"""
for pos in range(zeroes[-1], len(houses)):
    print(pos)

Добавлено через 1 час 50 минут
кое-как сделал, но пока наполовину работает. Если не сложно подскажите где ошибка пожалуйста

Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
def nearest_zero(houses):
    output = [0] * len(houses)
    zeroes = [
        index for index, value in enumerate(houses) if houses[index] == 0
    ]
    # print(zeroes)
    for k in range(zeroes[0]):
        output[k] = 0
    for k in range(len(zeroes) - 1):
        output[k] = min(zeroes[k], zeroes[k + 1])
        for pos in range(zeroes[k] + 1, zeroes[k + 1]):
            output[pos] = pos
    for k in range(zeroes[-1], len(houses)):
        output[k] = k
    return output
 
 
if __name__ == '__main__':
    street_length = int(input())
    houses = list(map(int, input().split()))
    print(nearest_zero(houses))

@Gdez · 05.09.2021, 21:49

Taron8117,

Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
def nearest_zero(houses):
    output = [0] * len(houses)
    zeroes = [
        index for index, value in enumerate(houses) if value == 0
    ]
    #print(zeroes)
    for k in range(zeroes[0]):
        output[k] = zeroes[0] - k
    for k in range(len(zeroes) - 1):
        #output[k] = min(zeroes[k], zeroes[k + 1])
        for pos in range(zeroes[k] + 1, zeroes[k + 1]):
            output[pos] = min(pos - zeroes[k], zeroes[k + 1] - pos)
    for k in range(zeroes[-1] + 1, len(houses)):
        output[k] = k - zeroes[-1]
    return output
 
 
if __name__ == '__main__':
    street_length = int(input())
    houses = list(map(int, input().split()))
    print(nearest_zero(houses))

@Taron8117 · 05.09.2021, 21:59 **[ТС]**

Спасибо вам огромное!

@pavelsokg6 · 18.02.2022, 14:30

Всем привет, решил не создавать новую тему, т.к. вопрос по этой же задаче. Помогите пожалуйста исправить замечания:

Сделать функцию универсальной и чистой, чтобы в ней был только алгоритм. Ввод и вывод данных вынести.
Избавиться от append, заранее подготовить список. Заполнить его нулями, а дальше изменять значение элементов

Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
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()

@Iprojekt · 14.04.2023, 15:06

Мучаюсь с этой же задачкой. Можете посдказать как сделать по плану?

План
1. Потратить один проход на нахождение всех мест, где находятся нулевые значения. Попробуй сделать это одним присвоением (list comprehension).
2. Разобрать три случая (вместе они дадут еще ровно один проход):
– Перебор позиций домов до первого нулевого.
– Перебор позиций домов между соседними нулевыми.
– Перебор позиций домов после последнего нулевого.
3. Для каждого дома будет известно положение ближайшего нулевого или ближайших двух.
Можно будет их использовать для явного вычисления расстояния.

Желательно без map/filter/zip

И можете обьяснить как он работает(Я вот сижу и вообще не понимаю как задачки решать)

@eaa · 14.04.2023, 18:27

Ближайший ноль
и смотри 3 пост, я там дал ссылку на алгоритм.

Новые блоги и статьи Все статьи Все блоги /
Установка Qt Creator для C и C++: ставим среду, CMake и MinGW без фреймворка Qt 8Observer8 05.04.2026 Среду разработки Qt Creator можно установить без фреймворка Qt. Есть отдельный репозиторий для этой среды: https:/ / github. com/ qt-creator/ qt-creator, где можно скачать установщик, на вкладке Releases:. . .	AkelPad-скрипты, структуры, и немного лирики.. testuser2 05.04.2026 Такая программа, как AkelPad существует уже давно, и также давно существуют скрипты под нее. Тем не менее, прога живет, периодически что-то не спеша дополняется, улучшается. Что меня в первую очередь. . .	Отображение реквизитов в документе по условию и контроль их заполнения Maks 04.04.2026 Алгоритм из решения ниже реализован на примере нетипового документа "ПланированиеСпецтехники", разработанного в конфигурации КА2. Данный документ берёт данные из другого нетипового документа. . .	Фото всей Земли с борта корабля Orion миссии Artemis II kumehtar 04.04.2026 Это первое подобное фото сделанное человеком за 50 лет. Снимок называют новым вариантом легендарной фотографии «The Blue Marble» 1972 года, сделанной с борта корабля «Аполлон-17». Новое фото. . .
Вывод диалогового окна перед закрытием, если документ не проведён Maks 04.04.2026 Алгоритм из решения ниже реализован на примере нетипового документа "СписаниеМатериалов", разработанного в конфигурации КА2. Задача: реализовать программный контроль на предмет проведения документа. . .	Программный контроль заполнения реквизитов табличной части документа Maks 02.04.2026 Алгоритм из решения ниже реализован на примере нетипового документа "СписаниеМатериалов", разработанного в конфигурации КА2. Задача: 1. Реализовать контроль заполнения реквизита. . .	wmic не является внутренней или внешней командой Maks 02.04.2026 Решение: DISM / Online / Add-Capability / CapabilityName:WMIC~~~~ Отсюда: https:/ / winitpro. ru/ index. php/ 2025/ 02/ 14/ komanda-wmic-ne-naydena/	Программная установка даты и запрет ее изменения Maks 02.04.2026 Алгоритм из решения ниже реализован на примере нетипового документа "СписаниеМатериалов", разработанного в конфигурации КА2. Задача: при создании документов установить период списания автоматически. . .

@eaa Status 418 4584 / 2350 / 601 Регистрация: 26.11.2017 Сообщений: 5,262 Записей в блоге: 3
	21.08.2021, 21:52
	Расстояния до нуля Не по теме: слышал звон, да не знает, где он 0

@Taron8117 0 / 0 / 0 Регистрация: 01.09.2013 Сообщений: 23
	22.08.2021, 14:41 [ТС]
	Gdez, u235, спасибо за помощь вам! 0

@Taron8117 0 / 0 / 0 Регистрация: 01.09.2013 Сообщений: 23
	05.09.2021, 21:59 [ТС]
	Спасибо вам огромное! 0

@Iprojekt 0 / 0 / 0 Регистрация: 14.04.2023 Сообщений: 3
	14.04.2023, 15:06
	Мучаюсь с этой же задачкой. Можете посдказать как сделать по плану? План 1. Потратить один проход на нахождение всех мест, где находятся нулевые значения. Попробуй сделать это одним присвоением (list comprehension). 2. Разобрать три случая (вместе они дадут еще ровно один проход): – Перебор позиций домов до первого нулевого. – Перебор позиций домов между соседними нулевыми. – Перебор позиций домов после последнего нулевого. 3. Для каждого дома будет известно положение ближайшего нулевого или ближайших двух. Можно будет их использовать для явного вычисления расстояния. Желательно без map/filter/zip И можете обьяснить как он работает(Я вот сижу и вообще не понимаю как задачки решать) 0

@eaa Status 418 4584 / 2350 / 601 Регистрация: 26.11.2017 Сообщений: 5,262 Записей в блоге: 3
	14.04.2023, 18:27
	Ближайший ноль и смотри 3 пост, я там дал ссылку на алгоритм. 0

Найти ближайший ноль

Решение