#include #define FOR(i,a,b) for (int i=(a);i<(b);i++) #define FORR(i,a,b) for (int i=(a);i>=(b);i--) #define pb push_back #define pcnt __builtin_popcount #define show(x) cout<<#x<<" = "< pii; typedef vector vi; typedef vector vvi; typedef vector vpii; typedef set si; typedef pair pll; typedef vector vl; typedef vector vvl; typedef vector vpll; typedef set sl; templatestring join(vector&v) {stringstream s;FOR(i,0,sz(v))s<<' '<b)swap(a,b);for(;a>0;b%=a,swap(a,b));return b;} int modpow(ll a,ll n,int m){if(a==0)return a;ll p=1;for(;n>0;n/=2,a=a*a%m)if(n&1)p=p*a%m;return(int)p;} void dout(double d){printf("%.12f\n",d);} const int iinf = 1e9; const ll linf = 1e17; const int mod = 1e9+7; const double pi = acos(-1); const double eps = 1e-10; int n, pl, mi; vl v; char c; map M[8][8]; pll search(int _pl, int _mi, int a){ // cout << "search(" << _pl << "," << _mi << "," << a << ")" << endl; if(M[_pl][_mi].find(a) != M[_pl][_mi].end()) return M[_pl][_mi][a]; ll ri = linf, ra = -linf; pll tmp; if(_pl + _mi >= pcnt(a)){ tmp = mp(ri, ra); M[_pl][_mi][a] = tmp; return tmp; } if(_pl == 0 && _mi == 0){ ri = 0, ra = 0; FOR(i, 0, n)if(a >> i & 1)ri = ri * 10 + v[i]; FORR(i, n-1, 0)if(a >> i & 1)ra = ra * 10 + v[i]; tmp = mp(ri, ra); M[_pl][_mi][a] = tmp; return tmp; } vi vv; FOR(i, 0, n)if((a >> i) & 1)vv.pb(i); int vvl = sz(vv); FOR(i, 1, (1<> j & 1)_ra = _ra * 10 + v[vv[j]]; FOR(j, 0, vvl)if(i >> j & 1)_ri = _ri * 10 + v[vv[j]]; FOR(j, 0, vvl)if(i >> j & 1)_a -= 1< 0){ tmp = search(_pl-1, _mi, _a); mins(ri, _ri+tmp.fi); maxs(ra, _ra+tmp.se); } if(_mi > 0){ tmp = search(_pl, _mi-1, _a); mins(ri, tmp.fi-_ra); maxs(ra, tmp.se-_ri); } } tmp = mp(ri, ra); M[_pl][_mi][a] = tmp; return tmp; } main(){ cin.tie(0); ios::sync_with_stdio(false); cin >> n; FOR(i, 0, n){ cin >> c; switch(c){ case '+': pl++; break; case '-': mi++; break; default: v.pb(c-'0'); } } n = sz(v); sort(rng(v)); pll ans = search(pl, mi, (1<fi << "::" << itr->se.fi << "," << itr->se.se << endl; return 0; }