#P1345. Address Recovery
Address Recovery
本题没有可用的提交语言。
题目描述
一家邮购公司陷入了大麻烦。该公司维护着一个包含客户地址记录的文件。由于处理不当,文件损坏了,且没有文件备份。公司需要一个程序来恢复这些地址,要求你为该公司开发这样一个程序。公司提供了以下信息:
- 通常,文件中的一条记录包含五个字段:编号(Id - no)、姓名(Name)、位置(Location)、邮局(Post - office) 和区域(Area)。不过,“区域”字段在地址中可能存在,也可能不存在。因此,一条记录中的字段总数要么是 个,要么是 个。最初,这些字段按照上述提及的顺序排列,即所谓的正常顺序。但由于处理不当,字段的顺序(而非内容)可能发生了改变。
- 每条记录以记录起始行开始,该行包含字符
@
,后面跟着一个表示记录编号的整数。文件以文件结束行结尾,该行包含字符$
,后面跟着一个表示文件中记录总数的整数。 - 一个字段可能由一行或多行组成。“编号”、“姓名”和“邮局”字段各自仅包含一行,而“位置”字段至少包含一行,“区域”字段(如果存在)可能包含一行或多行。
- 一行是由分号结尾的单词序列。空格字符可自由用于分隔一行中的单词。有时,逗号也可用于分隔“姓名”、“位置”和“区域”字段中的单词。同样,连字符可能出现在“编号”和“邮局”字段的两个单词之间。
- 一个单词可以是字母型(由字母
a - z
、A - Z
组成的字符串)、数字型(由数字0 - 9
组成的字符串)或字母数字型(由字母a - z
、A - Z
和/或数字0 - 9
组成的字符串)。 - “编号”字段可能包含任何类型的单词。除了空格字符外,“编号”字段中至少使用一个连字符来分隔单词。
- “姓名”字段中的单词是字母型的。“姓名”由两部分组成:名字部分和姓氏部分。通常,姓氏部分出现在末尾。然而,如果它出现在开头,则用逗号将其与名字部分分隔开。
- 与“编号”字段类似,“位置”字段可能包含任何类型的单词。不过,“位置”字段中从不使用连字符。
- “邮局”字段包含一个由六位数字单词表示的邮政编码。邮政编码前面有一个或多个用于标识邮局名称的字母型单词。除了空格字符外,连字符也可用于将邮政编码与邮局名称分隔开。
- “区域”字段(如果存在)仅包含字母型单词。不过,“区域”字段中的每个单词都以大写字母开头,并且可能以逗号结尾。
由于上述信息不够精确,损坏文件中的一行可能看起来属于多个字段。因此,并非总是能够唯一地恢复一条记录,甚至可能根本无法恢复。如果有多个恢复选项可用,应识别并报告所有可能的恢复记录选项。在每条恢复的记录中,字段的内容应与输入中出现的内容完全一致,只需改变字段的顺序。
输入
程序的输入是上述描述的损坏地址文件,示例输入中对此进行了说明。一条记录的长度绝不会超过 个字符,并且测试用例不超过 个。
输出
程序的输出是恢复后的地址文件,包含恢复损坏输入文件的所有可能选项。输出文件的结构基于输入文件的结构。一条记录的开头由记录起始行标识,该行除了包含字符 @
和记录编号外,还包含一个数字 ,表示恢复该记录的选项数量。数字 前面有一个空格字符。如果由于记录中包含的信息与公司提供的信息之间存在任何矛盾而无法恢复一条记录,则选项数量 设为 。记录起始行后面跟着 个恢复该记录的选项。每个选项以选项起始行开始,该行包含与选项编号相关的斜杠字符 /
的数量,例如,第二个选项将以包含两个斜杠 //
的行开始。每个恢复记录的选项中的字段按正常顺序排列。字段结尾的分号后面的所有空格字符和换行符都被视为属于前一个字段,而非后一个字段。文件以文件结束行结尾,该行除了包含字符 $
和文件中的记录总数外,还包含一个数字 ,表示恢复的记录总数。数字 前面有一个空格字符。输出文件的结构在示例输出中进行了说明。如果有多个可能的恢复地址,应按字典序对它们进行排序,并且可以假设换行符 \n
在比较中小于所有其他字符,且可能的恢复地址不超过 个。
输入样例
@1
gamma 436502;
Beta Alpha;
Nu5 321902;
Epsilon, Theta;
eta 123206;
Sigma Kappa, Lambda;
Zeta Delta;
@2
Alpha, Beta;
eta 123206;
Sigma Kappa, Lambda;
Nu5 321902;
gamma 436-502;
Epsilon, Theta;
$2
输出样例
@1 0
@2 2
/
gamma 436-502;
Alpha, Beta;
Sigma Kappa, Lambda;
Nu5 321902;
eta 123206;
Epsilon, Theta;
//
gamma 436-502;
Epsilon, Theta;
Sigma Kappa, Lambda;
Nu5 321902;
eta 123206;
Alpha, Beta;
$2 1
题目来源
坎普尔 2002 年竞赛题目