题目描述

题目译自 USACO 2024 US Open Contest, Platinum Problem 1. Identity Theft

FJ 的 $N\ (1\le N\le 10^5)$ 头奶牛都有一个二进制串（由字符 0 和 1 组成的字符串）形式的农场 ID 号。最年长的奶牛 Bessie 已经记住了所有奶牛的农场 ID 号，她喜欢到处询问奶牛们的 ID 号。

当一头奶牛被问及它们的农场 ID 号时，它们会开始说出正确的二进制串，但可能会在说完之前感到困惑而停止。Bessie 听到二进制串后，如果不是农场中任何一头奶牛的农场 ID 号，她就会耸耸肩走开。但是，如果她听到的 ID 号是与这头奶牛不同的另一头奶牛的 ID 号，那么她就会认为发生了身份窃取，并将农场封锁。请注意，即使奶牛说出了完整的农场 ID 号，也可能发生这种情况。

FJ 希望防止这种情况发生，并希望通过增加一些位来改变奶牛的农场 ID 号。在一秒钟内，他可以在任何一头奶牛的农场 ID 编号末尾添加一位。请求出他为了防止封锁发生所需的最短时间。

输入格式

第一行包含一个整数 $N$，表示奶牛头数。

接下来 $N$ 行，第 $k$ 行包含一个二进制串，表示第 $k$ 头奶牛的农场 ID 号。

没有奶牛的农场 ID 号是空的，并且所有农场 ID 号的长度总和不超过 $10^6$。

输出格式

输出 FJ 为了防止封锁发生所需的最短时间。

3
1
1
1

5

这组样例满足第一个子任务的限制。

我们可以在 $5$ 秒内采取以下行动防止封锁发生：在第一个农场 ID 后添加 0，在第二个农场 ID 后添加 10，在第三个农场 ID 后添加 11，使农场 ID 变为 10，110 和 111。

可以证明无法用 $4$ 秒或以下来达到目的。例如，如果不变，那么农场中所有三头奶牛的 ID 均为 1，Bessie 总会认为听到的 ID 号是与被问到的奶牛不同的另一头奶牛的 ID 号。

再比如，如果只花 $2$ 秒钟在第二个农场 ID 号后面加上 0，在第三个农场 ID 编号后面加上 1，那么农场 ID 号就是 1，10 和 11，因此第二头和第三头奶牛在说出它们的农场 ID 编号时，可能会停在中间，只说 1，也就是第一头奶牛的农场 ID 编号。

3
1
11
111

2

我们可以在前两个农场 ID 号后面加上 0，使农场 ID 号和之前一样分别为 10，110 和 111，这样就可以在 $2$ 秒内完成锁定。可以证明这不可能在 $1$ 秒钟内完成。

3
1
1
11

4

我们可以在第一个农场 ID 号上添加 00，在第二个农场 ID 号上添加 01，这样就可以在 $4$ 秒钟内完成。可以证明这无法在 $3$ 秒或更短时间内完成。

5
0
01
0011
010
01

6

14
0
1
1
0
1
0
1
1
1
1
1
0
0
1

41

这组样例满足第一个子任务的限制。

数据范围与提示

• 测试点 6-7：所有农场 ID 号的长度均为 $1$
• 测试点 8-15：$N\le 10^2$ 且农场 ID 号的总长度不超过 $10^3$
• 测试点 16-25：无附加限制

供题：Benjamin Qi