Guest User

491F

a guest
Jun 23rd, 2018
662
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. long long n;
  6. long long p10[10];
  7. map<long long, string> m;
  8. set<long long> s[10];
  9.  
  10. template<class T> string toString(T x) {
  11.     ostringstream sout;
  12.     sout << x;
  13.     return sout.str();
  14. }
  15.  
  16. int getlen(long long x) {
  17.     int ans = 0;
  18.     while (x) {
  19.         x /= 10;
  20.         ans++;
  21.     }
  22.     return max(ans, 1);
  23. }
  24.  
  25. string get(long long x) {
  26.     if (m.count(x))
  27.         return m[x];
  28.     return toString(x);
  29. }
  30.  
  31. void relax(long long x, string str) {
  32.     // obviously not optimal
  33.     if (x > n || str.length() >= getlen(x))
  34.         return;
  35.  
  36.     // already have better
  37.     if (m.count(x) && m[x].length() <= str.length())
  38.         return;
  39.  
  40.     s[m[x].length()].erase(x);
  41.     m[x] = str;
  42.     s[str.length()].insert(x);
  43. }
  44.  
  45. void generatePowers() {
  46.     for (long long x = 2; x * x <= n; x++) {
  47.         long long c = x * x;
  48.         int p = 2;
  49.         while (c <= n) {
  50.             string tmp = toString(x) + "^" + toString(p);
  51.             relax(c, tmp);
  52.             c *= x;
  53.             p++;
  54.         }
  55.     }
  56. }
  57.  
  58. void generatePowerAndPower(int maxlen) {
  59.     for (int i = 1; i <= maxlen; i++)
  60.         for (int j = i; i + j + 1 <= maxlen; j++)
  61.             for (auto x : s[i])
  62.                 for (auto y : s[j])
  63.                     relax(x * y, get(x) + "*" + get(y));
  64. }
  65.  
  66. void generateSimpleAndPower(int maxlen) {
  67.     for (int i = 1; i + 2 <= maxlen; i++)
  68.         for (long long x = 1; x < p10[maxlen - 1 - i]; x++)
  69.             for (long long y : s[i])
  70.                 relax(x * y, toString(x) + "*" + get(y));
  71. }
  72.  
  73. void precalc() {
  74.     generatePowers();
  75.     generatePowerAndPower(7);
  76.     generateSimpleAndPower(7);
  77. }
  78.  
  79. string ans;
  80. void relaxAns(string s) {
  81.     if (ans.length() > s.length())
  82.         ans = s;
  83. }
  84.  
  85. void check2() {
  86.     for (int i = 1; i * 2 + 1 < ans.length(); i++) {
  87.         for (long long x = 1; x <= p10[i]; x++) {
  88.             relaxAns(get(n - x) + "+" + get(x));
  89.             if (n % x == 0)
  90.                 relaxAns(get(n / x) + "*" + get(x));
  91.         }
  92.         for (auto x : s[i]) {
  93.             relaxAns(get(n - x) + "+" + get(x));
  94.             if (n % x == 0)
  95.                 relaxAns(get(n / x) + "*" + get(x));
  96.         }
  97.     }
  98. }
  99.  
  100. int main() {
  101.     p10[0] = 1;
  102.     for (int i = 1; i < 10; i++)
  103.         p10[i] = 10 * p10[i - 1];
  104.  
  105.     cin >> n;
  106.  
  107.     precalc();
  108.     ans = get(n);
  109.     check2();
  110.     cout << ans;
  111. }
RAW Paste Data