Задача 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