Форум программистов, компьютерный форум, киберфорум
Python для начинающих
Войти
Регистрация
Восстановить пароль
 
Рейтинг 4.60/5: Рейтинг темы: голосов - 5, средняя оценка - 4.60
1 / 1 / 0
Регистрация: 25.03.2019
Сообщений: 2
1

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

25.03.2019, 19:41. Просмотров 1055. Ответов 1
Метки нет (Все метки)


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

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

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

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

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

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

Ограничения и система оценивания

Решение, правильно работающее в случае, когда числа L и N не превосходят 10, будет оцениваться в 30 баллов.

Решение, правильно работающее в случае, когда числа L и N не превосходят 1000, будет оцениваться в 60 баллов.

Решение, правильно работающее в случае, когда числа L и N не превосходят 10 5 , будет оцениваться в 100 баллов.

Примеры
входные данные
3
8
0
0
1
0
1
0
1
0
выходные данные
2
помогите пожалуйста
почему то проходит не все тесты
не могу разобраться
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
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)
0
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
25.03.2019, 19:41
Ответы с готовыми решениями:

Определить, какое наименьшее число операций необходимо для того, чтобы получить из числа 1 заданное число N
Калькулятор выполняет 3 операции: Прибавить к числу единицу. Умножить число на 2. Умножить число...

Определить, какое наименьшее количество компаний-подрядчиков необходимо привлечь для ремонта дороги
Добрый вечер. Не понимаю как решить представленную задачу на informatics. Можете помочь решить.. а...

Определить какое наименьшее количество плит понадобится для замощения площади
Хао форумчанам! На днях столкнулся с задачкой, которую вроде бы решил, но Online judge system при...

Определить, какое количество видеопамяти необходимо для корректной работы сотового телефона
Сотовый телефон (коммуникатор) имеет следующие параметры экрана: ширина дисплея 128 высота дисплея...

1
Эксперт Python
4436 / 1871 / 342
Регистрация: 17.03.2012
Сообщений: 9,644
Записей в блоге: 5
26.03.2019, 10:13 2
Задача на динамическое программирование.
Больше писать пока не буду, ибо эти слова обычно не вызывают никакого отклика и идут в пустоту.

И да, используйте теги оформления кода.
0
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
26.03.2019, 10:13

Заказываю контрольные, курсовые, дипломные и любые другие студенческие работы здесь или здесь.

Определить какое наименьшее количество новых паспортов придется выпустить
условие В некотором королевстве есть N провинций. Король пожелал объединить все их под своей...

Определить за какое наименьшее время можно распечатать заданное количество грамот
У жюри одной олимпиады есть три принтера, первый печатает грамоту за 5 минут, второй за 7 минут,...

Определить, за какое наименьшее количество вопросов можно угадать задуманное число
Помогите пожалуйста. Некто загадал число от 1 до N. За какое наименьшее количество вопросов (на...

Маршрутное такси: Определить, какое наименьшее количество пассажиров придется пересадить
Маршрутное такси В час пик на остановку одновременно подъехали три маршрутных такси, следующие по...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
2
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2021, vBulletin Solutions, Inc.