Ремонт дороги

@ravix46 · Регистрация: 29.01.2020

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

Задание 3 Ремонт дороги
Участок автомагистрали длиной 1000 км ремонтируют несколько бригад рабочих.
Каждая бригада приступает к ремонту своего участка только тогда, когда предыдущая
бригада завершила работу. Ремонт дороги заключается в том, что рабочие снимают
асфальт с заасфальтированных участков и укладывают асфальт там, где его раньше не
было.
До начала ремонта вся автомагистраль была заасфальтирована. Бригада получает
наряд на ремонт в виде интервала [a, b), где a и b – расстояние от начала участка в
миллиметрах.
Требуется найти самую большую длину заасфальтированного участка
автомагистрали, оставшегося после завершения ремонта.

Входные данные:
Первая строка содержит число N (1<=N<=100) – количество нарядов на ремонт
дороги.
Затем следуют N строк, каждая их которых содержит два числа – границы
интервалов для одной бригады.

Выходные данные:
Одно число – длина самого большого заасфальтированного участка.

Пример ввода:
4
20 50
10 35
40 90
100 1000000000

Пример вывода:
15

@eaa · 31.01.2020, 10:47

Храните заасфальтированные участки в виде списка кортежей левая и правая граница (L, R)
На каждом шаге просматриваете и изменяете список в зависимости от входных данных.
В конце находите максимум из длин всех участков.

дано:
[0, 1000000000) - заасфальтировано.
1-й шаг:
[0,20) U [50, 1000000000) - заасфальтированные участки
2-й шаг:
[0,10) U [20,35) U [50, 1000000000) - заасфальтированные участки
3-й шаг:
[0,10) U [20,35) U [40, 50) U [90, 1000000000) - заасфальтированные участки
4-й шаг:
[0,10) U [20,35) U [40, 50) U [90, 100) - заасфальтированные участки

Максимальный участок [20, 35) его длина 15.

Рыжий Лис · 31.01.2020, 10:58

Python
1
2
3
4
5
>>> set(list(range(20,50)) + list(range(10,35)) + list(range(40,90)))
{10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 
30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 
50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 64, 65, 66, 67, 68, 69,
70, 71, 72, 73, 74, 75, 76, 77, 78, 79, 80, 81, 82, 83, 84, 85, 86, 87, 88, 89}

Считаем длину каждого участка и находим максимум.

@eaa · 31.01.2020, 11:23

Рыжий Лис, там миллиард в ограничениях

@avgoor · 31.01.2020, 17:52

Сообщение от eaa

Храните заасфальтированные участки в виде списка кортежей левая и правая граница (L, R)
На каждом шаге просматриваете и изменяете список в зависимости от входных данных.
В конце находите максимум из длин всех участков.

Можно проще.
Берем список [0, длина дороги]. Добавляем в него все границы нарядов. Сортируем. Оставляем в списке в единственном экземпляре только те числа, которые встречаются нечетное число раз. Все. В списке заасфальтированные участки в формате [начало1, конец1, начало2, конец2,...]

@TAVulator · 31.01.2020, 19:08

попытался решить просто логически-математически )
потестите, если кому не лень, самому интересно )

Python
1
2
3
4
5
6
7
8
9
10
11
12
13
#исходные данные
n = 4
a = [20,50,10,35,40,90,100,1000000000]
#==============
x = 1000000000 - (max(a)-min(a))
a = [0,1000000000] + a
print(a[2:])
for i in range(n):
    for j in range(n+i):
        if a[i+2] < a[j] and a[i+3] >= a[j]:
            if (a[i+3]-a[j]) > x:
                x = a[i+3]-a[j]
print(x)

логика:

Кликните здесь для просмотра всего текста

0 1000000000
мах = 1000000000
мин = 10
мах-мин=9999999990
1000000000-999999990=10
20 50
если 20 < 0 и 50 >= 0 то фейл
20 < 100000 и 50 >= 100000 то фейл
10 35
если 10 < 20 и 35 >= 20 то ххх = 35-20=15
10 < 50 и 35 >= 50 то фейл
если 10 < 0 и 35 >= 0 то фейл
10 < 1000000000 и 35 >= 1000000000 то фейл

40 90
если 40 < 10 и 90 >= 10 то фейл
если 40 < 35 и 90 >= 35 то фейл
если 40 < 20 и 90 >= 20 то фейл
если 40 < 50 и 90 >= 50 то ххх = 90-50=10
если 40 < 0 и 90 >= 0 то фейл
если 40 < 1000000000 и 90 >= 1000000000 то фейл

100 1000000000
если 100 < 40 и 1000000000 >= 40 то фейл
если 100 < 90 и 1000000000 >= 90 то фейл
если 100 < 10 и 1000000000 >= 10 то фейл
если 100 < 35 и 1000000000 >= 35 то фейл
если 100 < 20 и 1000000000 >= 20 то фейл
если 100 < 50 и 1000000000 >= 50 то фейл
если 100 < 0 и 1000000000 >= 0 то фейл
если 100 < 1000000000 и 1000000000 >= 1000000000 то ххх = 1000000000-1000000000=0
Итого самое большое из всех не фейлов = 15

