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

@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) ещё могу написать сюда программу, меньше уж извини не выложу.

Новые блоги и статьи Все статьи Все блоги /
Модульная разработка через nuget packages DevAlt 07.03.2026 Сложившийся в . Net-среде способ разработки чаще всего предполагает монорепозиторий в котором находятся все исходники. При создании нового решения, мы просто добавляем нужные проекты и имеем. . .	Модульный подход на примере F# DevAlt 06.03.2026 В блоге дяди Боба наткнулся на такое определение: В этой книге («Подход, основанный на вариантах использования») Ивар утверждает, что архитектура программного обеспечения — это структуры,. . .	Управление камерой с помощью скрипта OrbitControls.js на Three.js: Вращение, зум и панорамирование 8Observer8 05.03.2026 Содержание блога Финальная демка в браузере работает на Desktop и мобильных браузерах. Итоговый код: orbit-controls-threejs-js. zip. Сканируйте QR-код на мобильном. Вращайте камеру одним пальцем,. . .	SDL3 для Web (WebAssembly): Синхронизация спрайтов SDL3 и тел Box2D 8Observer8 04.03.2026 Содержание блога Финальная демка в браузере. Итоговый код: finish-sync-physics-sprites-sdl3-c. zip На первой гифке отладочные линии отключены, а на второй включены:. . .
SDL3 для Web (WebAssembly): Идентификация объектов на Box2D v3 - использование userData и событий коллизий 8Observer8 02.03.2026 Содержание блога Финальная демка в браузере. Итоговый код: finish-collision-events-sdl3-c. zip Сканируйте QR-код на мобильном и вы увидите, что появится джойстик для управления главным героем. . . .	Реалии Hrethgir 01.03.2026 Нет, я не закончил до сих пор симулятор. Эта задача сложнее. Не получилось уйти в плавсостав, но оно и к лучшему, возможно. Точнее получалось - но сварщиком в палубную команду, а это значит, в моём. . .	Ритм жизни kumehtar 27.02.2026 Иногда приходится жить в ритме, где дел становится всё больше, а вовлечения в происходящее — всё меньше. Плотный график не даёт вниманию закрепиться ни на одном событии. Утро начинается с быстрых,. . .	SDL3 для Web (WebAssembly): Сборка библиотек: SDL3, Box2D, FreeType, SDL3_ttf, SDL3_mixer и SDL3_image из исходников с помощью CMake и Emscripten 8Observer8 27.02.2026 Недавно вышла версия 3. 4. 2 библиотеки SDL3. На странице официальной релиза доступны исходники, готовые DLL (для x86, x64, arm64), а также библиотеки для разработки под Android, MinGW и Visual Studio. . . .

@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,759
	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