2087: Safecracker

内存限制:128 MB 时间限制:2 S 标准输入输出
题目类型:传统 评测方式:文本比较 上传者:
提交:13 通过:8

题目描述

物品被锁在Klein的保险箱里,藏在二楼图书馆的一幅画后面。Klein保险箱极其罕见;他们中的大多数,连同Klein和他的工厂,在第二次世界大战中被摧毁了。幸运的是,研究部门的Brumbaugh知道了Klein的秘密,并在死前把它们写了下来。Klein的保险柜有两个显著特征:用字母代替数字的密码锁和门上刻着的引文。Klein的引文通常包含5到12个不同的大写字母,通常在句子的开头,并提到一个或多个数字。五个大写字母构成了打开保险箱的密码。通过以适当的方式组合所有数字中的数字,就可以得到一个数字目标。(构建目标编号的细节是保密的。)为了找到这个组合,你必须选择5个字母v, w, x, y,和z,满足下面的方程,其中每个字母替换为它在字母表中的顺序位置(A=1, B=2,…, Z = 26)。组合是vwxyz。如果存在多个解,那么该组合就是字典序上最大的解,即字典中最后出现的解。


=== Op tech briefing, 2002/11/02 06:42 CST ===

"The item is locked in a Klein safe behind a painting in the second-floor library. Klein safes are extremely rare; most of them, along with Klein and his factory, were destroyed in World War II. Fortunately old Brumbaugh 

from research knew Klein's secrets and wrote them down before he died. A Klein safe has two distinguishing features: a combination lock that uses letters 

instead of numbers, and an engraved quotation on the door. A Klein quotation always contains between five and twelve distinct uppercase letters, usually 

at the beginning of sentences, and mentions one or more numbers. Five of the uppercase letters form the combination that opens the safe. By combining 

the digits from all the numbers in the appropriate way you get a numeric target. (The details of constructing the target number are classified.) To find the 

combination you must select five letters v, w, x, y, and z that satisfy the following equation, where each letter is replaced by its ordinal position in the 

alphabet (A=1, B=2, ..., Z=26). The combination is then vwxyz. If there is more than one solution then the combination is the one that is lexicographically 

greatest, i.e., the one that would appear last in a dictionary."

v - w^2 + x^3 - y^4 + z^5 = target

"For example, given target 1 and letter set ABCDEFGHIJKL, one possible solution is FIECB, since 6 - 9^2 + 5^3 - 3^4 + 2^5 = 1. There are actually several

 solutions in this case, and the combination turns out to be LKEBA. Klein thought it was safe to encode the combination within the engraving, because it 

could take months of effort to try all the possibilities even if you knew the secret. But of course computers didn't exist then."

=== Op tech directive, computer division, 2002/11/02 12:30 CST ===

"Develop a program to find Klein combinations in preparation for field deployment. Use standard test methodology as per departmental regulations. 

Input consists of one or more lines containing a positive integer target less than twelve million, a space, then at least five and at most twelve distinct 

uppercase letters. The last line will contain a target of zero and the letters END; this signals the end of the input. For each line output the Klein combination, 

break ties with lexicographic order, or 'no solution' if there is no correct combination. Use the exact format shown below."

输入格式

输入包含一个或多个行,其中包含一个小于1200万的正整数目标,一个空格,然后至少5个,最多12个不同的大写字母。最后一行将包含一个0的目标和字母END;这表示输入结束。

输出格式

对于每一行输出唯一的Klein组合,如果没有正确的组合,则输出“no solution”。请使用下面的格式。

输入样例 复制

1 ABCDEFGHIJKL
11700519 ZAYEXIWOVU
3072997 SOUGHT
1234567 THEQUICKFROG
0 END

输出样例 复制

LKEBA
YOXUZ
GHOST
no solution

分类标签