#P2431. Mooncake Tasting on Mid-Autumn Festival
Mooncake Tasting on Mid-Autumn Festival
Mooncake Tasting on Mid-Autumn Festival
On Mid-Autumn Festival, uim brings a set of mooncakes of different sizes and flavors. The weight of these mooncakes are given in grams as follows: \(1g, 2g, 4g, 8g, 16g, \dots\), where each mooncake (beyond the first) weighs twice as much as the previous one. There is exactly one mooncake of each weight.
A girl who wishes to try as many different flavors as possible will choose a subset of these mooncakes. However, she also has two constraints:
- The total weight must be at least \(A\) grams.
- The total weight must not exceed \(B\) grams.
She wants to maximize the number of mooncakes she eats while satisfying the above constraints. Note that you can only select each mooncake at most once, and mooncakes cannot be split.
Your task is to determine the maximum number of mooncakes she can eat such that there exists a selection whose total weight \(S\) fulfills \(A \le S \le B\).
Hint: The available mooncakes are the ones with weights \(2^0, 2^1, \dots, 2^m\) where \(2^m \le B\). For any subset of \(k\) mooncakes taken from these, the minimum possible total weight is \(S_{min} = 2^k - 1\) (obtained by taking the \(k\) smallest mooncakes) and the maximum possible weight is \(S_{max} = 2^{m+1} - 2^{m-k+1}\) (obtained by taking the \(k\) largest available mooncakes). The answer is the maximum \(k\) for which a selection exists with \(S_{min} \le B\) and \(S_{max} \ge A\}.
inputFormat
The input consists of two space‐separated integers \(A\) and \(B\) (in grams) on one line. It is guaranteed that \(1 \le A \le B\).
outputFormat
Output a single integer, the maximum number of mooncakes that can be eaten such that the total weight is between \(A\) and \(B\) (inclusive). If no valid selection exists, output 0.
sample
1 1
1