Wheel of Fortune

Special Judge Time Limit: 2000/1000MS (Java/Others) Memory Limit: 128000/64000KB (Java/Others)

Problem Description

      The popular show “Wheel of Fortune” attracts people from the whole country to their TV screens at the Friday night. The show proceeds as follows.
      There are n persons taking part in a show. The goal of the show is to guess the secret word. Initially only the number of letters in a word l is known, the letters are shown at the special tableau as the black boxes.
      The player who makes the turn chooses some letter. If this letter exists in the secret word, all of its occurences are open and the player makes the next turn. If there is no such letter the turn moves over to the next player. After the last player the turn gets back to the first one. The player who guesses the last letter is the winner of the game.
      For example, let the secret word be “CONTEST”. Initially the players only see “-------”. If the first player says ‘E’, it is opened, and the players see “----E--”. The first player makes turn again, let him, for example, say ‘A’. There is no such letter in the secret word, so the turn passes on to the next player. If he says ‘T’, its occurences are opened and the players see “---TE-T”, and so on.
      Paul’s friend is going to take a part in the game. Paul would like to know what are the chances of his friend. For each player Paul has learned his intellectual potential qt. The probability that the player t would guess the letter correctly, if there are i letters still not suggested, j different letters of the word are still unknown, and k unopened boxes on the tableau, is the following:

      Here we consider 00= 1.

      Each of the unknown letters has the equal probability to be guessed. 
      Given n, the Paul’s friend’s position among the players r, the secret word, and the intellectual potentials of the players, help Paul to detect what is the probability that his friend would win in the game.

Input

       The first line of the input file contains n and r (2 ≤ n ≤ 10, 1 ≤ r ≤ n). The second line contains the secret word. It consists of capital letters of the English alphabet. Its length does not exceed 12. The third line of the input file contains n real numbers — the intellectual potentials of the players (0 ≤ qt ≤ 0:99).

Output

      Output one number — the probability that Paul’s friend would win the game. Your answer must be accurate up to 10-8.

Sample Input

3 1
CONTEST
0.7 0.2 0.1

Sample Output

0.4648222937

Source

Andrew Stankevich Contest 16

Manager

Information
Solved Number4
Submit Number15
Problem Tags
No tag edit access
温馨提示:AC后可以编辑标签哦. ^-^
Login
LoginCancel