ZOJ Problem Set - 3294
It was in a war torn feudal era. For some strange reason, people in this era had animal ears and a tail. There was a peaceful village named Yamayura on the border of a country. There, lived two little girls, Eruruu and Aruruu. Eruruu was an apothecary and had a forceful but caring personality while Aruruu was her shy little sister who talked briefly.
Aruruu was fond of asking some strange problems. One day, she thought of a quite strange problem and asked Eruruu. Eruruu didn't know how to deal with it at all. So she turned to you for help. If you helped her solve the problem, she will give you a big bowl of delicious Mororo porridge. So here is the problem. Eruruu has got 150 betaines(A kind of drug). They all initially have an effect value A. To achieve the best effect, the effect value should reach B. Eruruu knows that Aruruu has got some magical tickets which can change effect value. But Aruruu says, "Well, I will only give you tickets which make effect value LARGER, or it's just a waste of time. And I won't give you too many tickets. For any two values i and j(1 ≤ i < j ≤ 100000), if the following three rules is satisfied, I will give you one ticket which can change a betaine with effect value i to value j."
Suppose i&j is n.
So, please help Eruruu calculate after getting as many tickets as possible, at most how many betaines can reach the best effect.
There are less than 100 test cases.
One line for each case, containing the number of betaines at most which can reach the most effect.
1 2 65403 65471
Author: ZHUANG, Junyuan
Source: ZOJ Monthly, January 2010