POJ 1248 - Safecracker

http://poj.org/problem?id=1248

概要

ターゲットの整数 \(T\) と，相異なる大文字のアルファベットの列 \(W\) が与えられる． \(W\) に含まれる大文字のアルファベットについて，\(A = 1, B = 2, \cdots, Z = 26\) と整数を関連付ける．

\(v - w ^ 2 + x ^ 3 - y ^ 4 + z ^ 5 = T\) となるように相異なる \((v, w, x, y, z)\) を \(W\) から選んだとき， その中で辞書順が最も遅いものを答える． ただしそのような5つ組が存在しないときは「no solution」と答える．

制約

解法

5つ組の組み合わせは \(\begin{eqnarray}{}_{12}\mathrm{P}_5\end{eqnarray} = 95040\) 通りしかないので全探索．

 1 #include <iostream>
 2 #include <algorithm>
 3 using namespace std;
 4 
 5 int f(const string& s)
 6 {
 7   int n = 0;
 8   for (int i = 0; i < 5; i++) {
 9     int x = -1;
10     for (int j = 0; j <= i; j++) {
11       x *= -(s[i]-'A'+1);
12     }
13     n += x;
14   }
15   return n;
16 }
17 
18 int main()
19 {
20   int N;
21   string s;
22   while (cin >> N >> s && N != 0) {
23     sort(s.rbegin(), s.rend());
24     do {
25       if (f(s) == N) {
26         cout << s.substr(0, 5) << endl;
27         goto NEXT;
28       }
29       reverse(s.begin()+5, s.end());
30     } while (prev_permutation(s.begin(), s.end()));
31     cout << "no solution" << endl;
32 NEXT:
33     ;
34   }
35   return 0;
36 }
poj/1248.cc