GSoC2013 accept!

一大早收到两封来自google的邮件,终于不是thank you开头,读研这段日子收了好多公司的感谢信(微软、大摩、EMC、新思。。。集满七封是不是可以换一个offer?)google的这句Congratulations确实够振奋我心 :)

Congratulations! Your proposal "[HURD] Improve the GDB Port for GNU Hurd" submitted to "GNU Project" has been accepted for Google Summer of Code 2013. Over the next few days, we will add you to the private Google Summer of Code Student Discussion List.
Now that you've been accepted, please take the opportunity to speak with your mentors about plans for the Community Bonding Period: what documentation should you be reading, what version control system will you need to set up, etc., before start of coding begins on 17 June.
Welcome to Google Summer of Code 2013! We look forward to having you with us.
With best regards,
The Google Summer of Code Program Administration Team
少年继续努力!为开源世界贡献一份力!

[逻辑题]放下那个坏球!

题目很简单,一共有12个小球,其中有一个的质量和其他不一样,问,如何用一架天平只称3次就找到那个坏球?

分析:12个球,3次,直觉就是4个球为一组,分3组。任意拿8个球出来称一次。有两种结果,平衡,不平衡。

情况一:天平平衡,说明选中的8个球都是好球,那么坏球一定在未选中的4个里。目标缩小到四个,接下来就好办了,从4个中任选两个,然后再拿两个好球出来称一次,若平衡,则坏球在未选中的两个中,不平衡则在选中的两个中;目标缩小到两个,取一个与好球称一次,结果立现,刚好称了三次。

情况二:天平不平衡,说明未选中的4个皆为好球,目标缩小为8,此种情况略复杂。对8个目标球进行编号1-8,并记天平左边盘子为A,右边盘子为B。则第一次称可以表示为A=(1,2,3,4),B=(5,6,7,8)。 假设A<B(因为不平衡,总有一边盘子重,用此记号方便描述,无他)。

第一个关键点来了我承认我是通过枚举的方式得到的),第二次称重方式为,A=(1,5,6),B=(2,7,0)。0表示好球,因为第一次称已经确定了4个好球。

此回合的结果有三。

A=B:说明坏球在3,4,8中。目标缩小到3个,但是现在只剩一次称的机会,需要确定三个球,貌似是不可能。但是,因为第一次称有额外的信息,即第一次称的结果A<B,说明要么是3,4球中有一个是轻的,要么是8号球重了。那么只需要把3,4球分别放在天平的两端,平衡则8好球是坏球,并且坏球是重的;不平衡则,轻的那端是坏球,并且坏球是轻的。

A<B:说明坏球在1,7中。目标缩小到2个,直接拿个好球来称一次就出结果。

A>B:说明坏球在2,5,6中。目标缩小到3个,类似上面的分析,额外信息是要么5,6中有一个是坏球,并且是重了;要么是2号球轻了。然后称一次5,6即可出结果。

这道题的关键之处在于,要充分利用前一次的信息来完成推理。

++++++++++++++++++++++++分割线++++++++++++++++++++++++++++++

到这里还没有结束,此题有个变种,13个球最少称几次能找到其中的坏球?

答案还是3!

思路如下:任选8个球称一次,若不平衡,目标缩小到8个,然后用上面的思路即可。

若平衡,则目标缩小为未选中的5个球。其实分析发现两次是可以确定5个球的,再次上编号,1,2,3,4,5。

然后 A=(1,2) B=(3,0),若平衡,说明4,5是坏球,目标为2,结果立现。

若不平衡,A<B,说明要么1,2有一个轻球,要么3是重球。称一次1,2即可。

若A>B,说明要么1,2有一个是重球,要么3是轻球,称一次1,2即可。

终于可以歇口气了。。。

4月29开始备战GSoC2013,从100多个组织中海选了8个感兴趣的。包括freeBSD、LFS、Gentoo、LTTng、Tor、Debian、Buildroot、GNU。疯狂的读各个网站上的项目说明,最终把目标锁定到GNU/Hurd。

目标项目是improve the GDB port for GNU Hurd, 对hurd一头雾水,疯狂的看hurd的文档,微内核、Mash、消息传递、exception port、GDB、gdbserver。

每天都奋战到凌晨一两点,累的跟一样,被各种英文文档轮番轰炸了三天,终于艰难的完成了申请报告,刚提交了第一个补丁,终于可以舒口气。

静候结果。