本题主要考察:数学归纳法
模拟非常的好写,此处不再赘述。
注意特殊性质A:
保证n是7的倍数
用模拟法求出 n=1…50 时的答案(2s)
可以发现,当 n/7≥3 时,
答案的前缀按 n 排序后分别为
888,108,188,200,208,288,688
答案后缀为 ceil(n/7.0) 个8.
注意特判 n=1…14 的情况。
就此,一个 O(Tlogn) 的算法诞生了!
#include <bits/stdc++.h>
using namespace std;
int T, n, d[20] = {0, -1, 1, 7, 4, 2, 6, 8, 10, 18, 22, 20, 28, 68, 88},
s[8] = {888, 108, 188, 200, 208, 288, 688};
int main()
{
scanf("%d", &T);
while (T--)
{
scanf("%d", &n);
if (n <= 14) printf("%d\n", d[n]);
else
{
printf("%d", s[n % 7]);
for (int i = 1; i <= ceil(n / 7.0) - 3; i++) putchar('8');
putchar('\n');
}
}
return 0;
}