当前位置:首页 > 动态规划 > 正文
SSOJ4389火柴
2030+

题目大意:n根火柴,能拼出的最小数字和最大数字分别是多少?

题目描述

众所周知的是,火柴棒可以拼成各种各样的数字。具体可以看下图:

通过2根火柴棒可以拼出数字“1”,通过5根火柴棒可以拼出数字“2”,以此类推。
现在LYK拥有k根火柴棒,它想将这k根火柴棒恰好用完,并且想知道能拼出的最小和最大的数分别是多少。

输入

一个数k。

输出

两个数,表示最小的数和最大的数。注意这两个数字不能有前导0。

样例输入

15

样例输出

108 7111111

提示

对于20%的数据n<=10
对于40%的数据n<=100
对于60%的数据n<=1000
对于100%的数据1<=n<=100000。

解题思路

最大数:位数越多越好,多拼出1,每两根火柴拼出1个1;如果恰好用尽,位数是最多的,肯定是最大的;如果还剩下1根,那么为了保持位数最大,拼出一个7即可。

最小数:位数越少越好,多拼出8,预估位数不超过15位,可以用long long,避免高精度。f[i]表示i根火柴拼出的最小值,预处理出最高位,因为不能是0,所以特殊处理。

当然,暴力搜索也可以,因为除了1或者8,其他数字的数量很少。

程序实现

About

坚决不Copy代码!

本文标签:,,,,,,

SSOJ4389火柴:等您坐沙发呢!

发表评论

您必须 [ 登录 ] 才能发表留言!