ZOJ Problem Set - 3415
SanGuoSha is a famous card game which is base on the roles in Three Kingdoms. Zhou Yu is one roles in this card game.
Zhou Yu has a skill called "fanjian" , he can make one player to choose one suit from m different suits, and then the player will choose one of the cards held by Zhou Yu. If the the suit of this card is different from the suit he chose, the player will lose one health point(hp).
We make a little change here , if the suit is the same as he chose , the player will gain one hp , else the player will lose one hp, and the hp of this player can not exceed n, and the game will be over when hp reaches 0. Anyway, the card would be back to Zhou Yu after the player pick it and check the suit. Every time the player randomly choose a suit and randomly pick a card, what he did at the previous rounds don't make sense.
Now I want to know the expectation of rounds this game will last, which means how many times the player can guess before his hp reaches 0.
There are about 1000 test cases, processing to the end of file.
The first line the each case contains two integer n,m, at first the player has n health point, m is the number of suits of all the cards. (2<=n <=106,2<=m<=106).
For each test case, print one float number, the expectation you get. If the error is no more than 1e-8, the answer will be accepted.
Author: CHEN, Zhangyi
Contest: ZOJ Monthly, October 2010