Our warmest thanks to Kevin Bodurtha aka moxieman for this problem!
Dafydd is a shepherd with a small farm next to a gentle river in a quiet wooded valley in Wales. In the evening after a busy day of tending his sheep, he enjoys sitting by the fire and reading the Mabinogion, a collection of medieval Welsh tales filled with myth and legend.
While he was reading one day, he came across a curious passage:
And he came towards a valley, through which ran a river; and the borders of the valley were wooded, and on each side of the river were level meadows. And on one side of the river he saw a flock of white sheep, and on the other a flock of black sheep. And whenever one of the white sheep bleated, one of the black sheep would cross over and become white; and when one of the black sheep bleated, one of the white sheep would cross over and become black.
Dafydd realized that the place being described sounded suspiciously similar to his own farm! In the morning he brought his flock out to the river in the meadow, placing all black sheep on one side of the river and all white sheep on the other. Soon one of the white sheep bleated, then one of the black sheep jumped over the river and changed color into a white sheep! Amazed at the sight, Dafydd began to dance with joy (you see, white wool can be sold for more profit than black wool). However, one minute later one of the black sheep bleated, then one of the white sheep jumped over the river and changed color into a black sheep. Like clockwork, every minute one sheep at random would bleat and then a sheep of the other color (if one existed) would jump over the river and change color.
Dafydd scratched his head for a moment as he tried to analyze the situation. He imagined that he could go take a nap in a shady grove and let the sheep randomly swap colors until all sheep were a single color. Although it would be unfortunate if he ended up with an all-black flock, but with no way to predict which sheep was about to bleat, how could Dafydd influence the result of random chance?
Dafydd continued to think hard, letting his mind wander as he watched his sheep jump over the wide gently-flowing river. His cousins Marc and Haf owned their own sheep farm downstream from this river, and Dafydd began to daydream about some sheep floating down the gentle river...
Just then Dafydd sprang awake. He realized that in the minute between each bleat he could send some sheep down the river to his cousins farm. The river was wide and gentle enough to prevent any harm to the sheep, and his cousins would never turn down free livestock of any color. Those sheep would then be removed forever from his flock, but that action could grant him some degree of control over the otherwise random process.
Being a smart fellow, Dafydd quickly developed the optimal strategy for removing sheep from his flock in order to maximize the possibility of white sheep that he would end up with and got to work.
Being somewhat reluctant fellow however, he do not remove any sheep in initial position, e.g. before any jumps are made.
Input data gives the number of testcases T on the first line.
The following T lines will each give two integer values W and B corresponding to the quantities of black
and white sheep initially in the flock.
Answer should contain T values - expected final number of white sheep if sheep are removed with the optimal
strategy. Answers should be accurate to 1e-7.
Example
input data:
7
2 2
3 2
2 3
3 3
9 12
17 14
15 100
answer:
2.291666666 3.7878787879 2.115151515 3.751893939 13.30056113 27.41157104 22.6717838