Language: C++

#include <bits/stdc++.h>
using namespace std;
#define FOR(i,k,n) for(ll i = (k); i < (n); i++)
#define REP(i,n) FOR(i,0,n)
#define ALL(a) a.begin(), a.end()
#define MS(m,v) memset(m,v,sizeof(m))
#define D10 fixed<<setprecision(10)
typedef vector<ll> vi;
typedef vector<string> vs;
typedef pair<ll, ll> pii;
typedef long long ll;
const ll INF = LLONG_MAX / 100000;
const ll MOD = 1000000007;
const double EPS = 1e-10;
template<class T> T &chmin(T &a, const T &b) { return a = min(a, b); }
template<class T> T &chmax(T &a, const T &b) { return a = max(a, b); }

/*--------------------template--------------------*/

const ll MAX = (1ll << 36) - 1;
vector<vector<ll>> p(15);
ll n;
ll len;


int pow(ll x, ll n)
{
	ll res = 1;
	while (n > 0)
	{
		if (n & 1) res = res * x;
		x = x*x;
		if (res > MAX) return INF;
		n >>= 1;
	}
	return res;
}

void make_power()
{
	FOR(i, 2, 10)FOR(j, 2, 10)
	{
		ll t = pow(i, j);
		if (t >= 1000) p[3].push_back(t);
	}
	FOR(i, 2, 10)FOR(j, 10, 100)
	{
		ll t = pow(i, j);
		if (t > MAX) break;
		if (t >= 10000) p[4].push_back(t);
	}
	FOR(i, 10, 100)
		FOR(j, 2, 10)
	{
		ll t = pow(i, j);
		if (t > MAX) break;
		if (t >= 10000) p[4].push_back(t);
	}
	FOR(i, 100, 1000)FOR(j, 2, 10)
	{
		ll t = pow(i, j);
		if (t > MAX) break;
		if (t >= 100000) p[5].push_back(t);
	}
	FOR(i, 10, 100)FOR(j, 10, 100)
	{
		ll t = pow(i, j);
		if (t > MAX) break;
		if (t >= 100000) p[5].push_back(t);
	}
	FOR(i, 1000, 10000)FOR(j, 2, 10)
	{
		ll t = pow(i, j);
		if (t > MAX) break;
		if (t >= 1000000) p[6].push_back(t);
	}
	FOR(i, 10000, 100000)FOR(j, 2, 10)
	{
		ll t = pow(i, j);
		if (t > MAX) break;
		if (t >= 10000000) p[7].push_back(t);
	}
	FOR(i, 100000, 1000000)FOR(j, 2, 10)
	{
		ll t = pow(i, j);
		if (t > MAX) break;
		if (t >= 100000000) p[8].push_back(t);
	}
	FOR(i, 3, 9) sort(ALL(p[i]));
}

ll length(ll t)
{
	if (t == 0) return 100;
	ll cnt = 0;
	while (t > 0)
	{
		cnt++;
		t /= 10;
	}
	return cnt;
}

ll add(ll a, ll b) //return x, a+x=b or a-x=b
{
	return abs(b - a);
}

ll mul(ll a, ll b) //return x, a*x=b or a/x=b
{
	if (a == b) return INF;
	if (a < b) return (b / a*a == b ? b / a : INF);
	if (a > b) return (a / (a / b) == b ? a / b : INF);
}

/*--------------------4~--------------------*/


ll P() //P = N^N
{
	FOR(i, 3, len + 1)
	{
		if (find(ALL(p[i]), n) != p[i].end()) return i;
	}
	return 100;
}

/*--------------------6~--------------------*/

ll P_op_N()
{
	ll res = 99;
	FOR(i, 3, len - 2)
	{
		if (p[i][0] > n) chmin(res, i + length(p[i][0] - n) + 1);
		else if (p[i].back() < n) chmin(res, i + length(n - p[i].back()) + 1);
		else
		{
			auto it = lower_bound(ALL(p[i]), n);
			chmin(res, i + length(*it - n) + 1);
			if (it != p[i].begin()) chmin(res, i + length(n - *(it - 1)) + 1);
		}
	}
	FOR(i, 3, len - 2)
	{
		REP(j, p[i].size())
		{
			ll t = mul(p[i][j], n);
			chmin(res, length(t) + i + 1);
		}
	}
	return res;
}


/*--------------------8~--------------------*/

ll P_op_N_op_N()
{
	ll res = 98;
	FOR(i, 3, len - 4)
	{
		REP(j, p[i].size())
		{
			if (p[i][j] == n) break;
			else if (p[i][j] < n)
			{
				FOR(k, 2, pow(10, len - i - 4))
				{
					ll t = p[i][j] * k;
					if (t > MAX) break;
					chmin(res, i + length(k) + length(add(t, n)) + 2);
				}
			}
			else if (p[i][j] > n)
			{
				FOR(k, 2, pow(10, len - i - 4))
				{
					ll t = p[i][j] / k;
					if (t < 10) break;
					chmin(res, i + length(k) + length(add(t, n)) + 2);
				}
			}
		}
	}
	FOR(i, 3, len - 4)
	{
		REP(j, p[i].size())
		{
			FOR(k, 2, pow(10, len - i - 4))
			{
				ll t = p[i][j] * k;
				if (t > MAX) break;
				chmin(res, i + length(k) + length(mul(t, n)) + 2);
			}
		}
	}
	return res;
}


ll P_op_P()
{
	ll res = 97;
	FOR(i, 3, len - 4)
	{
		REP(j, p[i].size())
		{
			ll t = add(p[i][j], n);
			ll u = mul(p[i][j], n);
			FOR(k, 3, len - i - 1)
			{
				if (p[k].back() >= t&&*lower_bound(ALL(p[k]), t) == t) chmin(res, (ll) i + k + 1);
				if (p[k].back() >= u&&*lower_bound(ALL(p[k]), u) == u) chmin(res, (ll) i + k + 1);
			}
		}
	}
	return res;
}


