Google Code Jam 2011 (Qualification)

书接上篇

1. [84%/98%] Bob Trust: 两个机器人并行依次按钮

由于要依次按钮,所以并行能节省的时间,只有另外一个机器人移动的时间,而它按钮的那一秒钟是不能节省的。

2. [87%/82%] Magicka:依次合并或者清除元素

由于即使是大数据集,合并列表和冲突列表个数也不过36和28,所以最好直接把这两个列表反向来进行匹配,而不是在后面的匹配测试中去正反测试两遍。
另外注意先合并,后判冲突。

3. [90%/85%] Candy Splitting:加法改异或

按题目叙述,不难发现Patrick的错误加法真值表与异或XOR运算相同。由于没有进位,可以单独看每个二进制位。
如果某一个二进制位上,1的个数为奇数,则无论如何划分,都不可能使得最后异或结果相等。
如果1的个数为偶数,则可以任意划分,但需要保证可怜的Patrick至少分到一个糖果。
所以排序后取最小的数给Patrick,其他的全部留给Sean。

4. [58%/97%] GoroSort:概率排序

首先注意,下面这个Smallest的条件很容易被忽略掉:
The second line of each test case will contain a permutation of the N smallest positive integers.

然后由于每个数都已经知道最后需要所在的位置,所以排除掉已经在目标位置的情况,其他的每hit一次,有1/2的机会回到正常的位置,再加上,占据现有位置的那个数,以后会有1/2的机会回到它自己的位置,所以只需要每个不在目标位置的数上累计加一就能得出结果。

这题最挨打的,就是那个%.6lf。 我是用整数表示,然后后面加6个0。这个实在太误导了,让人以为会计算很复杂的概率。

PS 最后,这次的GCJ Command Line Tool还蛮好用的,呵呵~

GCJ 2011 Qualification Round Solution Download

发表评论

电子邮件地址不会被公开。 必填项已用*标注