陈远龙精品编程（信奥赛） 助力信奥赛学子取得优秀的成绩

题目描述

Alex是一个IP网络管理员。他的客户拥有许多个独立的IP地址，他决定将这些IP地址归并到尽可能小的IP网络中。

每个IP地址是一个4字节的数字，按字节以点分十进制表示法写成：“byte0.byte1.byte2.byte3”（引号用于说明）。每个字节表示为0到255（包括0和255）的十进制数，且没有多余的前导零。

IP网络由两个4字节的数字描述——网络地址（network address）和网络掩码（network mask）。网络地址和网络掩码的表示方法与IP地址相同。

为了理解网络地址和网络掩码的意义，需要考虑它们的二进制表示。IP地址、网络地址和网络掩码的二进制表示由32位组成：

• byte0 的8位（二进制从高到低排列）
• 接着是 byte1 的8位
• 再接着是 byte2 的8位
• 最后是 byte3 的8位。

一个IP网络包含了 $2^n$ 个IP地址，其中 $0 \leq n \leq 32$。

• 网络掩码 在二进制表示中总是从高位开始的 $32 - n$ 位设置为1，低位的 $n$ 位设置为0。
• 网络地址 的二进制表示中前 $32 - n$ 位是任意值，后 $n$位设置为0。

一个IP网络包含所有与网络地址的前 $32 - n$ 位相同、后 $n$位任意的IP地址。如果一个IP网络包含的IP地址数量少于另一个网络，则我们认为前者的网络“更小”。

例如：
网络地址为 194.85.160.176，网络掩码为 255.255.255.248 的IP网络包含从 194.85.160.176 到 194.85.160.183 共8个IP地址（包含端点）。

输入格式

输入文件包含多个测试用例，每个测试用例的格式如下：

• 第一行是一个整数 $m$ ($1 \leq m \leq 1000$)，表示有 $m$ 个IP地址。
• 接下来的 $m$ 行中，每行一个IP地址。每个IP地址可能在输入文件中出现多次。

输出格式

对于每个测试用例，输出两行描述包含所有输入IP地址的最小可能的IP网络：

• 第一行是网络地址
• 第二行是网络掩码

样例 #1

样例输入 #1

3  
194.85.160.177  
194.85.160.183  
194.85.160.178  

样例输出 #1

194.85.160.176  
255.255.255.248

样例 #2

样例输入 #2

1
36.185.229.221
2
51.110.164.229
51.110.165.28

样例输出 #2

36.185.229.221
255.255.255.255
51.110.164.0
255.255.254.0

补充说明

输入会有多组测试数据，最后以EOF作为输入结束的标志

IP网络地址为 194.85.160.176，网络掩码为 255.255.255.248 的IP网络包含从 194.85.160.176 到 194.85.160.183 共8个IP地址（包含端点）。

IP网络地址为 194.85.160.176的二进制表示为： 11000010 . 01010101 . 10100000 . 10110000

网络掩码为 255.255.255.248的二进制表示为：11111111 . 11111111 . 11111111 . 11111000

网络地址通过将IP地址与网络掩码按位与（AND）运算得到：11000010 . 01010101 . 10100000 . 10110000 => 194.85.160.176

在这个子网中，主机地址范围是从网络地址到广播地址之间的地址（包含网络地址和广播地址）：

• 网络地址的主机部分：末尾的000 到 111，共8个IP地址，由掩码的最后的3个0控制
• 可用主机地址范围：194.85.160.176 - 194.85.160.183

可以简单的认为网络掩码的前n位的1用于确定的是网络地址，后m位的0用于确定网络主机的地址（n + m = 32位）

如果末尾有m位0，则可以有0000..（m位） - 111..（m位）的主机地址

网络掩码的作用也可以认为是掩饰掉网络IP中的不同的信息（主机部分），将这部分置为0，保留相同的信息（网络部分），将这部分置为1

如何计算多个不同IP的网络掩码

计算多个不同IP地址的网络掩码的过程是为了找到它们的公共网络前缀，也就是确定这些IP地址属于同一个网络的最小网络掩码。以下是详细步骤：

---

步骤 1：将IP地址转换为二进制 将每个IP地址转换为32位二进制表示。例如：

• IP1: 192.168.1.1 → 11000000.10101000.00000001.00000001
• IP2: 192.168.1.5 → 11000000.10101000.00000001.00000101

---

步骤 2：比较每位，找出公共前缀 从左到右比较每一位二进制数：

• 如果相同，保留该位；对应的网络掩码设置为1
• 如果不同，从此位置开始就没有公共前缀了。从第1个不同位开始到最后，网络掩码设置为0

网络知识补充阅读（选读）

IP地址和网络掩码

IP地址和网络掩码是计算机网络中非常重要的概念，用于标识设备并划分网络。

IP地址是分配给网络设备的唯一标识，用于在网络中标识一个设备的位置。

• IPv4地址由四组十进制数字组成，每组数字的范围是0-255，用点分隔，例如：192.168.1.1。
• 每个IPv4地址由网络部分和主机部分组成：
  • 网络部分：标识设备所在的网络。
  • 主机部分：标识该网络中的具体设备。

网络掩码（Subnet Mask）用于划分网络和主机的范围，帮助确定IP地址的网络部分和主机部分。

• IPv4网络掩码通常用点分十进制表示，例如：255.255.255.0。
• 每个网络掩码的作用是：
  • 1表示网络部分。
  • 0表示主机部分。

假设IP地址为192.168.1.1，网络掩码为255.255.255.0：

• 网络部分是192.168.1（由掩码的1决定）。
• 主机部分是.1（由掩码的0决定）。

IP地址和网络掩码结合可以确定设备所在的网络。例如：

• IP地址：192.168.1.1
• 网络掩码：255.255.255.0

计算得到的网络地址是192.168.1.0，表示这个设备属于192.168.1.0/24的网络。

用斜杠表示网络掩码中连续的1的数量。例如：

• 255.255.255.0可以写作/24。
• 255.255.0.0可以写作/16。

网络掩码的作用

网络掩码的主要作用是划分网络，帮助区分IP地址中的网络部分和主机部分，从而实现高效的网络管理和通信。

网络掩码通过将IP地址的某些位固定为网络部分，可以确定一个网络的范围。例如：

• IP地址：192.168.1.1
• 网络掩码：255.255.255.0
• IP地址的前24位由掩码的1表示为网络部分，结果是：192.168.1.0/24。
• 网络范围：192.168.1.0到192.168.1.255。

设备通信前需要判断是否在同一网络：

1. 将两台设备的IP地址分别与其网络掩码按位与（AND）运算。
2. 如果结果相同，说明它们在同一网络中，可以直接通信；否则需要通过网关通信。

比如：

• 设备A：IP地址192.168.1.1，掩码255.255.255.0。
• 设备B：IP地址192.168.1.100，掩码255.255.255.0。

计算网络地址：

• 192.168.1.1 & 255.255.255.0 = 192.168.1.0
• 192.168.1.100 & 255.255.255.0 = 192.168.1.0

结果相同，说明两台设备在同一网络中。

测试点数目

共5个测试点，每个测试点20分

时间与内存限制

每个测试点时间：1000ms（1.0s），内存：256MiB

输入输出模式

本OJ支持两种输入输出模式