/*--------------------10~--------------------*/

ll P_op_P_op_N()
{
	ll res = 96;
	FOR(i, 3, len - 6)
	{
		REP(j, p[i].size())
		{
			FOR(k, 3, len - i - 3)
			{
				REP(l, p[k].size())
				{
					vector<ll> t;
					if (p[i][j] * p[k][l] <= MAX) t.push_back(p[i][j] * p[k][l]);
					if (p[i][j] / p[k][l] > 0) t.push_back(p[i][j] / p[k][l]);
					REP(m, t.size())
					{
						ll tmp = add(t[m], n);
						chmin(res, i + k + length(tmp) + 2);
						tmp = mul(t[m], n);
						chmin(res, i + k + length(tmp) + 2);
					}
				}
			}
		}
	}
	return res;
}

ll P_mul_N_div_N_op_N()
{
	ll res = 95;
	FOR(i, 3, len - 6)
	{
		REP(j, p[i].size())
		{
			FOR(k, 2, pow(10, len - i - 6))
			{
				ll t = p[i][j] * k;
				if (t > MAX) break;
				FOR(l, 2, pow(10, len - i - length(k) - 5))
				{
					ll tt = t / l;
					chmin(res, i + length(k) + length(l) + length(add(tt, n)) + 3);
					chmin(res, i + length(k) + length(l) + length(mul(tt, n)) + 3);
				}
			}
		}
	}
	return res;
}

ll P_op_N_and_N()
{
	ll res = 94;
	FOR(i, 3, len - 6)
	{
		REP(j, p[i].size())
		{
			FOR(k, 1, pow(10, len - i - 6))
			{
				vector<ll> t;
				if (p[i][j] + k <= MAX) t.push_back(p[i][j] + k);
				if (p[i][j] - k > 0) t.push_back(p[i][j] - k);
				FOR(l, 2, pow(10, len - i - length(k) - 5))
				{
					REP(m, t.size())
					{
						if (t[m] * l == n || t[m] / l == n || pow(t[m], l) == n)
							chmin(res, i + length(k) + length(l) + 4);
					}
				}
			}
		}
	}
	return res;
}

ll P_mul_N_dif_P()
{
	ll res = 93;
	FOR(i, 3, len - 6)
	{
		REP(j, p[i].size())
		{
			FOR(k, 2, pow(10, len - i - 6))
			{
				vector<ll> t;
				if (p[i][j] * k <= MAX) t.push_back(p[i][j] * k);
				if (p[i][j] / k > 0) t.push_back(p[i][j] / k);
				FOR(l, 3, len - i - length(k) - 2)
				{
					REP(m, 2)
					{
						ll tmp = add(t[m], n);
						if (find(ALL(p[l]), tmp) != p[l].end()) chmin(res, i + length(k) + length(l) + 2);
					}
				}
			}
		}
	}
	return res;
}

ll P_add_P_mul_N()
{
	ll res = 92;
	FOR(i, 3, len - 6)
	{
		REP(j, p[i].size())
		{
			FOR(k, 2, pow(10, len - i - 6))
			{
				vector<ll> t;
				if (p[i][j] * k <= MAX)
				{
					t.push_back(n + p[i][j] * k);
					t.push_back(n - p[i][j] * k);
				}
				if (p[i][j] / k > 0)
				{
					t.push_back(n + p[i][j] / k);
					t.push_back(n - p[i][j] / k);
				}
				FOR(l, 3, len - i - length(k) - 2)
				{
					REP(m, t.size())
					{
						if (find(ALL(p[l]), t[m]) != p[l].end()) chmin(res, i + length(k) + l + 2);
					}
				}
			}
		}
	}
	return res;
}

ll solve()
{
	len = to_string(n).size();
	ll res = len;
	if (len >= 4)
	{
		chmin(res, P());
	}
	if (len >= 6)
	{
		chmin(res, P_op_N());
	}
	if (len >= 8)
	{
		chmin(res, P_op_N_op_N());
		chmin(res, P_op_P());
	}
	if (len >= 10)
	{
		chmin(res, P_op_P_op_N());
		chmin(res, P_mul_N_div_N_op_N());
		chmin(res, P_op_N_and_N());
		chmin(res, P_add_P_mul_N());
	}
	return res;
}

int main()
{
	make_power();
	while (cin >> n&&n != -1)
	{
		cout << solve() << endl;
	}
	return 0;
}

Compiler output:
a.cc:8:16: error: 'll' was not declared in this scope
    8 | typedef vector<ll> vi;
      |                ^~
a.cc:8:18: error: template argument 1 is invalid
    8 | typedef vector<ll> vi;
      |                  ^
a.cc:8:18: error: template argument 2 is invalid
a.cc:10:14: error: 'll' was not declared in this scope
   10 | typedef pair<ll, ll> pii;
      |              ^~
a.cc:10:18: error: 'll' was not declared in this scope
   10 | typedef pair<ll, ll> pii;
      |                  ^~
a.cc:10:20: error: template argument 1 is invalid
   10 | typedef pair<ll, ll> pii;
      |                    ^
a.cc:10:20: error: template argument 2 is invalid
a.cc: In function 'int pow(ll, ll)':
a.cc:33:39: warning: overflow in conversion from 'long long int' to 'int' changes value from '92233720368547' to '-702313053' [-Woverflow]
   33 |                 if (res > MAX) return INF;
      |                                       ^~~
a.cc: In function 'll mul(ll, ll)':
a.cc:114:1: warning: control reaches end of non-void function [-Wreturn-type]
  114 | }
      | ^