ZOJ Problem Set - 3344
EZ and asmn are game fans. Lately they like to play a game like this:
First, they writes down number 1-N on N cards. Then, they shuffle the cards randomly and put them in N boxes marked 1-N from top to bottom. For example, after the shuffle, the cards from top to bottom are 3 2 4 1, then card 3 is put into box 1, card 2 is put into box 2, card 4 is put into box 3, card 1 is put into box 4.
Now they take turns to play like this: For each turn, Player takes out the card with the smallest number which is still in the box, After remember the number k on this card, he throws the card away. Player continues to take out card in the box marked k and continues, until the card he wants is no longer in the boxes, then the other player takes his turn. If the player has no card to choose in his turn, he loses the game.
So, what is the possibility that EZ will win in no more than than K turns if he always picks first?(One turn means one player makes a move)
The input contains multiple test cases. Each test case contains N(1<= N <=50) and K(1<= K <=N) in a single line.
Process to the end-of-file.
For each test case print a single line contains the possibility represented by fraction in simplest form(Attention: Even the result can be an integer, represent it as a/b where GCD(a,b)=1).
1 1 2 2
Author: CHAO, Jiansong
Contest: ZOJ Monthly, June 2010