POJ 1950 - Dessert

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

概要

1 2 3 ... N という数列の間に +, -, . のいずれかの記号を入れて数式を作る． . は空白を意味する．例えば 10 . 11 という式は 1011 として扱われる点に注意．

数式を計算した結果が 0 になるようなものを辞書順で小さいほうから20個出力し，また全部で何通り存在するかも答える． 20通り未満の数式しか存在しないときはすべて出力する．

数式の順序は + が最も小さく，次に -，最後に . とする．

制約

• 3 <= N <= 15

解法

数式は 3^14 のおよそ500万通りしかないので全探索．

 1 #include <iostream>
 2 using namespace std;
 3 
 4 int N, cnt;
 5 char ops[20];
 6 
 7 void dfs(int n, long long acc = 0, long long x = 1, char op = '+')
 8 {
 9   if (n == N-1) {
10     if (op == '+') {
11       acc += x;
12     } else {
13       acc -= x;
14     }
15     if (acc == 0) {
16       ++cnt;
17       if (cnt <= 20) {
18         cout << "1";
19         for (int i = 0; i < N-1; i++) {
20           cout << " " << ops[i] << " " << i+2;
21         }
22         cout << endl;
23       }
24     }
25   } else {
26     long long a = acc + (op == '+' ? x : -x);
27     long long y = (n+2 >= 10 ? 100LL : 10LL)*x + n+2;
28     ops[n] = '+'; dfs(n+1, a, n+2, '+');
29     ops[n] = '-'; dfs(n+1, a, n+2, '-');
30     ops[n] = '.'; dfs(n+1, acc, y, op);
31   }
32 }
33 
34 int main()
35 {
36   cin >> N;
37   dfs(0);
38   cout << cnt << endl;
39   return 0;
40 }