icp备案查询网站,深圳市做网站的企业,海外网站服务器下载,甘肃省作风建设年活动有网站[CSP-J 2024] 小木棍
题目描述
小 S 喜欢收集小木棍。在收集了 n n n 根长度相等的小木棍之后#xff0c;他闲来无事#xff0c;便用它们拼起了数字。用小木棍拼每种数字的方法如下图所示。 现在小 S 希望拼出一个正整数#xff0c;满足如下条件#xff1a;
拼出这个数…[CSP-J 2024] 小木棍
题目描述
小 S 喜欢收集小木棍。在收集了 n n n 根长度相等的小木棍之后他闲来无事便用它们拼起了数字。用小木棍拼每种数字的方法如下图所示。 现在小 S 希望拼出一个正整数满足如下条件
拼出这个数恰好使用 n n n 根小木棍拼出的数没有前导 0 0 0在满足以上两个条件的前提下这个数尽可能小。
小 S 想知道这个数是多少可 n n n 很大把木棍整理清楚就把小 S 折腾坏了所以你需要帮他解决这个问题。如果不存在正整数满足以上条件你需要输出 − 1 -1 −1 进行报告。
输入格式
本题有多组测试数据。
输入的第一行包含一个正整数 T T T表示数据组数。
接下来包含 T T T 组数据每组数据的格式如下
一行包含一个整数 n n n表示木棍数。
输出格式
对于每组数据输出一行如果存在满足题意的正整数输出这个数否则输出 − 1 -1 −1。
样例 #1
样例输入 #1
5
1
2
3
6
18样例输出 #1
-1
1
7
6
208提示
【样例 1 解释】
对于第一组测试数据不存在任何一个正整数可以使用恰好一根小木棍摆出故输出 − 1 -1 −1。对于第四组测试数据注意 0 0 0 并不是一个满足要求的方案。摆出 9 9 9、 41 41 41 以及 111 111 111 都恰好需要 6 6 6 根小木棍但它们不是摆出的数最小的方案。对于第五组测试数据摆出 208 208 208 需要 5 6 7 18 5 6 7 18 56718 根小木棍。可以证明摆出任何一个小于 208 208 208 的正整数需要的小木棍数都不是 18 18 18。注意尽管拼出 006 006 006 也需要 18 18 18 根小木棍但因为这个数有前导零因此并不是一个满足要求的方案。
【数据范围】
对于所有测试数据保证 1 ≤ T ≤ 50 1 \leq T \leq 50 1≤T≤50 1 ≤ n ≤ 1 0 5 1 \leq n \leq 10^5 1≤n≤105。
测试点编号 n ≤ n\leq n≤特殊性质 1 1 1 20 20 20无 2 2 2 50 50 50无 3 3 3 1 0 3 10^3 103A 4 , 5 4,5 4,5 1 0 5 10^5 105A 6 6 6 1 0 3 10^3 103B 7 , 8 7,8 7,8 1 0 5 10^5 105B 9 9 9 1 0 3 10^3 103无 10 10 10 1 0 5 10^5 105无
特殊性质 A保证 n n n 是 7 7 7 的倍数且 n ≥ 100 n \geq 100 n≥100。
特殊性质 B保证存在整数 k k k 使得 n 7 k 1 n 7k 1 n7k1且 n ≥ 100 n \geq 100 n≥100。
【题目分析】 我们可以知道要拼成0到9这十个数字的火柴棒个数分别是6255456376。 不难发现组成8的小木棍个数最多需要7根小木棍结合题目中给到的特殊数据可以得到如果小木棍的数量为7的倍数尽量去拼数字8最好如果拼其它的数字我们所得到的数字位数较多而题目中要求拼出的数字尽可能小。 【代码实现】 那么根据7的倍数和余数关系可以得到 如果正好是7的倍数那么所有的小木棍都去拼8可以拼出n/7个8如果n%7的结果是1那么会存在两种情况第一种情况是只有1根小木棍无法拼出任何一个数字所以输出-1第二种情况是在尽量去拼8的情况下会多出8根小木棍可以拼成10那么可以输出10和(n-8)/7个8。如果n%7的结果是2那么可以先输出一个1然后让剩下的小木棍都去拼8后面输出(n-2)/7个8。如果n%7的结果是3那么存在3种情况第一种是小木棍的数量为3那么输出7即可第二种是小木棍的数量是10那么可以输出22。第三种是小木棍的数量为17或者17以上的满足条件的数可以先输出200然后剩余的木棍拼8输出(n-17)/7个8。如果n%7的结果是4那么存在两种情况第一种是小木棍的数量为4那么输出4即可第二种是小木棍的数量为11或者11以上那么可以先输出20然后输出n-11/7个8。如果n%7的结果是5那么可以先输出一个2然后剩余的木棍可以拼成(n-5)/7个8。如果n%7的结果是6那么可以先输出一个6然后剩余的木棍可以拼成(n-6)/7个8。 #includebits/stdc.h
using namespace std;
long long n, t;
int main() {cin t;while (t--) {cin n;int m n % 7;if (m 0) {for (int i 1; i n / 7; i)cout 8;cout endl;continue;}if (m 1) {if (n 1)cout -1 endl;else {cout 10;for (int i 1; i n / 7 - 1; i)cout 8;cout endl;}continue;}if (m 2) {cout 1;for (int i 1; i n / 7; i)cout 8;cout endl;continue;}if (m 3) {if (n 3)cout 7 endl;else if (n 10)cout 22 endl;else {cout 200;for (int i 1; i (n - 17) / 7; i)cout 8;cout endl;}continue;}if (m 4) {if (n 4)cout 4 endl;else {cout 20;for (int i 1; i (n - 11) / 7; i)cout 8;cout endl;}continue;}if (m 5) {cout 2;for (int i 1; i (n - 5) / 7; i)cout 8;cout endl;continue;}if (m 6) {cout 6;for (int i 1; i (n - 6) / 7; i)cout 8;cout endl;continue;}}return 0;
}
