865E - Hex Dyslexia - CodeForces Solution

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
inline int geti(char c) {return isdigit(c) ? c - '0' : c - 'a' + 10;}
inline char getc(int x) {return x < 10 ? x + '0' : x + 'a' - 10;}
char s[16];int n;ll d[20],sum[1 << 14];ll ans = LLONG_MAX,f[1 << 14];
inline int lowbit(int x) {return x & -x;}
void solve()
{
int lim = 1 << (n - 1);memset(f,63,sizeof(ll) * lim);f[0] = 0;sum[0] = d[n - 1];
for (int i = 1;i < lim;i++) sum[i] = sum[i - lowbit(i)] + d[__lg(lowbit(i))];
for (int i = 0;i < lim;i++)
{
if (sum[i] < 0 || sum[i] > 15) continue;
for (int j = 0;j < n;j++)
if (!(i & (1 << j))) f[i | (1 << j)] = min(f[i | (1 << j)],f[i] + (sum[i] << (j * 4)));
}
ans = min(ans,f[lim - 1]);
}
void dfs(int pos,int cnt)
{
if (pos == n - 1)
{
if (!cnt) solve();
return;
}
if (cnt < n - pos) dfs(pos + 1,cnt);
if (cnt) { d[pos] -= 16;d[pos + 1]++;dfs(pos + 1,cnt - 1);d[pos] += 16;--d[pos + 1]; }
}
void print(ll x,int c)
{ if (c == 1) cout << getc(x);else print(x >> 4,c - 1),cout << getc(x & 15); }
int main ()
{
ios::sync_with_stdio(false);
cin >> s;n = strlen(s);ll sum = 0,tt = 1,num = 0;
for (int i = n - 1;i >= 0;--i,tt *= 16) sum += geti(s[i]) * tt,num += geti(s[i]),d[i] = geti(s[n - i - 1]);
if (num % 15) {cout << "NO" << endl;return 0;}
int cnt = num / 15;dfs(0,cnt);
if (ans >= (1ll << (n * 4)) - sum) cout << "NO" << endl;else print(ans,n);
return 0;
}