pe093.cpp

#include <bits/stdc++.h>

using namespace std;
#define all(x) x.begin(), x.end()
using ll = long long;

struct Rational {
  
  ll N, D; 
  ll GCD(ll x, ll y) { 
    return y==0?x:GCD(y, x%y);
  }
  Rational(ll n, ll d) : N(n), D(d) {
    if(D < 0) {
      N *= -1;
      D *= -1;
    }
    ll gcd = GCD(abs(N), abs(D));
    N /= gcd;
    D /= gcd;
  }

  Rational operator+(Rational x) {
    ll a = N, b = D, c = x.N, d = x.D;
    ll nn = a*d+b*c, nd = b*d;
    return Rational(nn, nd);
  }

  Rational operator-(Rational x) {
    ll a = N, b = D, c = x.N, d = x.D;
    ll nn = a*d-b*c, nd = b*d;
    return Rational(nn, nd);
  }  

  Rational operator*(Rational x) {
    ll a = N, b = D, c = x.N, d = x.D;
    ll nn = a*c, nd = b*d;
    return Rational(nn, nd);
  }

  Rational operator/(Rational x) {
    ll a = N, b = D, c = x.N, d = x.D;
    ll nn = a*d, nd = b*c;
    return Rational(nn, nd);
  }

  bool operator<(const Rational& x) const {
    ll a = N, b = D, c = x.N, d = x.D;
    return a*d < b*c;
  }
};
int main()
{
  cin.tie(0);
  ios::sync_with_stdio(false);
  cout << fixed << setprecision(12);

  string ans = "";
  int mxlen = 0;
  int len = 4;
  for(int i=1; i<10; i++) {
    for(int j=i+1; j<10; j++) {
      for(int k=j+1; k<10; k++) {
        for(int l=k+1; l<10; l++) {
          vector<int> v{i, j, k, l};
          sort(all(v));
          set<int> all;
          do {
            set<Rational> st[len+1][len+1];
            for(int i=0; i<len; i++) st[i][i+1].insert(Rational(v[i], 1));

            for(int d=2; d<=len; d++) {
              for(int L=0; L<len; L++) {
                if(L+d > len) break;
                int R = L + d;

                for(int m=L+1; m<R; m++) {
                  //[l, k), [k, r);
                  for(auto e1: st[L][m]) {
                    for(auto e2: st[m][R]) {
                      if(e2.D == 0) continue;
                      st[L][R].insert(e1+e2);
                      st[L][R].insert(e1-e2);
                      st[L][R].insert(e1*e2);
                      st[L][R].insert(e1/e2);
                    }
                  }
                }
              }
            }
            for(auto e: st[0][len]) {
              if(e.D == 1 && e.N > 0) all.insert(e.N);
            }
          }while(next_permutation(all(v)));

          auto itr = all.begin();
          int num = *itr;
          
          if(num == 1){ 
            itr++;
            for(; itr != all.end(); itr++) {
              if(num + 1 != *itr) {
                break;
              }
              num = *itr;
            }
            if(mxlen < num){
              mxlen = num;
              ans = to_string(i*1000+j*100+k*10+l);
            }
          }
        }
      }
    }
  }
  
  cout << ans << endl;
  return 0;
}