\(\text{C - 1, 2, 3 - Decomposition}\)
解法
定义一个数为好数当且仅当它由 \(1,2,3\) 组成，\(f(i)\) 就是 \(i\) 的答案。
分而治之 的思想挺妙的，但我压根没想到。考虑将 \(n\) 分解成 \(10p+r\) 的形式（并非除数与余数），可以想到，\(f (p)\) 分解的每个好数再乘以 \(10\) 加上 \(1,2,3\) 就又是一个好数。
基于此，不妨令 \(k\le r\le 3k\)，那么如果 \(f(p)\le k\) 就意味着一定能找出解，即有 \(1,2,3\) 与每个好数匹配。注意不满足条件也不意味着一定无解，这点下文详细再谈。
考虑时间复杂度。
打表发现，\(f(n)\le 5\)。现在我们加以证明：转化一下，现在只用证明 \(n\) 一定能被分解成这样的 \(p,r\) 满足 \(f(p)\le 5\) 且 \(5\le r\le 15\)。我们可以归纳证明。首先当 \(i\le 15\) 时一定有 \(f(i)\le 5\)，对于其它情况，你发现 \(r\) 的个位取值取到了 \([0,9]\) 中每个数字！而我们又可以任意减去 \(10\) 的倍数，所以结论得证。
既然我们证明这样构造一定有解，就不用考虑不满足构造仍有解的情况了。
由于 \(f(n)\le 5\) 且 \(5\le r\le 15\)，我们容易得出对于每个 \(n\)，\(p\) 至多有两种取值，而迭代次数由于每次除以 \(10\) 非常小。所以这是可过的。
代码
#include <cstdio>
#define print(x,y) write(x),putchar(y)
template <class T> inline T read(const T sample) {
T x=0; int f=1; char s;
while((s=getchar())>‘9‘||s<‘0‘) if(s==‘-‘) f=-1;
while(s>=‘0‘&&s<=‘9‘) x=(x<<1)+(x<<3)+(s^48),s=getchar();
return x*f;
}
template <class T> inline void write(const T x) {
if(x<0) return (void) (putchar(‘-‘),write(-x));
if(x>9) write(x/10);
putchar(x%10^48);
}
#include <map>
using namespace std;
typedef long long ll;
map <ll,int> mp;
int f(ll n) {
if(mp.count(n)) return mp[n];
int ans=-1;
for(ll k=1;k<=n;++k) {
for(ll i=k;i<=k*3;++i) {
if(n-i<0) break;
if((n-i)%10==0) {
if(f((n-i)/10)<=k) {
ans=k; break;
}
}
}
if(~ans) break;
}
return mp[n]=ans;
}
int main() {
mp[0]=0;
for(int T=read(9);T;--T) {
ll n=read(9ll);
print(f(n),‘\n‘);
}
return 0;
}