Maximum Data Transmission Rate

In this problem, we consider a data transmission system in which data is sent from one computer to another via a cable. The cable supports \(k\) different voltage levels. The voltage level changes every \(\frac{1}{n}\) second (each change is called a pulse). A data packet is composed of \(m\) consecutive pulses (i.e. one packet is sent every \(\frac{m}{n}\) seconds).

Due to technical limitations, a data packet cannot maintain a constant voltage level throughout and must change voltage several times. More precisely, if a packet contains any contiguous block of \(l\) pulses with the same level, then that packet cannot be sent. (Note that adjacent packets do not affect each other.)

If there are \(x\) possible valid packets, then each packet can encode \(\log_2 x\) bits of information (this value can be fractional). Z wants to know the maximum number of bits that can be transmitted in 1 second.

Your task is: given the four integers \(k, n, m, l\) as input, compute the maximum number of bits that can be transmitted in one second. In one second, \(\frac{n}{m}\) packets can be sent, so the answer is \(\frac{n}{m} \times \log_2(x)\), where \(x\) is the number of valid packets that can be generated using the above rules.

The constraints are such that you can use dynamic programming to count the number of valid packets. A valid packet is a sequence of \(m\) pulses (each chosen from \(k\) levels) that does not contain any contiguous subsequence of \(l\) identical pulses. For example, if \(l=3\), then any packet that contains three or more consecutive pulses with the same level is invalid.

The answer should be output as a floating‐point number with a precision up to 6 decimal places.

inputFormat

The input consists of a single line containing four integers:

• \(k\): the number of different voltage levels,
• \(n\): the reciprocal of the pulse duration (i.e. there are \(n\) pulses per second),
• \(m\): the number of pulses in one packet, and
• \(l\): the minimum length of a constant subsequence that is forbidden.

outputFormat

Output a single floating‐point number: the maximum number of bits that can be transmitted in 1 second, rounded (or printed) to 6 decimal places.

sample

2 8 4 3

6.643856