#P5308. [COCI2018-2019#4] Akvizna

    ID: 4284 Type: RemoteJudge 2000ms 250MiB Tried: 0 Accepted: 0 Difficulty: 6 Uploaded By: Tags>2019二分数位 dp斜率优化COCI

[COCI2018-2019#4] Akvizna

题目描述

你面临 nn 名参赛者的挑战,最终要将他们全部战胜。
每一轮中,都会淘汰一些选手;你会得到这一轮奖金池中 被淘汰者 除以 这一轮对手总数 比例的奖金。

例如某一轮有 1010 个对手,淘汰了 33 个,那么你将获得奖金池中 3/103/10 的奖金。

假设每一轮的奖金池均为一元,Mirko 希望通过恰好 kk 轮赢得比赛,那么他最多可能获得多少奖金呢?

你只需要输出答案保留 99 位小数即可。

输入格式

一行两个正整数 n,kn,k

输出格式

输出一行一个实数表示答案。

5 3
2.100000000
10 10
2.928968254

提示

样例1解释:

最优的情况为:
第一轮淘汰 33 人,剩下两轮各淘汰 11 人。
获得奖金为 35+12+11=2.1\frac{3}{5}+\frac{1}{2}+\frac{1}{1}=2.1 元。

数据范围:

对于20%20\%的数据,1n1001\le n\le 100

对于40%40\%的数据,1n30001\le n \le 3000

对于100%100\%的数据,1kn1051\le k \le n \le 10^5

本题较卡精度,请留意。