900. 二进制数据压缩

单点时限: 2.0 sec

内存限制: 512 MB

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

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

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

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

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

输入格式

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

  • 20% 的数据满足 $N \leq 50$;
  • 60% 的数据满足 $N \leq 1~000~000~000$;
  • 100% 的数据满足 $N \leq 10^{18}$。

输出格式

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

样例

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

247 人解决,316 人已尝试。

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

2.8 EMB 奖励。

创建: 6 年,6 月前.

修改: 9 月前.

最后提交: 5 月,1 周前.

来源: N/A

题目标签