2019牛客暑期多校训练营(第六场)-周五确认问题

时间限制：C/C++ 5秒，其他语言10秒

空间限制：C/C++ 262144K，其他语言524288K

64位IO格式：%lld

题目描述

汤汤非常喜爱周五，并记录了一系列他认为是周五的日期。每个日期格式为“yyyy/mm/dd”，其中“yyyy”代表年份，“mm”代表月份，“dd”代表日。汤汤考虑的年份范围在1600至9999之间，因此所有年份都是四位数，而月份和日可能需要前导零来保持两位数格式，例如，“2019年8月3日”应表示为“2019/08/03”。为了安全存储，汤汤使用了一种简单的替换密码，将每个数字替换成字母‘A’到‘J’中的一个，相同的数字对应相同的字母，不同的数字对应不同的字母。

不幸的是，汤汤忘记了具体的替换规则。请帮助他恢复原始的日期列表。

输入描述

包含多个测试用例。第一行包含一个整数T（1≤T≤10），表示测试用例的数量。每个测试用例的第一行包含一个整数n（1≤n≤1000001），表示日期的数量。接下来的n行每行包含一个加密后的日期字符串，格式为“yyyy/mm/dd”，其中每个数字被替换成了大写字母‘A’到‘J’。

输出描述

对于每个测试用例，输出一行“Case #x: y”，其中x是从1开始的测试用例编号，y是该测试用例的答案。如果无法恢复日期列表，则y为“Impossible”。否则，y是一个由十个不同数字组成的字符串，表示解密列表的密钥。具体来说，y中的第i个数字对应第i个大写字母。如果有多种可能的解，则输出字典序最小的一种。

示例输入

2
1
CABJ/AI/AC
5
CABJ/AI/AC
CABJ/AI/AD
CABJ/AI/AE
CABJ/AI/AF
CABJ/AI/AG

示例输出

Case #1: 0123456789
Case #2: Impossible

题目解析：给定一组由字母A-J组成的字符串，这些字母分别对应数字0-9（具体对应关系未知）。任务是找到一个字典序最小的映射关系，使所有给定的字符串都表示周五。

解决方案：通过模拟和蔡勒公式来实现。蔡勒公式是一种计算给定日期是星期几的方法。本题中，通过遍历所有可能的数字与字母的映射关系，检查每个加密日期是否能正确映射回周五。如果存在多个有效的映射关系，则选择字典序最小的一个。