Космическая связь

@nikita23123 · Регистрация: 05.11.2021

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

Помогите пожалуйста, натолкните на мысль

Космическая связь
В этой задаче от вас потребуется написать программу для составления расписания сеансов связи со спутником. Каждый сеанс заключается в обмене короткими сообщениями, поэтому мы считаем, что он происходит мгновенно. Поскольку ресурсы оборудования ограничены, следует стремиться к минимизации количества сеансов. Вместе с тем, интервал времени между сеансами не должен превышать d миллисекунд. Кроме того, существуют промежутки времени, в течении которых связь невозможна. При этом на границах промежутка мгновенный сеанс связи возможен. Расписание составляется на ttмиллисекунд. Первый сеанс должен обязательно состояться в момент 0, а последний — в момент t.

Рассмотрим пример. Пусть t=100, d=20 и задано 3 промежутка недоступности связи: (5;25), (27;40), (75;90)). Тогда потребуется восемь сеансов связи, которые можно провести в моменты времени 0, 5, 25,45, 65, 75,90,100. Конкретное расписание может быть другим, но в любом случае количество сеансов не может быть меньше восьми.

Ваша программа должна по имеющейся информации найти минимальное возможное количество сеансов связи.

Формат входных данных
В первой строке через пробел записаны три натуральных числа n, d и t — количество интервалов недоступности связи, максимальный интервал между между сеансами и время, на которое составляется расписание.
Далее в n строках заданы по два целых неотрицательных числа ai
и bi
— начало и конец каждого интервала недоступности связи. bi-ai

≤d. Интервалы недоступности связи не пересекаются, каждый следующий интервал начинается строго после окончания предыдущего. a_1

Формат выходных данных
Вывести одно число — количество сеансов связи в графике.

Sample Input:
3 20 100
5 25
27 40
75 90

Sample Output:
8

@Zeropus1 · 07.11.2021, 10:04

Python
1
2
3
4
5
6
7
8
9
10
11
12
n = int(n)
d = int(d)
t = int(t)
sv = []
for i in range(n):
    a,b = input().split()
    a = int(a)
    b = int(b)
    x = b-a
    sv.append(x)
z = ((t-sum(sv))//d)+6
print(z)

это только на 0.8 балов
помогите пожалуйста)

Добавлено через 13 минут
там сверху еще

Python
1
n,d,t = input().split()

@anton78spb · 07.11.2021, 10:09

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

Потому что это последние задание олимпиады - как правило всегда самое сложное

Какая-то очень слабенькая олимпиада, если это задание в ней самое сложное.

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

помогите пожалуйста)

Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
t = 100
d = 20
p = [(5, 25), (27, 40), (75, 90)]
c = 0
i = 0
r = []
while c < t:
    r.append(c)
    c += d
    for j in p:
        if j[0] < c < j[1]:
            c = j[0]
        
r.append(t)
print(len(r))

@Zeropus1 · 07.11.2021, 10:40

спасибо)

Добавлено через 26 минут
все равно 0.8

@montelnRoben · 07.11.2021, 11:11

anton78spb, в качестве входных данных используются случайные числа. Эти числа были даны только в качестве примера. Нужно разработать прогу которая способна работать со всей областью их определения

@MaMush · 07.11.2021, 12:05

Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
n, d, t = map(int, input().split())
p =[list(map(int, input().split())) for i in range(n)]
c = 0
i = 0
r = []
while c < t:
    r.append(c)
    c += d
    for j in p:
        if j[0] < c < j[1]:
            c = j[0]
        
r.append(t)
print(len(r))

Вот с инпутом. Набрало 8/20 баллов. Дальше только по времени.

@eaa · 07.11.2021, 12:31

ограничения какие в задаче?

@anton78spb · 07.11.2021, 12:35

eaa, у меня ушло меньше времени чем на прочтение задание чтобы наговнокодить то что я выложил выше.
Написал я это исключительно после прочтения фразы.

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

тут я даже не знаю за что зацепиться

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

все равно 0.8

К сожалению мне это ничего не говорит.

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

Дальше только по времени.

Вот так попробуйте.

Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
t = 100
d = 20
p = [(5, 25), (27, 40), (75, 90)]
c = 0
i = 0
r = []
while c < t:
    r.append(c)
    c += d
    for j in p:
        if j[0] < c < j[1]:
            c = j[0]
            break
 
r.append(t)
 
# print(len(r))
print(r)

Если не прокатит оптимизируйте дальше. Уберите проверку по всем интервалам с самого начала, проверяйте только по актуальному на текущий момент.

