This page is still under construction.

Parts of this page are still being built. What you see may change.

Painting Pips

Time limit1sMemory limit1024 MB

Summary
Given N dice and M total pips to distribute across faces, find the maximum expected product of the rolled values.
Level

Hard8 of 10

Topics
Math, Dynamic programming, Greedy, Probability
Solved
No attempts yet

Problem

Alice and Bob like playing games. Lately they have been playing a game in which Alice rolls NN dice and Bob pays her a dollar amount equal to the product of the numbers rolled on the NN dice. But for lack of the required skill, Alice and Bob have grown bored.

To spice things up, they decide to use a custom set of dice. Specifically, Alice has NN blank 66-sided dice and she gets to paint pips on them. She has enough paint to paint MM pips. Subject to this constraint, she can paint the dice however she wants; for example, she may paint more than 66 pips on one side of a die. Note that she can choose to paint 00 pips on a side; if any of the rolled numbers is 00, the product is 00.

Assuming Alice paints the dice optimally, what is the expected value of her winnings in this game?

Input

The only line of input contains two space-separated integers, NN (1≤N≤201 \leq N \leq 20) and MM (1≤M≤1001 \leq M \leq 100): the number of dice in the game and the maximum number of pips Alice may paint in total, respectively.

Output

Output a single real number, Alice's expected winnings. Your answer is considered correct if its absolute or relative error is at most 10−610^{-6}.

Notes

In the first sample case, the best Alice can do is to put one pip on each die. This gives her an expected value of 1/361/36.

In the second sample case, one optimal strategy for Alice is to put a pip on each side of the die. No matter what she rolls, she receives a payout of 11.

In the final sample case, Alice can only paint 11 pip, so no matter what she does, she will always receive a payout of 00.

Examples4

  1. Example 1

    Input
    2 2
    
    Expected output
    0.027777777778
    
  2. Example 2

    Input
    1 6
    
    Expected output
    1.000000000000
    
  3. Example 3

    Input
    2 3
    
    Expected output
    0.055555555556
    
  4. Example 4

    Input
    2 1
    
    Expected output
    0.000000000000