This page is still under construction.

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

Stepping Stones

Time limit1sMemory limit1024 MB

Summary
Each row has 1 tempered and 2 normal glasses; players cross in order and die on normal glass. Find the probability that the K-th player survives all N rows.
Level

Medium7 of 10

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

Problem

While watching the drama Squid Game, Ilwoo became curious about the game called stepping stones. The question was: "When the length of the stepping stones is N, what is the probability that the K-th player to start survives?" Ilwoo solves math problems as easily as breathing, so he found the solution right away. However, full of curiosity, Ilwoo also wondered about the probability when the number of glasses in a row is 3 instead of 2, and since he could not find the answer, he brought this problem to you. The new stepping stones problem you must solve is as follows.

There are N rows, each with 1 tempered glass and 2 normal glasses. Tempered glass does not break when a player steps on it, while normal glass breaks the moment a player steps on it. Each player can jump at most N times during the game, and on the i-th jump the player must step on one of the glasses in the i-th row. If, after some jump, the glass stepped on is a normal glass, that glass immediately breaks and is removed from the game. The player who stepped on that glass is also eliminated from the game. A player who survives after N jumps is automatically moved to the Safe Zone and receives the game's prize of 45.6 billion won. Note that more than one player can receive the 45.6 billion won.

Normal glass and tempered glass cannot be distinguished by appearance, so players cannot know which glass is tempered until either someone has already stepped on it or the only glass remaining in a row is the one left. On the other hand, since players have good memories, when jumping to a row, if there is a glass in that row already revealed to be tempered, they step only on that glass.

K people entered this game aiming for the huge prize. Each player is numbered from 1 to K in order, and the number received equals the order in which that player starts. The game proceeds in order starting from player 1. Player i (2 ≤ i ≤ K) can move only after player i-1 is eliminated or reaches the Safe Zone.

The figure above is an example with N=4 and K=2.

Write a program that computes the probability that the K-th player in this game receives the game's prize of 45.6 billion won.

Input

Two integers N (1 ≤ N ≤ 3,000) and K (1 ≤ K ≤ 456) are given, separated by a space.

Output

Output the probability that the K-th player in this game receives 45.6 billion won. An answer is accepted as correct if its absolute or relative error from the model answer is at most 10-6.

Examples2

  1. Example 1

    Input
    4 2
    
    Expected output
    0.061728395062
    
  2. Example 2

    Input
    1 1
    
    Expected output
    0.333333333333