[CSP-J 2024] 小木棍

题目描述

小 S 喜欢收集小木棍。在收集了 $n$ 根长度相等的小木棍之后，他闲来无事，便用它们拼起了数字。用小木棍拼每种数字的方法如下图所示。

现在小 S 希望拼出一个正整数，满足如下条件：

• 拼出这个数恰好使用 $n$ 根小木棍；
• 拼出的数没有前导 $0$；
• 在满足以上两个条件的前提下，这个数尽可能小。

小 S 想知道这个数是多少，可 $n$ 很大，把木棍整理清楚就把小 S 折腾坏了，所以你需要帮他解决这个问题。如果不存在正整数满足以上条件，你需要输出 $-1$ 进行报告。

输入格式

本题有多组测试数据。

输入的第一行包含一个正整数 $T$，表示数据组数。

接下来包含 $T$ 组数据，每组数据的格式如下：

一行包含一个整数 $n$，表示木棍数。

输出格式

对于每组数据：输出一行，如果存在满足题意的正整数，输出这个数；否则输出 $-1$。

输入输出样例 #1

输入 #1

5
1
2
3
6
18

输出 #1

-1
1
7
6
208

说明/提示

【样例 1 解释】

• 对于第一组测试数据，不存在任何一个正整数可以使用恰好一根小木棍摆出，故输出 $-1$。
• 对于第四组测试数据，注意 $0$ 并不是一个满足要求的方案。摆出 $9$、$41$ 以及 $111$ 都恰好需要 $6$ 根小木棍，但它们不是摆出的数最小的方案。
• 对于第五组测试数据，摆出 $208$ 需要 $5+6+7=18$ 根小木棍。可以证明摆出任何一个小于 $208$ 的正整数需要的小木棍数都不是 $18$。注意尽管拼出 $006$ 也需要 $18$ 根小木棍，但因为这个数有前导零，因此并不是一个满足要求的方案。

【数据范围】

对于所有测试数据，保证：$1\le T\le 50$，$1\le n\le 10^5$。

测试点编号	$n\le$	特殊性质
$1$	$20$	无
$2$	$50$	无
$3$	$10^3$	A
$4,5$	$10^5$	A
$6$	$10^3$	B
$7,8$	$10^5$	B
$9$	$10^3$	无
$10$	$10^5$	无

特殊性质 A：保证 $n$ 是 $7$ 的倍数且 $n\ge 100$。

特殊性质 B：保证存在整数 $k$ 使得 $n=7k+1$，且 $n\ge 100$。

火柴棒与数字的对应关系（经典规则）：

• 数字 0 需6根，1 需2根，2 需5根，3 需5根，4 需4根，5 需5根，6 需6根，7 需3根，8 需7根，9 需6根。

解决这道题的核心思路

1. 位数优先：最小的数优先保证位数最少（位数少的数一定比位数多的小）。
2. 单个数字最小化：位数相同时，高位数字越小，整体越小。
3. 利用8的特性：8消耗7根火柴（单个数字中最多），优先用8减少位数，再用余数构造最小前缀。

代码如下：

#include <bits/stdc++.h>
using namespace std;

int T,n;
 
int main() {
	cin >> T;
	while(T--){
		cin >> n;
		if(n == 1)
			cout << -1;
		else if(n == 2) 
			cout << 1;
		else if(n == 3) 
			cout << 7;
		else if(n == 4) 
			cout << 4;
		else if(n == 5) 
			cout << 2;
		else if(n == 6) 
			cout << 6;
		else if(n == 7) 
			cout << 8;
		else if(n == 10)
			cout << 22;
		else if(n%7 == 0)
			for(int i = 1;i <= n/7;i++)cout<<8;
		else if(n%7 == 1){
			cout << 10; 
			for(int i = 1;i <= n/7-1;i++) 
				cout << 8;
			}
		else if(n%7 == 2){
			cout << 1; 
			for(int i = 1;i <= n/7;i++) 
				cout << 8;
			}
		else if(n%7 == 3){
			cout << 200; 
			for(int i = 1;i <= n/7-2;i++) 
				cout << 8;
			}
		else if(n%7 == 4){
			cout << 20; 
			for(int i = 1;i <= n/7-1;i++) 
				cout << 8;
			}
		else if(n%7 == 5){
			cout << 2; 
			for(int i = 1;i <= n/7;i++) 
				cout << 8;
			}
		else if(n%7 == 6){
			cout << 6; 
			for(int i = 1;i <= n/7;i++) 
				cout << 8;
			}
			
		cout << "\n";
	}
    
    return 0;
}

分析：

核心思路是：优先使用消耗火柴棒最多的单个数字（8，需7根）以减少位数（位数越少，数字越小），再用余数部分补充最小可能的数字。

首先特殊值处理（小 n 的情况）

直接硬编码 n 较小时的结果：

• n=1：无法组成任何正整数（最小数字1需2根），输出 -1。
• n=2：只能组成 1（2根），输出 1。
• n=3：只能组成 7（3根），输出 7。
• n=4：只能组成 4（4根），输出 4。
• n=5：最小数字为 2（5根），输出 2。
• n=6：最小数字为 6（6根），输出 6。
• n=7：只能组成 8（7根），输出 8。
• n=10：特殊处理为 22（2个2，每个5根，共10根）。

通用情况（n≥8）

根据 n 除以7的余数（r = n % 7）分类处理，因为 8 是单个数字中消耗火柴棒最多的（7根），优先用 8 可减少位数：

• r=0：n 是7的倍数，全用 8 组成数字（如 n=14 输出 88）。
• r=1：剩余1根无法组成数字，需减少1个 8（节省7根），此时余数变为 1+7=8，用 10（1需2根+0需6根=8根）补充，后面跟 (n/7 - 1) 个 8（如 n=8 输出 10）。
• r=2：剩余2根可组成 1（2根），输出 1 加 n/7 个 8（如 n=9 输出 18）。
• r=3：剩余3根需配合减少2个 8（节省14根），余数变为 3+14=17，用 200（2需5根+0需6根+0需6根=17根）补充，后面跟 (n/7 - 2) 个 8（如 n=17 输出 200）。
• r=4：剩余4根需减少1个 8（节省7根），余数变为 4+7=11，用 20（2需5根+0需6根=11根）补充，后面跟 (n/7 - 1) 个 8（如 n=11 输出 20）。
• r=5：剩余5根可组成 2（5根），输出 2 加 n/7 个 8（如 n=12 输出 28）。
• r=6：剩余6根可组成 6（6根），输出 6 加 n/7 个 8（如 n=13 输出 68）。

时间复杂度分析：

这段代码的时间复杂度是 O(T × n)，其中 T 是测试用例数量，n 是每个测试用例的输入值。符合时间限制