如何出一个BT的题目

-只说  sayonly.com                 english | other        geek挑战google
 


昨天写了个google程序大赛（Google Code Jam）的文儿，winters mi在后面留言说，“好像这么急躁的认定某些事情不是很好吧”，并且给了2个题目的链接，应该是winters mi做了印度的google程序大赛的题目的链接（1，2），在第二个链接中，winters mi说，那个500分的看起来比较难，我就简单的以之为例分析一下，如何出一个比较BT的题目。

不过这里的分析比较技术啦（这么说让真正的geek见笑了），不关心技术的请跳过后面这段。不过只说只是简单看了一下，也许玄虚还没有完全看出来，看到不是，请指出。

只说把题目简单读了一遍，大致意思是，4个战区，你占有一个，敌人占三个。每个区有一定的军队，你可以任选一个区用一定数目的军队进攻，进攻时，军队损失的概率是一定的，有一张表如下：
进攻方   |防守方   |军队折损|概率
超过三人|超过一人|2  - 0    |2275/7776
超过三人|超过一人|1  - 1    |2611/7776
超过三人|超过一人|0  - 2    |2890/7776
……
每次，进攻选择为最优方案。

隐藏的条件如下：
1，在进攻时，总需要选择目前双发力量对比最优的方案，这决定了具有相同军队数量组合总会得到相同的胜率；
2，每次进攻会得到有限数量（小于3个）的有效结果，有效结果可以形成另一个敌我双方对比；
3，每个有效结果概率一定，会形成敌我双方不同的力量对比（减去一个驻守），然后根据状态判断选择下一次进攻方案。
4，军队数量组合的数量一定，可以考虑逐个进行计算。

由于限定我方军队数不超过50，所以敌我双方的比只有一定数量，例如50*20*3=3000个不同的组合，可能通过多次叠代得到结果。把所有结果，是我方胜利的概率相加，得出最后的胜率。所以只需要拟定几个方法即可叠代出结果
1，当前对比下选择进攻谁；
方法：attackTarget（）
根据剩下战区的军队数，以及我军数量，算出我们军队损失最小的进攻战区
2，计算有效结果即概率
方法：double attack（int attackNumber,int defendNumber）
其中prob为当前力量对比出现的概率，返回值是当前对比力量的胜率
3，判断一方是否消灭
判断一方是否被消灭，如果是敌方被消灭，则加到胜率的概率里面去

时间关系，就不实践了。呵呵。
接下来，就像在“据说”一文中说的一样，我们来hack这个题目，以证明比出题者更BT。

先看一下通常方法的叠代次数。
通常方法就是从当前敌我双方对比力量开始计算，计算到一方被消灭，如果敌方被消灭，就加到胜率里面。显然这种方法的叠代次数太多，没法完成，精度也不能保 证（结果要求误差不得小于1E-9）。按最坏的情形，每次进攻如果敌我双方数量加起来超过4的时候，任何一种结果敌我双方会损失掉2个军队，那么按照最大 数50+20来算，最多要叠代（50+20）/2次，也就是35次，每次会有3个不同的结果，那么会有3的35次方，结果是5后面跟17个0。

这个数量太恐怖了，很容易让人辨别出来。如果出题bt点的话，应该计算一下正好发生精度问题/次数过多问题的敌我数量之比，把这个数量作为上限（而不是 50和20）。让答题的人洋洋得意自以为已经得到正确答案的时候，不失时机地给出他没有察觉的问题，让他们从极度兴奋霎那间变成极度气馁，一股凉气从心底 升起，充分感受到命运的残酷。

当然bt之处绝不止这一个地方，我们可以把三个结果中的一个结果的概率设置得十分小，或者隐藏其中的一个概率，参与者也许并不留心概率加起来不等于 100%，由于这个概率并不大，所以验证的例子可以选择几个不影响的例子。如果在正确答案公布的时候指出这个小小却十分严重的失误，那么作者一定羞惭至 死，几十年后，也许觉得人生一切成云烟的时候，还会为了这个小小的失误而耿耿于怀，哈哈。

 
 
 
        （ 订阅RSS频道：文儿 feed.sayonly.com   收藏  tag.sayonly.com ）

Click here to view the original Webpage.

---

Sent using R|mail.