Safecracker

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstdlib>
 4 #include <cstring>
 5 
 6 using namespace std;
 7 
 8 int flag, visited[12];
 9 
10 int cmp(const void *a, const void *b){
11     return *(char *)b - *(char *)a;
12 }
13 
14 int calculate(char *ans) {
15     int res = 0, x = 1, sign = 1;
16     for(int i=0; i<5; i++) {
17         for(int j=0; j<=i; j++) {
18             x *= (ans[i] - ‘A‘ + 1);
19         }
20         res += x * sign;
21         x = 1;
22         sign *= (-1);
23     }
24     return res;
25 }
26 
27 void dfs(char *str, int target, char *ans, int depth, int len) {
28     if(depth == 5) {
29         if(calculate(ans) == target)
30             flag = 1;
31         return;
32     }
33     for(int i=0; i<len; i++) {
34         if(!visited[i]) {
35             ans[depth] = str[i];
36             visited[i] = 1;
37             dfs(str, target, ans, depth+1, len);
38             if(flag)
39                 return;
40             visited[i] = 0;
41         }
42     }
43 }
44 
45 int main()
46 {
47     int target;
48     char ans[6], str[13];
49     while(scanf("%d %s", &target, str)!=EOF && !(target==0 && strcmp(str, "END")==0)) {
50         memset(visited, 0, sizeof(visited));
51         qsort(str, strlen(str), sizeof(char), cmp);
52         flag = 0;
53         dfs(str, target, ans, 0, strlen(str));
54         if(flag){
55             ans[5] = ‘\0‘;
56             puts(ans);
57         } else {
58             puts("no solution");
59         }
60     }
61     return 0;
62 }