Provider.dat n1.dat n2.dat solvt1.sol solv2.sol

2 1 3 0 1 3 4

N1.dat 4 5 5 6 7 8

N2.dat 6 7 11 now 9 10

11 8

Представим приведенные примеры входа и выхода графически. Ясно, что подключения и отключения изменяют состояния каналов, т. являются точками событий в каналах. Между точками событий в каналах ничего не изменяется, поэтому для анализа состояний каналов важны только эти точки.

Чтобы определить, в какие моменты времени заняты или свободны все каналы, достаточно отследить, как изменяется количество занятых каналов в точках событий, т.е. это количество характеризует состояние системы.

Для решения задачи используем метод выметания. Он включает в себя следующие этапы.

1. Выделить точки событий.

2. Отсортировать точки событий.

3. Обработать точки событий, передвигаясь последовательно от точки события к следующей согласно проведенной сортировке

В нашей задаче статусом естественно считать количество занятых каналов. Такой статус помогает ответить на основной вопрос задачи: все каналы заняты, если статус равен N, и все свободны, если он равен 0. Кроме того, этот статус нетрудно поддерживать, двигаясь по точкам событий.

По условию в момент одновременного подключения и отключения нескольких каналов все они считаются занятыми. Поэтому будем считать, что подключения происходят «в начале секунды», а одновременные с ними отключения «в конце секунды».

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

Решение.

Чтобы начать прохождение по точкам событий, нужно выбрать первую точку. Она соответствует первому моменту, записанному в каком-то из файлов. Поэтому прочитаем первые числа всех файлов и найдем минимальное, оно и задает первую точку события.

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

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

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