@Zeropus1 · 07.11.2021, 12:36

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

огранадаче?

Программа проверяется на 25 тестах. Прохождение каждого теста оценивается в 0.8 балла. Тест из условия задачи при проверке не используется.
В первых десяти тестах t≤1000. В следующих 15 тестах t≤10^6

@eaa · 07.11.2021, 12:39

на N какие ограничения?

@Zeropus1 · 07.11.2021, 12:41

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

на N какие ограничения?

n≤200000

@anton78spb · 07.11.2021, 12:42

MaMush, Случайно скопировал не тот вариант. Вот нужный.

Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
n, d, t = map(int, input().split())
p =[list(map(int, input().split())) for i in range(n)]
c = 0
i = 0
r = []
while c < t:
    r.append(c)
    c += d
    for j in p:
        if j[0] < c < j[1]:
            c = j[0]
            break
 
r.append(t)
print(len(r))

@Zeropus1 · 07.11.2021, 12:45

нет 8/20

@IlyxM15 · 07.11.2021, 13:02

у меня такая же фигня, сколько бы не оптимизировал дальше 10 не проходит

@eaa · 07.11.2021, 13:03

Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
n, d, t = map(int, input().split())
p = [tuple(map(int, input().split())) for _ in range(n)]
p.sort(reverse=True)
c = 0
res = 1
while c < t:
    res += 1
    c += d
    if p:
        a, b = p[-1]
        if a < c < b:
            c = a
            p.pop()
        if c > b:
            p.pop()
print(res)

не знаю зайдет ли такое на python'e. O(t).
но можно это по другому решить, а можно и это решение ускорить.

@Zeropus1 · 07.11.2021, 13:14

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

n, d, t = map(int, input().split())
p = [tuple(map(int, input().split())) for _ in range(n)]
p.sort(reverse=True)
c = 0
res = 1
while c < t:
res += 1
c += d
if p:
a, b = p[-1]
if a < c < b:
c = a
p.pop()
if c > b:
p.pop()
print(res)

прошло на 4 теста и все

@iVan22822 · 07.11.2021, 13:17

у кого то получилось???

@Zeropus1 · 07.11.2021, 13:19

только на 8 баллов

@anton78spb · 07.11.2021, 13:33

Zeropus1, Так попробуйте.

Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
n, d, t = map(int, input().split())
p =[list(map(int, input().split())) for i in range(n)]
 
c = 0
i = 0
r = []
while c < t:
    r.append(c)
    c += d
    for j in range(i, n):
        if p[j][0] < c < p[j][1]:
            c = p[j][0]
            i = j
            break
 
r.append(t)
print(len(r))

Добавлено через 3 минуты
Zeropus1, А еще лучше, киньте ссылку на "проверялку" для данного задания. Хочется самому посмотреть как это работает. Да и попробовать, перед тем как сюда кидать каждый вариант.

@IlyxM15 · 07.11.2021, 13:35

Тоже только 10 из 25 проходит ,остальные time limit exceeded

Новые блоги и статьи Все статьи Все блоги /
Переходник USB-CAN-GPIO Eddy_Em 20.03.2026 Достаточно давно на работе возникла необходимость в переходнике CAN-USB с гальваноразвязкой, оный и был разработан. Однако, все меня терзала совесть, что аж 48-ногий МК используется так тупо: просто. . .	Оттенки серого Argus19 18.03.2026 Оттенки серого Нашёл в интернете 3 прекрасных модуля: Модуль класса открытия диалога открытия/ сохранения файла на Win32 API; Модуль класса быстрого перекодирования цветного изображения в оттенки. . .	SDL3 для Desktop (MinGW): Рисуем цветные прямоугольники с помощью рисовальщика SDL3 на Си и C++ 8Observer8 17.03.2026 Содержание блога Финальные проекты на Си и на C++: finish-rectangles-sdl3-c. zip finish-rectangles-sdl3-cpp. zip	Символические и жёсткие ссылки в Linux. algri14 15.03.2026 Существует два типа ссылок — символические и жёсткие. Ссылка в Linux — это запись в каталоге, которая может указывать либо на inode «файла-ИСТОЧНИКА», тогда это будет «жёсткая ссылка» (hard link),. . .
[Owen Logic] Поддержание уровня воды в резервуаре количеством включённых насосов: моделирование и выбор регулятора ФедосеевПавел 14.03.2026 Поддержание уровня воды в резервуаре количеством включённых насосов: моделирование и выбор регулятора ВВЕДЕНИЕ Выполняя задание на управление насосной группой заполнения резервуара,. . .	делаю науч статью по влиянию грибов на сукцессию anaschu 13.03.2026 прикрепляю статью	SDL3 для Desktop (MinGW): Создаём пустое окно с нуля для 2D-графики на SDL3, Си и C++ 8Observer8 10.03.2026 Содержание блога Финальные проекты на Си и на C++: hello-sdl3-c. zip hello-sdl3-cpp. zip Результат:	Установка CMake и MinGW 13.1 для сборки С и C++ приложений из консоли и из Qt Creator в EXE 8Observer8 10.03.2026 Содержание блога MinGW - это коллекция инструментов для сборки приложений в EXE. CMake - это система сборки приложений. Здесь описаны базовые шаги для старта программирования с помощью CMake и. . .

