符得到结果,字典序输出
#include
#include
#include
#include
#include
#include
using namespace std; const int MAXN = 200; const int INF = 0x3f3f3f3f; typedef long long ll; string str; ll res[MAXN]; int N, M, op[MAXN]; set
f; ll tran(int st, int ed) { if (str[st] == '0' && ed-st > 0) return -1; ll x = 0; for (int i = st; i <= ed; i++) x = x*10 + str[i]-'0'; return x; } void cal() { int m = N-1; int len = str.length()+N-2; string p(len+1, '*'); p[len--] = '='; for (int i = N-1; i >= 0; i--) { ll x = res[i]; if (x == 0) p[len--] = '0'; while (x) { p[len--] = x%10+'0'; x /= 10; } if (i) { if (op[m-1] == 0) { p[len--] = '+'; m--; } else if (op[m-1] == 1) { p[len--] = '-'; m--; } else { p[len--] = '*'; m--; } } } f.insert(p); } void findExpression(int cur, stack
s) { if (cur == N-1) { ll ans = 0; while (!s.empty()) { ans += s.top(); s.pop(); } if (N > 1 && ans == 2000) cal(); return; } for (int i = 0; i < 3; i++) { op[cur] = i; if (i == 0) { s.push(res[cur+1]); findExpression(cur+1, s); s.pop(); } else if (i == 1) { s.push(-res[cur+1]); findExpression(cur+1, s); s.pop(); } else { ll x = res[cur+1]*s.top(); s.pop(); s.push(x); findExpression(cur+1, s); } } } void solve(int cur, int n) { if (cur == str.length()-1) { N = n; stack
s; s.push(res[0]); findExpression(0, s); return; } for (int i = cur; i < str.length()-1; i++) { ll x = tran(cur, i); if (x != -1) { res[n] = x; solve(i+1, n+1); } } } int main() { int cas = 1; while (cin>>str) { f.clear(); if (str.length() == 1 && str[0] == '=') break; printf("Problem %d\n", cas++); solve(0, 0); if (f.size() == 0) printf(" IMPOSSIBLE\n"); else { for (set
::iterator it = f.begin(); it != f.end(); it++) cout << " " << *it << endl; } } return 0; }