Форум программистов
 

Восстановите пароль или Зарегистрируйтесь на форуме, о проблемах и с заказом рекламы пишите сюда - alarforum@yandex.ru, проверяйте папку спам!

Вернуться   Форум программистов > Скриптовые языки программирования > Python
Регистрация

Восстановить пароль
Повторная активизация e-mail

Купить рекламу на форуме - 42 тыс руб за месяц

Ответ
 
Опции темы Поиск в этой теме
Старый 14.04.2021, 02:59   #1
eikturnir
Новичок
Джуниор
 
Регистрация: 14.04.2021
Сообщений: 4
По умолчанию Ремонт дороги

Ремонт дороги
Длина автомобильной дороги составляет N километров. Часть дороги необходимо отремонтировать. При обследовании дорога была разбита на N участков длиной 1 километр, и для каждого участка было определено, нуждается ли он в ремонте или нет, после чего был составлен план дороги, на котором отмечены участки, нуждающиеся в ремонте.

Для ремонта дороги можно привлечь несколько компаний-подрядчиков. Каждая компания может отремонтировать только непрерывный фрагмент дороги. При этом из-за требований антимонопольного законодательства длина фрагмента дороги, который ремонтирует одна компания, не должна превышать L километров (даже если на фрагменте, который ремонтирует одна компания, есть не нуждающиеся в ремонте участки, общая длина данного фрагмента не должна превышать L километров).

Определите, какое наименьшее количество компаний-подрядчиков необходимо привлечь для ремонта дороги.

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

Первая строка входных данных содержит целое число L ( L> 0 ) — максимальную длину фрагмента дороги, который может отремонтировать одна компания. Во второй строке входных данных записано целое число N ( N> 0 ) — длина всей дороги. Следующие N строк содержат по одному числу, равному 0 или 1. Число 1 обозначает, что соответствующий участок дороги нуждается в ремонте, число 0 — что участок не требует ремонта.

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

Программа должна вывести одно целое число — минимальное количество компаний-подрядчиков, которое необходимо привлечь для ремонта дороги.

Примечание

В тесте из примера первая компания может отремонтировать участок номер 3, вторая компания — участки с 5 по 7.

Примеры
Ввод
3
8
0
0
1
0
1
0
1
0
Вывод
2
Решение №1
Код:
S = int(input())
dor = [int(input()) for _ in range(int(input()))]
if any(dor):
    Otvet = 1
    p = dor.index(1)
    q = len(dor) - dor[::-1].index(1)
    while p + S < q:
        Otvet += 1
        p = p + S + dor[p + S:].index(1)
    print(Otvet)
else:
    print(0)
Решение №2
Код:
l = int(input())
n = int(input())
isWork = False
currl = 0
kb = 0
a = []
for i in range(n):
        b = int(input())
        a.append(b)
for i in range(n):
        if a[i] == 0:
            if isWork == True:
                currl += 1
                if currl >= l:
                    isWork = False
                    currl = 0
        else:
            if isWork == True:
                currl += 1
                if currl >= l:
                    isWork = False
                    currl = 0
            else:
                currl += 1
                kb += 1
                isWork = True
print(kb)
В компиляторе все красиво, но в проверщике выдает ошибку "Программа выполнялась слишком долго и была прервана"

Помогите разобраться?!
eikturnir вне форума Ответить с цитированием
Старый 14.04.2021, 08:46   #2
Ципихович Эндрю
Старожил
 
Регистрация: 24.01.2011
Сообщений: 3,034
По умолчанию

Цитата:
Сообщение от eikturnir Посмотреть сообщение
но в проверщике выдает ошибку
4 темы с этой формулировкой-может проверяльщик плохой?
Ципихович Эндрю вне форума Ответить с цитированием
Старый 14.04.2021, 12:25   #3
FrosyaZZ
Форумчанин
 
Регистрация: 16.11.2020
Сообщений: 243
По умолчанию

Цитата:
Сообщение от eikturnir Посмотреть сообщение
Решение №1
Проверьте, на N, L - любые и все 0

Цитата:
Сообщение от eikturnir Посмотреть сообщение
Решение №2
Пропускаете куски, когда случается
Код:
currl >= l
Выдаст 0, если хватает одной компании для ремонта.
FrosyaZZ вне форума Ответить с цитированием
Ответ


Купить рекламу на форуме - 42 тыс руб за месяц

Опции темы Поиск в этой теме
Поиск в этой теме:

Расширенный поиск


Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
Дороги Великобритании Utkin Свободное общение 53 14.04.2016 08:29
Дороги и виноватые... mv28jam Свободное общение 6 27.05.2015 18:53
Задача про дороги makskovalko Помощь студентам 1 09.12.2013 22:05
Дураки и дороги. ImmortalAlexSan Свободное общение 16 12.07.2011 19:07
Иммитация железной дороги (Анна) Паскаль, Turbo Pascal, PascalABC.NET 4 22.01.2011 11:39