#P2978. [Poi2002]协议

    ID: 2099 传统题 1000ms 512MiB 尝试: 49 已通过: 18 难度: 5 上传者: 标签>CF1800普及+/提高-线性 DP计数 DP滚动数组高精度加法高精度乘法提取最高置位

[Poi2002]协议

题目描述

Mr ZHU 在一个通讯公司工作,他承担了公司的网络协议设计任务。目前他致力于通过一条电缆从一台电脑发送数据到另一台电脑。在电缆中有 kk 种不同的电平,每秒有 nn 个脉冲。每个脉冲持续 1/n1/n 秒,期间电平保持不变。数据打包发送时,包含了 mm 个连续的脉冲。(即每 mn\displaystyle \frac{m}{n} 秒发送一个包)。

由于技术原因, 在同一个包内,任意连续 ll 个脉冲的电平不能全部相同。这个限制不跨越包的边界。如果某种协议允许发送 xx 个不同的包,那么能对一个包进行 log⁡2x\log_2 x 二进制位的编码。Mr ZHU 想知道在 11 秒内最多能发送多少位信息。

例如,假设电缆允许我门发送 22 种不同的电平的信息(k=2k=2),我们用 00 和 11 表示。如果电平每秒有 2020 次变化(n=20n=20),包含有 44 个脉冲(m=4m=4),在每个包内有 33 个连续的脉冲具有同一种电平(l=3l=3),这时我们不能发送这些包: 0000,0001,1000,1111,1110,01110000, 0001, 1000, 1111, 1110, 0111. 但是可以发送这些包: $0010, 0011, 0100, 0110, 0101, 1101, 1100, 1011, 1001$ 与 10101010。当一个要发送 1010 个不同种类的包,我们对每个包进行 log⁡210\log_2 10 位信息编码。在一秒内可以发送 20/4=520/4 = 5 个包,也就是 5log⁡210≈16.60965\log_2 10 \approx 16.6096 位信息。

输入格式

有四个整数:电平种类 kk,脉冲的频率 nn,数据包的大小 mm,在一个包中连续脉冲的数目 ll,也就是说在这个范围内必须改变电平。

输出格式

输出每秒最多能传送的比特数,并向下取整。若有 xx 种合法的数据包,输出 ⌊(n/m)log⁡2x⌋\left\lfloor(n/m)\log_2 x\right\rfloor。

样例输入

2 20 4 3

样例输出

16

数据规模与约定

对于 100%100\% 的数据,2≤k≤102 \leq k \leq 10,1≤n≤1×1031 \leq n \leq 1\times 10^3,1≤m≤1001 \leq m \leq 100,2≤l≤m2 \leq l \leq m,n/mn/m 为不超过 1010 的正整数。

题目来源