luogu#P11045. [蓝桥杯 2024 省 Java B] 最优分组

[蓝桥杯 2024 省 Java B] 最优分组

题目描述

小蓝开了一家宠物店,最近有一种 X 病毒在动物之间进行传染,小蓝为了以防万一打算购买测试剂对自己的宠物进行病毒感染测试。

为了减少使用的测试剂数目,小蓝想到了一个好方法:将 NN 个宠物平均分为若干组,使得每组恰好有 KK 只宠物,这样对同一组的宠物进行采样并混合后用一个试剂进行检测,如果测试结果为阴性则说明组内宠物都未感染 X 病毒;如果是阳性的话则需要对组内所有 KK 只宠物单独检测,需要再消耗 KK 支测试剂(当 K=1K=1 时,就没必要再次进行单独检测了,因为组内只有一只宠物,一次检测便能确认答案)。

现在我们已知小蓝的宠物被感染的概率为 pp,请问 KK 应该取值为多少,才能使得期望的测试剂的消耗数目最少?如果有多个答案,请输出最小的 KK

输入格式

第一行,一个整数 NN

第二行,一个浮点数 pp

输出格式

输出一行,一个整数 KK 表示答案。

1000
0.05
5

提示

【评测用例规模与约定】

对于 30%30\% 的评测用例:1N101\leq N\leq 10

对于 60%60\% 的评测用例:1N10001\leq N\leq 1000

对于 100%100\% 的评测用例:1N1061\leq N\leq 10^60p10\leq p\leq 1