250:Safecracker ②

描述
“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 - w2+ x3- y4+ z5= target

“For example, given target 1 and letter set ABCDEFGHIJKL, one possible solution is FIECB, since 6 - 92+ 53- 34+ 25= 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.”

"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 unique Klein combination, or ‘no solution’ if there is no correct combination. Use the exact format shown below."
样例输入
1 ABCDEFGHIJKL
11700519 ZAYEXIWOVU
3072997 SOUGHT
1234567 THEQUICKFROG
0 END
样例输出
LKEBA
YOXUZ
GHOST
no solution

题意

大致是字符串abc…分别代表123,
输入target和字符串然后在字符串中找到符合公式 [ v - w2+ x3- y4+ z5= target ] 的最大字典序字符串
完整翻译在最后

解析

不难,先用一个sort排好字典序,然后枚举可能性

代码

#include <algorithm>
#include <cstring>
#include <iostream>
using namespace std;

bool cmp(char a, char b) { return a > b; }

int main() {
    int target;
    char all[16];
    while (scanf("%d%s", &target, all)) {
        if (target == 0 && strcmp("END", all) == 0)
            break;
        int len = strlen(all);

        sort(all, (all + len), cmp);
        bool flag = true;
        for (int a = 0; a < len; a++) {
            for (int b = 0; (b < len) && flag; b++) if (b != a)
                    for (int c = 0; (c < len) && flag; c++) if (c != b && c != a)
                            for (int d = 0; (d < len) && flag; d++) if (d != a && d != b && d != c)
                                    for (int e = 0; e < len && flag; e++) {
                                        if (e == a || e == b || e == c || e == d)
                                            continue;
                                        int v = all[a] - 'A' + 1;
                                        int w = all[b] - 'A' + 1;
                                        int x = all[c] - 'A' + 1;
                                        int y = all[d] - 'A' + 1;
                                        int z = all[e] - 'A' + 1;

                                        if (v-w*w+x*x*x-y*y*y*y+z*z*z*z*z==target) {
                                            flag = false;
                                            printf("%c%c%c%c%c\n", all[a],
                                                   all[b], all[c], all[d],
                                                   all[e]);
                                            break;
                                        }
                                    }
        }
        if (flag)
            printf("no solution\n");
    }
}

机器翻译

描述
“项目是克莱恩锁在一个安全的背后在图书馆二楼的一幅画。克莱恩保险箱极其罕见;他们中的大多数,连同克莱因和他的工厂,在第二次世界大战中被摧毁。幸运的是,研究部门的老布伦博知道了克莱因的秘密,并在他死前写下了这些秘密。克莱因保险箱有两个明显的特点:用字母代替数字的密码锁和刻在门上的报价。克莱因的引文总是包含5到12个不同的大写字母,通常出现在句子的开头,并提到一个或多个数字。五个大写字母组成了打开保险箱的密码组合。通过以适当的方式组合所有数字中的数字,就可以得到一个数字目标。(建造目标号的细节是保密的。)要找到这个组合,你必须选择五个字母v, w, x, y,和z,满足下面的等式,每个字母都被它在字母表中的序数所取代(A=1, B=2,…), Z = 26)。然后这个组合就是vwxyz。如果有多个解,那么组合就是字典上最大的解,也就是在字典中最后出现的解。
v - w2+ x3- y4+ z5= target
例如,给定目标1和字母集ABCDEFGHIJKL,一个可能的解决方案是FIECB,因为6 - 92+ 53- 34+ 25= 1。在这种情况下实际上有几个解决方案,组合起来就是LKEBA。克莱因认为,把密码编码到版画里是安全的,因为即使你知道这个秘密,你也要花上好几个月的时间去尝试所有的可能性。当然,那时还没有电脑。”
“开发一个程序来找到克莱恩组合,为野外部署做准备。按照部门规定使用标准测试方法。
输入
输入由一行或多行组成,其中包含一个小于1200万的正整数目标,一个空格,然后至少5个,最多12个不同的大写字母。最后一行将包含一个目标0和字母结束;这表示输入的结束。
输出
对于每一行输出唯一的Klein组合,如果没有正确的组合,则输出“no solution”。使用如下所示的格式。”

上一篇:505C - Mr. Kitayuta, the Treasure Hunter(思维+dp偏移量优化)


下一篇:MFC—RichEdit控件有关使用