#PQJ1494x8151. QOJ 1494_8151
QOJ 1494_8151
2
- 靠谱的预言家 (prop.pas/c/cpp) ★问题描述: 你也许听过诺查丹玛斯的大名吧。他是16 世纪初的犹太裔法国人,是400 年来世界最 著名的预言家。他生前留下了一本用四行体诗写成的《百诗集》,成为很多神秘学爱好者研 究未来预言的必备书籍。几个世纪后,诺查丹玛斯的后裔们组成了神秘的预言家集团,其中 每个人都有出众的预测才能。这个神秘的预言家集团采用少数服从多数的综合策略来提高整 个集团的预言准确率。假定预言家集团中有𝑛个预言家,他们都能独立地预测一个随机事件 的结果,比如,抛一枚硬币的结果是正面朝上还是反面朝上,并且预测准确率都是𝑝。考虑 如下的预言综合预测策略:以这𝑛个预言家中超过半数的预言家的预测结论为综合预测结论。 比如,在抛硬币的结果预测时,如果超过半数的预言家是预测正面,则综合策略预测正面, 否则综合策略预测反面。按此策略,如果p=81%,则可以计算出当𝑛= 3时,综合策略预测 正确的概率是90.54%。相比于单个预言家,综合策略显著地提高了预测准确率。事实上, 当p=81%时,只要𝑛≥3,综合策略的预测准确率都不小于90%。 在靠谱的预言家问题中,给定单个预言家独立预测随机事件的准确率𝑝和综合预测策略 希望达到的预测准确率𝑞,计算至少需要多少个互相独立的预言家来共同预测,才能使综合 策略的预测准确率不小于𝑞。 ★编程任务: 对于给定单个独立的预言家预测随机事件的准确率𝑝和综合策略希望达到的预测准确 率𝑞,设计一个算法来计算至少需要多少个互相独立的预言家来共同预测,才能使综合策略 的预测准确率不小于𝑞。 ★数据输入: 输入文件名为prop.in。 有𝑘组测试数据(1 ≤𝑘≤10),每行给出一组测试数据。每组测试数据由2 个实数𝑝和𝑞 组成。其中𝑝是单个独立的预言家预测的准确率,𝑞是综合策略希望达到的预测准确率。 ★结果输出: 输出文件名为prop.out。 依次输出各组测试数据至少需要的预言家数。每行输出一个数。如果不存在满足要求的 预言家数则输出-1。
输入示例 输出示例 0.81 0.90 0.60 0.90 0.40 0.40 0.90 0.80 0.49 0.50 3 41 1 1 -1