Новые блоги и статьи Все статьи Все блоги /
Thinkpad X220 Tablet — это лучший бюджетный ноутбук для учёбы, точка. Programma_Boinc 23.12.2025 Рецензия / Мнение/ Перевод Ниже машинный перевод статьи The Thinkpad X220 Tablet is the best budget school laptop period . Thinkpad X220 Tablet — это лучший бюджетный ноутбук для учёбы,. . .	PhpStorm 2025.3: WSL Terminal всегда стартует в ~ and_y87 14.12.2025 PhpStorm 2025. 3: WSL Terminal всегда стартует в ~ (home), игнорируя директорию проекта Симптом: После обновления до PhpStorm 2025. 3 встроенный терминал WSL открывается в домашней директории. . .	Как объединить две одинаковые БД Access с разными данными VikBal 11.12.2025 Помогите пожалуйста !! Как объединить 2 одинаковые БД Access с разными данными.	Новый ноутбук volvo 07.12.2025 Всем привет. По скидке в "черную пятницу" взял себе новый ноутбук Lenovo ThinkBook 16 G7 на Амазоне: Ryzen 5 7533HS 64 Gb DDR5 1Tb NVMe 16" Full HD Display Win11 Pro	Музыка, написанная Искусственным Интеллектом volvo 04.12.2025 Всем привет. Некоторое время назад меня заинтересовало, что уже умеет ИИ в плане написания музыки для песен, и, собственно, исполнения этих самых песен. Стихов у нас много, уже вышли 4 книги, еще 3. . .
От async/await к виртуальным потокам в Python IndentationError 23.11.2025 Армин Ронахер поставил под сомнение async/ await. Создатель Flask заявляет: цветные функции - провал, виртуальные потоки - решение. Не threading-динозавры, а новое поколение лёгких потоков. Откат?. . .	Поиск "дружественных имён" СОМ портов Argus19 22.11.2025 Поиск "дружественных имён" СОМ портов На странице: https:/ / norseev. ru/ 2018/ 01/ 04/ comportlist_windows/ нашёл схожую тему. Там приведён код на С++, который показывает только имена СОМ портов, типа,. . .	Сколько Государство потратило денег на меня, обеспечивая инсулином. Programma_Boinc 20.11.2025 Сколько Государство потратило денег на меня, обеспечивая инсулином. Вот решила сделать интересный приблизительный подсчет, сколько государство потратило на меня денег на покупку инсулинов. . . .	Ломающие изменения в C#.NStar Alpha Etyuhibosecyu 20.11.2025 Уже можно не только тестировать, но и пользоваться C#. NStar - писать оконные приложения, содержащие надписи, кнопки, текстовые поля и даже изображения, например, моя игра "Три в ряд" написана на этом. . .	Мысли в слух kumehtar 18.11.2025 Кстати, совсем недавно имел разговор на тему медитаций с людьми. И обнаружил, что они вообще не понимают что такое медитация и зачем она нужна. Самые базовые вещи. Для них это - когда просто люди. . .

@ravix46 0 / 0 / 0 Регистрация: 29.01.2020 Сообщений: 8

	Ремонт дороги 30.01.2020, 18:52. Показов 2892. Ответов 5 Метки python, задача (Все метки) Задание 3 Ремонт дороги Участок автомагистрали длиной 1000 км ремонтируют несколько бригад рабочих. Каждая бригада приступает к ремонту своего участка только тогда, когда предыдущая бригада завершила работу. Ремонт дороги заключается в том, что рабочие снимают асфальт с заасфальтированных участков и укладывают асфальт там, где его раньше не было. До начала ремонта вся автомагистраль была заасфальтирована. Бригада получает наряд на ремонт в виде интервала [a, b), где a и b – расстояние от начала участка в миллиметрах. Требуется найти самую большую длину заасфальтированного участка автомагистрали, оставшегося после завершения ремонта. Входные данные: Первая строка содержит число N (1<=N<=100) – количество нарядов на ремонт дороги. Затем следуют N строк, каждая их которых содержит два числа – границы интервалов для одной бригады. Выходные данные: Одно число – длина самого большого заасфальтированного участка. Пример ввода: 4 20 50 10 35 40 90 100 1000000000 Пример вывода: 15 0

@eaa Status 418 4584 / 2350 / 601 Регистрация: 26.11.2017 Сообщений: 5,262 Записей в блоге: 3
	31.01.2020, 10:47
	Храните заасфальтированные участки в виде списка кортежей левая и правая граница (L, R) На каждом шаге просматриваете и изменяете список в зависимости от входных данных. В конце находите максимум из длин всех участков. дано: [0, 1000000000) - заасфальтировано. 1-й шаг: [0,20) U [50, 1000000000) - заасфальтированные участки 2-й шаг: [0,10) U [20,35) U [50, 1000000000) - заасфальтированные участки 3-й шаг: [0,10) U [20,35) U [40, 50) U [90, 1000000000) - заасфальтированные участки 4-й шаг: [0,10) U [20,35) U [40, 50) U [90, 100) - заасфальтированные участки Максимальный участок [20, 35) его длина 15. 0

@eaa Status 418 4584 / 2350 / 601 Регистрация: 26.11.2017 Сообщений: 5,262 Записей в блоге: 3
	31.01.2020, 11:23
	Рыжий Лис, там миллиард в ограничениях 0