{"raw_statement":[{"iden":"statement","content":"...Во время межпланетных сборов программистов в институте Космической Гавани на планете Латакония случилось непредвиденное: в предназначенной для участников сборов подсети обнаружилась нехватка свободных IP-адресов. Прибывший с Земли системный администратор Дмитрий просканировал логи роутера, обнаружил список адресов подключенных устройств и поручил Вам по маске подсети и списку встречающихся в логе подключения адресов выяснить, сколько адресов в данной подсети свободно. Заметим, что роутер обслуживает не только интересующую нас подсеть, а также что один и тот же адрес может упоминаться в логах многократно.\n\nПодсеть задаётся базовым IP-адресом и маской подсети. \n\nМаска подсети записывается через наклонную черту сразу после базового адреса. Например, \"_129.1.3.17/28_\". В данном случае маска равна 28, то есть подсеть включает в себя все IP-адреса с фиксированными 28 старшими битами 10000001 00000001 00000011 0001 (то есть адреса от \"_129.1.3.16_\" до \"_129.1.3.31_\" ). \n\nПервая строка входных данных. задаёт подсеть в формате, описанном в условии задачи. Все числа в IP-адресе и маска подсети не содержат в записи ведущих нулей.\n\nВо второй строке входных данных задано одно целое число N (1 ≤ N ≤ 100) — количество устройств, подключенных к роутеру. Каждая из последующих N строк содержит один IP-адрес, записанный в стандартном формате — упоминание подключенного к роутеру устройства в логе. Гарантируется, что все IP-адреса корректны.\n\nВыведите одно целое число — количество свободных IP-адресов в заданной подсети. В случае, если в логах роутера обнаружены адрес или широковещательный адрес заданной подсети, то в конфигурации системы есть какая-то ошибка и надо вывести  - 1.\n\n"},{"iden":"входные данные","content":"Первая строка входных данных. задаёт подсеть в формате, описанном в условии задачи. Все числа в IP-адресе и маска подсети не содержат в записи ведущих нулей.Во второй строке входных данных задано одно целое число N (1 ≤ N ≤ 100) — количество устройств, подключенных к роутеру. Каждая из последующих N строк содержит один IP-адрес, записанный в стандартном формате — упоминание подключенного к роутеру устройства в логе. Гарантируется, что все IP-адреса корректны."},{"iden":"выходные данные","content":"Выведите одно целое число — количество свободных IP-адресов в заданной подсети. В случае, если в логах роутера обнаружены адрес или широковещательный адрес заданной подсети, то в конфигурации системы есть какая-то ошибка и надо вывести  - 1."},{"iden":"примеры","content":"Входные данные129.1.3.17/282129.1.3.17129.1.3.15Выходные данные13Входные данные129.1.3.17/244129.1.3.255127.0.0.1129.1.3.18129.1.3.255Выходные данные-1"}],"translated_statement":null,"sample_group":[],"show_order":[],"formal_statement":"**Definitions**  \nLet $ \\text{subnet} = \\text{base\\_ip}/m $, where:  \n- $ \\text{base\\_ip} $ is a 32-bit IPv4 address represented as four 8-bit octets.  \n- $ m \\in \\{0, 1, \\dots, 32\\} $ is the prefix length (subnet mask).  \n\nLet $ S \\subseteq \\{0,1\\}^{32} $ be the set of all IP addresses in the subnet:  \n$$ S = \\{ x \\in \\{0,1\\}^{32} \\mid x \\text{ and } \\text{mask}(m) = \\text{base\\_ip} \\text{ and } \\text{mask}(m) \\} $$  \nwhere $ \\text{mask}(m) $ is the 32-bit mask with the first $ m $ bits set to 1 and the rest to 0.  \n\nLet $ A = \\{a_1, a_2, \\dots, a_N\\} $ be the multiset of IP addresses from the router logs, each represented as a 32-bit integer.  \n\nLet $ \\text{network\\_addr} $ be the smallest address in $ S $ (all host bits 0).  \nLet $ \\text{broadcast\\_addr} $ be the largest address in $ S $ (all host bits 1).  \n\n**Constraints**  \n1. $ 1 \\le N \\le 100 $  \n2. All IP addresses (base and logged) are valid IPv4 addresses.  \n3. $ 0 \\le m \\le 32 $  \n\n**Objective**  \nCompute the number of free IP addresses in subnet $ S $:  \n$$ \\text{free} = 2^{32 - m} - |A \\cap S| $$  \n\n**But if** $ \\text{network\\_addr} \\in A $ or $ \\text{broadcast\\_addr} \\in A $,  \nthen output $ -1 $.","simple_statement":"Given a subnet defined by a base IP and a subnet mask, and a list of connected device IPs, count how many IP addresses in the subnet are free. If any logged IP is the network address or broadcast address of the subnet, output -1.","has_page_source":false}