AOJ2588.cpp

#include <bits/stdc++.h>
 
#define REP(i,n) for(int i=0;i<(int)(n);i++)
#define ALL(x) (x).begin(),(x).end()
 
using namespace std;
 
typedef long long ll;
 
const ll MAX = 1LL << 36;
 
vector<ll> dp1[16], dp2[16];
 
int len(ll n) { return n == 0 ? 0 : len(n / 10) + 1; }
 
int main() {
  for (ll i = 2; i * i < MAX; ++i) {
    ll num = i * i;
    for (int j = 2; num < MAX; ++j) {
      int s = len(i) + len(j) + 1, l = len(num);
      if (s < l) dp1[s].push_back(num);
      num *= i;
    }
  }
  for (ll i = 1; i < 10000; ++i) dp1[len(i)].push_back(i);
  REP(l,9) {
    REP(i,l) {
      int j = l - i - 1;
      for (ll a: dp1[i]) for (ll b: dp1[j]) {
        if ((1LL << 37) / a > b && a * b < MAX && l < len(a * b))
          dp1[l].push_back(a * b);
        if (a + b < MAX && l < len(a + b)) dp2[l].push_back(a + b);
        if (a > b && l < len(a - b)) dp2[l].push_back(a - b);
        if (a > b && l < len(a / b)) dp1[l].push_back(a / b);
      }
      for (ll a: dp1[i]) for (ll b: dp2[j]) {
        if (a + b < MAX && l < len(a + b)) dp2[l].push_back(a + b);
        if (a > b && l < len(a - b)) dp2[l].push_back(a - b);
      }
      int k = j - 2;
      if (k < 1) continue;
      for (ll b: dp2[i]) for (ll a: dp1[k]) {
        if ((1LL << 37) / a > b && a * b < MAX && l < len(a * b))
          dp1[l].push_back(a * b);
        if (a > b && l < len(a / b)) dp1[l].push_back(a / b);
      }
    }
    sort(ALL(dp1[l]));
    auto it = unique(ALL(dp1[l]));
    dp1[l].resize(it - begin(dp1[l]));
    sort(ALL(dp2[l]));
    it = unique(ALL(dp2[l]));
    dp2[l].resize(it - begin(dp2[l]));
  }
  ll n;
  while (cin >> n, n >= 0) {
    if (n == 0) { cout << 1 << endl; continue; }
    int res = len(n);
    REP(l,11) {
      for (ll i: dp1[l]) {
        if (i == n) res = min(res, l);
        if (l > 8) continue;
        res = min(res, l + len(abs(n - i)) + 1);
        if (n % i == 0) res = min(res, l + len(n/i) + 1);
        ll div = i / n;
        if (div > 0 && i / div == n) res = min(res, l + len(div) + 1);
        if (l > 6) continue;
        for (int j = 3; j < min(7, 11-l); ++j) {
          auto it = lower_bound(ALL(dp1[j]), n-i);
          if (it != end(dp1[j]) && i + *it == n) res = min(res, l+j+1);
          it = lower_bound(ALL(dp1[j]), n+i);
          if (it != end(dp1[j]) && *it - i == n) res = min(res, l+j+1);
          if (n % i == 0) {
            it = lower_bound(ALL(dp1[j]), n/i);
            if (it != end(dp1[j]) && *it * i == n) res = min(res, l+j+1);
          }
          if (div > 0 && i / div == n) {
            it = lower_bound(ALL(dp1[j]), div);
            if (it != end(dp1[j]) && *it == div) res = min(res, l+j+1);
          }
        }
      }
      for (ll i: dp2[l]) {
        if (i == n) res = min(res, l);
        if (l > 8) continue;
        res = min(res, l + len(abs(n - i)) + 1);
        if (n % i == 0) res = min(res, l + len(n/i) + 3);
        ll div = i / n;
        if (div > 0 && i / div == n) res = min(res, l + len(div) + 3);
      }
    }
    cout << res << endl;
  }
  return 0;
}