小木棍 (CSP-J 2024)

用火柴棍拼数字，问恰好用完 $n$ 根火柴棍能拼成的最小的数是多少。

直观来看，最小的数字首先应该位数最少，然后高位数字尽量小。同时因为 $n$ 比较大（ $10^5$ ），我们考虑是否有贪心解。

从每个数字消耗的火柴数量入手：

0 1 2 3 4 5 6 7 8 9
6 2 5 5 4 5 6 3 7 6

以下是一个分类讨论思考过程，中间记录了一下部分的思考错误，试图找出一个简单的贪心法：

剩下大于等于7的时候，全用8，每次消耗7根，这样数字位数最少
如果除7余6，则我们在数字后面加9，余5在前面加2，余4在前面加4，余3在前面加7，余2在前面加1
余1更复杂，因为1个火柴不能拼成数字，所以我们考虑去掉一个8，数字前面加10
这样我们得到一个贪心法，但关键是我们要检查这个办法对不对，从1开始检查前面一些数字，发现1-10都是对的，但不幸的是11不对，用这个办法得到48（余4），但正确答案应该是20。这里的原因，是虽然都是两位，但高位数不是简单用8之后剩下的数，而是可以再有更优的优化组合。

小结一下，我们感觉应该有贪心解，但是直接找到的办法不对。不过，虽然这个“尽量放8，最后余数做调整”的贪心法不对，但我们可以做一个重要的观察：最小数的位数的确是 $\lceil \frac{n}{7} \rceil$ ，因为首先这个最小位数是可以达到的（上面的办法给出了一个具体的操作办法），而且这个位数的确是最小的（数字无法再短）。

这时我们基于最小位数的发现，就可以来设计正确的贪心算法了：

如果 $n=1$ ，则输出 $-1$
$n$ 根火柴，拼成的最小数的位数必须是：

$f(n)=\lceil \frac{n}{7} \rceil$

所以，一个正确的结果，位数必须正好是 $f(n)$ 。
我们穷举选择最小的最高位上的数字：第一位不能是0，其它位可以是所有10个数字之一
我们最高位数字选择最小的 $x$ ，使得以下成立：

$f(n-x)=f(n)-1$

也就是说，剩下的火柴，必须能够拼成一个位数为 $f(n)-1$ 的数字。
最后一位必须用完所有剩下火柴。

以下代码就实现了这个算法。

另外，实际上上面分类讨论的办法也是可以走下去细化的，可以参考这个解。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
 
 
int c[] = {6,2,5,5,4,5,6,3,7,6};  // sticks for each number
int n, a;
 
int main() {
    scanf("%d", &n);
    while (n--) {
        scanf("%d", &a);
        if (a <= 1) {
            printf("-1\n");
            continue;
        }
        int cnt = (a+6)/7;
        for (int i = 0; i < cnt; i++) {
            for (int j = i ? 0 : 1; j < 10; j++) {
                int rem = a - c[j];     // remaining sticks
                int ds = cnt - i - 1;   // should make this many digits
                if (ds == 0 && rem == 0 ||
                    ds == 1 && rem > 0 && rem <= 7 && rem != 1 ||
                    ds > 1 && (rem + 6)/7 == ds)
                {
                    printf("%d", j);
                    a -= c[j];
                    break;
                }
                if (j == 9) {
                    printf("failure\n");
                    assert(false);
                }
            }
        }
        printf("\n");
    }
    return 0;
}