Identity Theft

题目描述

注意：本题的时间限制和内存限制分别为 3s 和 512MB，分别是正常限制的 1.5 倍和 2 倍。 农夫约翰的 $N$（$1 \leq N \leq 10^5$）头奶牛，每头都有一个农场 ID 号码，形式为一个比特串（只包含字符 '0' 和 '1' 的字符串）。年长的奶牛 Bessie 记住了所有奶牛的农场 ID 号码，并喜欢到处询问奶牛们的 ID。

当一头奶牛被问到它的农场 ID 号码时，它会开始说出正确的比特串，但可能会困惑并在说完之前就停下。Bessie 听到这个比特串后，如果它不是农场里任何一头奶牛的农场 ID 号码，那么她会耸耸肩离开。然而，如果它是另一头（不是她询问的那头）奶牛的 ID 号码，那么她会认为发生了身份盗用，并让农场进入封锁状态。注意：即使奶牛说出了完整的农场 ID 号码，这种情况也可能发生。

农夫约翰希望防止这种情况发生，并愿意通过在奶牛的农场 ID 号码末尾添加一些比特来更改它们。每秒钟，他可以在任意一头奶牛的农场 ID 号码末尾添加 1 个比特。请计算为了保证封锁永远不会发生，他所需的最少时间。

输入格式

第一行包含 $N$，表示农夫约翰农场里的奶牛数量。 接下来有 $N$ 行。第 $k$ 行包含一个比特串，等于农夫约翰农场中第 $k$ 头奶牛的农场 ID 号码。

没有奶牛的农场 ID 号码为空，并且所有农场 ID 号码的总长度最多为 $10^6$。

输出格式

输出农夫约翰需要花费的最少秒数，以确保封锁永远不会发生。

3
1
1
1

5

3
1
11
111

2

3
1
1
11

4

5
0
01
0011
010
01

6

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

41

提示

该样例满足第一个子任务的限制。 我们可以用 5 秒使封锁不可能发生：给第一个农场 ID 号码末尾添加 '0'，给第二个农场 ID 号码末尾添加 '10'，给第三个农场 ID 号码末尾添加 '11'，使农场 ID 号码变为 '10'、'110' 和 '111'。 你可以证明这不可能在 4 秒或更少时间内完成。例如，如果你保持农场 ID 号码不变，那么 3 头奶牛都有相同的农场 ID 号码 '1'，因此当 Bessie 听到它时，它总会是另一头奶牛的农场 ID 号码。 再比如，如果你只花 2 秒给第二个农场 ID 号码添加 '0'、给第三个农场 ID 号码添加 '1'，那么农场 ID 号码变为 '1'、'10' 和 '11'，于是第二和第三头奶牛在说它们的农场 ID 号码时可能会在中途停下只说出 '1'，这会是第一头奶牛的农场 ID 号码。

我们可以用 2 秒使封锁不可能发生：给前两个农场 ID 号码都添加 '0'，使农场 ID 号码像之前一样变为 '10'、'110' 和 '111'。 你可以证明这不可能在 1 秒内完成。

我们可以用 4 秒使封锁不可能发生：给第一个农场 ID 号码添加 '00'，给第二个农场 ID 号码添加 '01'。你可以证明这不可能在 3 秒或更少时间内完成。

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

评分（SCORING）： 输入 6-7：所有农场 ID 号码长度都恰好为 $1$。 输入 8-15：$N\le 10^2$ 且农场 ID 号码总长度不超过 $10^3$。 输入 16-25：无额外限制。 题目鸣谢：Benjamin Qi

标签: USACO|2024|Platinum

来源

USACO|2024|Platinum