@nikita23123 0 / 0 / 0 Регистрация: 05.11.2021 Сообщений: 1

	Космическая связь 05.11.2021, 18:02. Показов 18133. Ответов 60 Метки python 3, Задачи (Все метки) Помогите пожалуйста, натолкните на мысль Космическая связь В этой задаче от вас потребуется написать программу для составления расписания сеансов связи со спутником. Каждый сеанс заключается в обмене короткими сообщениями, поэтому мы считаем, что он происходит мгновенно. Поскольку ресурсы оборудования ограничены, следует стремиться к минимизации количества сеансов. Вместе с тем, интервал времени между сеансами не должен превышать d миллисекунд. Кроме того, существуют промежутки времени, в течении которых связь невозможна. При этом на границах промежутка мгновенный сеанс связи возможен. Расписание составляется на ttмиллисекунд. Первый сеанс должен обязательно состояться в момент 0, а последний — в момент t. Рассмотрим пример. Пусть t=100, d=20 и задано 3 промежутка недоступности связи: (5;25), (27;40), (75;90)). Тогда потребуется восемь сеансов связи, которые можно провести в моменты времени 0, 5, 25,45, 65, 75,90,100. Конкретное расписание может быть другим, но в любом случае количество сеансов не может быть меньше восьми. Ваша программа должна по имеющейся информации найти минимальное возможное количество сеансов связи. Формат входных данных В первой строке через пробел записаны три натуральных числа n, d и t — количество интервалов недоступности связи, максимальный интервал между между сеансами и время, на которое составляется расписание. Далее в n строках заданы по два целых неотрицательных числа ai и bi — начало и конец каждого интервала недоступности связи. bi-ai ≤d. Интервалы недоступности связи не пересекаются, каждый следующий интервал начинается строго после окончания предыдущего. a_1 Формат выходных данных Вывести одно число — количество сеансов связи в графике. Sample Input: 3 20 100 5 25 27 40 75 90 Sample Output: 8 0

@Zeropus1 0 / 0 / 0 Регистрация: 07.11.2021 Сообщений: 21
	07.11.2021, 10:40
	спасибо) Добавлено через 26 минут все равно 0.8 0

@montelnRoben 0 / 0 / 0 Регистрация: 07.11.2021 Сообщений: 3
	07.11.2021, 11:11
	anton78spb, в качестве входных данных используются случайные числа. Эти числа были даны только в качестве примера. Нужно разработать прогу которая способна работать со всей областью их определения 0

@eaa Status 418 4584 / 2350 / 601 Регистрация: 26.11.2017 Сообщений: 5,262 Записей в блоге: 3
	07.11.2021, 12:31
	ограничения какие в задаче? 0

@eaa Status 418 4584 / 2350 / 601 Регистрация: 26.11.2017 Сообщений: 5,262 Записей в блоге: 3
	07.11.2021, 12:39
	на N какие ограничения? 0

@Zeropus1 0 / 0 / 0 Регистрация: 07.11.2021 Сообщений: 21
	07.11.2021, 12:45
	нет 8/20 0

@IlyxM15 0 / 0 / 0 Регистрация: 05.04.2020 Сообщений: 15
	07.11.2021, 13:02
	у меня такая же фигня, сколько бы не оптимизировал дальше 10 не проходит 0

@iVan22822 -18 / 0 / 0 Регистрация: 06.11.2021 Сообщений: 15
	07.11.2021, 13:17
	у кого то получилось??? 0

@Zeropus1 0 / 0 / 0 Регистрация: 07.11.2021 Сообщений: 21
	07.11.2021, 13:19
	только на 8 баллов 0

@IlyxM15 0 / 0 / 0 Регистрация: 05.04.2020 Сообщений: 15
	07.11.2021, 13:35
	Тоже только 10 из 25 проходит ,остальные time limit exceeded 0