900. 二进制数据压缩

单点时限: 2.0 sec

内存限制: 512 MB

数据压缩的目的在于减少数据存储与通信的冗余。

现有一个二进制数据压缩算法:把连续 n (n>2)个 1 替换为 n 的二进制表示。

例如,可以把数据 11111111001001111111111111110011 (对应的十进制数 4280811507)压缩为10000010011110011(对应的十进制数 66803)。原始数据有 32 位长,压缩以后的数据仅有 17 位。

这个压缩方法的缺点在于,有时解压缩过程可能从同一条数据解压出多个可能的原始数据,从而导致无法获得真正的原始数据。

现给定一个数据,要求输出按照上述规则压缩得到的较短的数据。

输入格式

在一行中输入原始数据N(以十进制正整数形式输入)。

  • 20% 的数据满足 N50
  • 60% 的数据满足 N1 000 000 000
  • 100% 的数据满足 N1018

输出格式

在一行中输出压缩以后的数据(以十进制形式输出)、压缩前的有效二进制位数和压缩后的有效二进制位数,中间用逗号分隔。

样例

Input
4280811507
Output
66803,32,17
Input
999999999999999999
Output
14299781569298,60,44

247 人解决,317 人已尝试。

300 份提交通过,共有 1260 份提交。

2.8 EMB 奖励。

创建: 6 年,10 月前.

修改: 1 年,1 月前.

最后提交: 2 周,1 天前.

来源: N/A

题目标签