Имея логи всех каналов, определить периоды когда все каналы были заняты

@mamba12 · Регистрация: 14.10.2021

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

Имеется сервер, имеющий N каналов для подключений клиентов. Когда клиент не подключен к каналу, канал простаивает. Когда к каналу подключен клиент, он считается занятым, и к нему нельзя подключиться. Каждый канал ведет текстовый лог подключений/отключений клиентов, следующего вида:

4 22 59 <...>

Каждая запись данного лога – это временная метка в секундах от старта сервера. Нечетные записи (по порядку, а не по значению) – подключения, четные – отключения. В данном примере имеем лог канала, к которому на 4-ой секунде подключился клиент, на 22 секунде – отключился, и на 59 секунде – подключился, то есть сейчас этот канал занят.

Для определенности все эти периоды являются полуинтервалами: левая граница включена в период подключения, а правая не включена. Т.е. если лог имеет вид 1 2 2 4, то это значит что канал был занят с 1 по 4 секунду.

Необходимо имея логи всех каналов, определить периоды когда все каналы были заняты.

Формат описания входных данных:
В первой строке записано количество каналов N. В следующих строках описания каждого из N логов.
Каждое описание логов состоит из двух строк:

кол-во записей в логе
записи в логе, разделенные пробелом
Гарантируется, что в каждом логе четное количество записей и что лог отсортирован в неубывающем порядке.

Формат описания выходных данных:
В первой строке кол-во записей в результате
Во второй строке временные метки, где нечетные записи (по порядку, а не по значению) – подключения, четные – отключения (т.е. формат аналогичен формату логов).

Ограничения:
N <= 500
Максимальное количество записей в одном логе <= 500

Примеры:

Input:
2
4
1 4 8 10
4
1 5 7 11

Output:
4
1 4 8 10

Input:
2
4
1 4 8 10
2
5 9

Output:
2
8 9

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

Python
1
2
3
4
5
6
def solution(f_in, f_out):
    pass
 
if __name__ == "__main__":
    import sys
    solution(sys.stdin, sys.stdout)

@eaa · 15.10.2021, 12:58

mamba12, что именно не получается?

@mamba12 · 15.10.2021, 15:42 **[ТС]**

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

mamba12, что именно не получается?

В целом в каком направлении двигаться, т.к. списков может быть больше 2, думал в матрицу записывать, и с пересечением есть вопросы,intersection() не совсем подходит

@eaa · 15.10.2021, 16:13

И что даже простой перебор не можете написать для начала?
Какое ограничение на числа внутри лога?

@u235 · 15.10.2021, 16:22

Для реальной задачи такого типа удобно использовать библиотеку portion, чтобы не изобретать велосипед.

@eaa · 15.10.2021, 16:36

ну вот "тупой" перебор (для понимания задачи):

Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
from itertools import groupby
n = int(input())
d = []
for _ in range(n):
    n_log = int(input())
    *log, = map(int, input().split())
    a = [0]*log[-1]
    for lo, hi in zip(log[::2], log[1::2]):
        a[lo-1:hi] = [1]*(hi-lo+1)
    d.append(a)
 
colums = [sum(col) == n for col in zip(*d)]
res = []
for k, g in groupby(enumerate(colums, 1), lambda x: x[1]):
    if k:
        *lst, = g
        res.append(lst[0][0])
        res.append(lst[-1][0])
print(len(res))
print(*res)

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

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

библиотеку portion

его же нет "из коробки", а ТС видимо будет отправлять в проверяющую систему.

@junior_student · 15.10.2021, 16:51

eaa, Я пишу анализатор Python(подсчет операторов и операндов).Сам лично с Python вообще не знаком.
Подскажи что в 6 строке значит *log, .Звездочка это указатель??просто в Python нету вроде указателей. И почему перед присваиванием стоит запятая? И если не сложно,можешь написать все переменные которые здесь есть
Еще a.append(a) будет ли здесь 'а' считаться как операнд??
И почему в цикле for вместо переменной стоит '_'

Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
from itertools import groupby
n = int(input())
d = []
for _ in range(n):
    n_log = int(input())
    *log, = map(int, input().split())
    a = [0]*log[-1]
    for lo, hi in zip(log[::2], log[1::2]):
        a[lo-1:hi] = [1]*(hi-lo+1)
    d.append(a)
 
colums = [sum(col) == n for col in zip(*d)]
res = []
for k, g in groupby(enumerate(colums, 1), lambda x: x[1]):
    if k:
        *lst, = g
        res.append(lst[0][0])
        res.append(lst[-1][0])
print(len(res))
print(*res)

@eaa · 15.10.2021, 16:54

Python
1
*log, = map(int, input().split())

это тоже самое что:

Python
1
log = list(map(int, input().split()))

просто я специально так пишу.

@junior_student · 15.10.2021, 17:02

eaa, понятно,значит log это переменная
А в циклах for почему вместо переменной стоит '_' и например в 8 строке

Python
1
for lo, hi in zip(log[::2], log[1::2]):

Зачем здесь уже запятая lo,
Это тоже как LIst только сокращение?

@u235 · 15.10.2021, 17:03

Не по теме:

eaa, тут все зависит от цели ТС:
Решить практическую задачу, научиться решать такого типа задачи или просто получить код который можно просто выдать за свой (плагиат).

@eaa · 15.10.2021, 17:07

junior_student, это элементарные вещи в python. почитайте книжечку.

Добавлено через 50 секунд

Не по теме:

u235, полное решение вряд ли он тут получит)

@mamba12 · 15.10.2021, 17:16 **[ТС]**

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

Какое ограничение на числа внутри лога?

как и на количество каналов, не больше 500

@eaa · 15.10.2021, 22:05

O(n^3) ещё могу написать сюда программу, меньше уж извини не выложу.

Новые блоги и статьи Все статьи Все блоги /
Переходник 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 и. . .

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

@eaa Status 418 4584 / 2350 / 601 Регистрация: 26.11.2017 Сообщений: 5,262 Записей в блоге: 3
	15.10.2021, 16:13
	И что даже простой перебор не можете написать для начала? Какое ограничение на числа внутри лога? 0

@u235 5516 / 2869 / 571 Регистрация: 07.11.2019 Сообщений: 4,760
	15.10.2021, 16:22
	Для реальной задачи такого типа удобно использовать библиотеку portion, чтобы не изобретать велосипед. 0

@u235
	15.10.2021, 17:03
	Не по теме: eaa, тут все зависит от цели ТС: Решить практическую задачу, научиться решать такого типа задачи или просто получить код который можно просто выдать за свой (плагиат). 0

@eaa Status 418 4584 / 2350 / 601 Регистрация: 26.11.2017 Сообщений: 5,262 Записей в блоге: 3
	15.10.2021, 17:07
	junior_student, это элементарные вещи в python. почитайте книжечку. Добавлено через 50 секунд Не по теме: u235, полное решение вряд ли он тут получит) 0

@eaa Status 418 4584 / 2350 / 601 Регистрация: 26.11.2017 Сообщений: 5,262 Записей в блоге: 3
	15.10.2021, 22:05
	O(n^3) ещё могу написать сюда программу, меньше уж извини не выложу. 0