Contest.uni-smr.ac.ru :: соревнования по программированию
Русская версия || English version
Login:
Password:
Забыли пароль?
 пример поиска: Вася Пупкин
 






Задача E. IP-диапазоны

Задачу добавил: alef

Успешно сдано решений: 7

Оговоримся сразу — в компьютерных классах сейчас полный порядок, соседние машины получают соседние IP-адреса. Но когда-то, когда проводились первые чемпионаты, а компьютерные классы находились в стадии формирования, такая задача была весьма актуальной...

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

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

Ваша задача — определить минимальное количество диапазонов, с помощью которого можно закрыть доступ в интернет всем компьютерам участников, сохранив при этом доступ для всех тех, кто учится. Считайте, что любого из учащихся можно переместить за любой резервный компьютер, и что никого из участников переместить за резервный компьютер нельзя. Ради простоты мы будем представлять IP-адрес в виде целого числа от 1 до N.

 

Формат входного файла input.txt

Первая строка — целое число N — верхняя граница диапазона ip-адресов (1 <= N <= 10^9)

Вторая строка — слово Competitors

На третьей и последующих строках через пробел записаны числа из диапазона от 1 до N — IP-адреса компьютеров участников чемпионата.

Затем следует строка, содержащая слово Students.

На следующих после нее строках через пробел записаны числа из диапазона от 1 до N — IP-адреса компьютеров учащихся

Далее записана строка, содержащая единственное слово Reserved

На следующих за ней строках до конца файла через пробел записаны числа из диапазона от 1 до N — IP-адреса резервных компьютеров.

Гарантируется, что в группах Competitors, Students и Reserved суммарно содержится не более 10^5 адресов, нет повторяющихся адресов, каждая из этих групп содержит, по крайней мере, один элемент, и эти группы в попарном пересечении дают пустое множество.

 

Формат выходного файла output.txt

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

 

Пример входного файла

25

Competitors

16 3 6

22 8 10

11 13 14

15

Students

17 2 18

21 4 5

7 25 12

Reserved

1 20

 

Пример выходного файла

3


Сдать задачу

Задать вопрос жюри по этой задаче