ZOJ Problem Set - 2709
Many lotteries now publish ads proclaiming that they have a super-prize in each ticket. The idea is the following. The ticket has n windows, each of which contains some letter. Initially all windows are covered by the opaque substance. A person who buys the ticket removes the covering substance from m windows and if the letters revealed can be combined to form the winning m-letter word, the ticket owner wins the super-prize. The advertised features are the following: each ticket can win, and the only letters that are hidden in the windows are the letters from the winning word.
Assuming that the person uncovers m randomly chosen windows, you have to find the probability of winning a super-prize. Of course, the winning probability depends on the exact multi-set of the letters in the windows. For example, if the winning word is WOW and there are four windows, the letters used may be:
There are mutiple cases in the input file.
The first line of each case contains n (1 <= n <= 60 ). The second line contains the winning word. It contains only capital letters of the English alphabet, its length does not exceed n.
There is an empty line after each case.
On the first line of the output file print the maximal possible probability of winning, as an irreducible fraction. On the second line print the minimal possible probability of winning in the same form.There should be am empty line after each case.
4 WOW 7 VICTORY 60 ABRACADABRA
3/4 1/2 1/1 1/1 635250/29290609 1/6854002506
Source: Andrew Stankevich's Contest #10