Чемпіон із гри в кості
Limits: 3 sec., 256 MiB
Зовсім недавно у Львові відбувся перший щорічний чемпіонат міста з гри в кості. Грається гра звичайними шестигранними кубиками з рівноймовірним випаданням кожної з граней. Грані кубиків (костей) пронумеровані числами від 1-го до 6-ти.
На чемпіонаті вже визначився переможець. Грошова винагорода переможцю теж визначається за допомогою гральних кубиків. За умовами гравець повинен кинути \(n\) кубиків одночасно, зі значень, що випали на кубиках, обрати \(k\) (\(k \le n\)) найбільших. Сума вибраних значень буде рівна виплаті переможцю в деяких грошових одиницях.
Але переможець може відмовитися від цієї суми й кинути кубики ще раз. У цьому випадку чемпіон кидатиме вже на 1 кубик менше (\(n-1\)), але все ще обиратиме \(k\) найбільших значень. Відмовлятися від виграшу можна до тих пір, поки кількість кубиків не менша ніж \(k\). Коли ж гравець прийме суму, або в нього більше не буде можливості відмовитися — він отримає винагороду, що рівна останній сумі вибраних значень.
Чемпіон просить вас допомогти визначити, яку середню очікувану суму виграшу він може отримати, якщо він відмовиться продовжувати кидати кубики в оптимальний момент.
Input
У єдиному рядку задано два цілі числа \(n\) і \(k\) — кількість кубиків на початку й кількість значень, що треба вибрати.
Output
Виведіть єдине число — середню очікувану кількість очок, що отримає гравець при оптимальній стратегії. Відповідь вважатиметься правильною, якщо її абсолютна чи відносна похибка не перевищуватиме \(10^{-7}\).
Constraints
\(1 \le n \le 35\),
\(1 \le k \le n\).
Samples
| Input (stdin) | Output (stdout) |
|---|---|
| 1 1 | 3.5 |
| Input (stdin) | Output (stdout) |
|---|---|
| 2 1 | 4.73611111 |
Submit a solution
| Element Type | Created | Who | Problem | Compiler | Result | Time (sec.) | Memory (MiB) | # | Actions |
|---|
| Element Type | Created | Who | Problem | Compiler | Result | Time (sec.) | Memory (MiB) | # | Actions |
|---|