Submission #65289916

---

Source Code Expand

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

#define xx first
#define yy second
#define PB push_back
#define MP make_pair

using namespace std;

using ll = long long;
using pii = pair<int,int>;
using tii = tuple<int,int,int>;
using vi = vector<int>;
template <typename T> using V = vector<T>;

template<class T> using uset = unordered_set<T>;
template<class T1, class T2> using umap = unordered_map<T1, T2>;

const vector<pair<int, int>> DIRS = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
constexpr int MOD = 1000000007;
mt19937_64 rnd(time(0));

bool is1(int n ){
    while ( n ) {
        if ( n%10 != 1 ) return false;
        n /= 10;
    }
    return true;
}

template <class T>
using ordered_set =  __gnu_pbds::tree<T,__gnu_pbds::null_type,less<T>,__gnu_pbds::rb_tree_tag,__gnu_pbds::tree_order_statistics_node_update>;
signed main() {
    cin.tie(nullptr)->sync_with_stdio(false);
    int n;
    cin >> n;
    string res[2005];
    bool isp[2005] = {0};
    for ( int i=1; i<=n; i++ ) {
        if ( is1(i) ) {
            res[i] = to_string(i);
            continue;
        }
        for ( int j=1; j<=i/2; j++ ) {
            string tmp = res[j]+"+"+res[i-j];
            if ( res[i].size() == 0 || tmp.size() < res[i].size() ) {
                res[i] = tmp;
                isp[i] = true;
            }
        }
        for ( int j=1; j*j<=i; j++ ) {
            if ( i%j ) continue;
            string tmp;
            if ( isp[j] ) tmp += "(";
            tmp += res[j];
            if ( isp[j] ) tmp += ")";
            tmp += "*";
            if ( isp[i/j] ) tmp += "(";
            tmp += res[i/j];
            if ( isp[i/j] ) tmp += ")";
            if ( res[i].size() == 0 || tmp.size() < res[i].size() ) {
                res[i] = tmp;
                isp[i] = false;
            }
        }
    }
    cout << res[n] << '\n';
    return 0;
}

Submission Info

Judge Result