谷歌编程挑战赛要求参赛者在有限的时间内通过编程来解决复杂的算法问题。竞赛允许参赛者选择所熟悉的编码语言和开发环境。报名日期为2009年8月10日至2009年9月3日。

比赛流程大致是：先和来自世界各地的参赛者在网上比赛；从网上比赛的选手中选出25个最佳参赛者，前往在美国加州山景城的谷歌总部进行决赛。决赛时间定于2009年11月13日，届时将决出全球总冠军。

关于更详细大赛信息和报名详情，请访问谷歌全球编程挑战赛主页。请注意，报名截止时间是9月3日；报名注册的第一步是需要有一个Google Account, 如果您还没有Google Account，那就请在注册第一步的页面上创建属于自己的Google Account（如图中所示点击“Create an account now”）。

谁较咱好奇心强呢~~~就注册了一个。。。结果发现Qualification Round正好在9月2号搬家日~~~不知道搬了家还有没有精神去programing～～～～

不过细细读了一下比赛规则，发现这一轮的自动化程度还是很高的：

• 两道题，一道４分钟内解决 另一道８分钟之内解决
• 都是先从比赛网页上下载输入数据 自己写算法程序 生成输出数据 提交结果和源代码到比赛网页
• 网页会立刻判断提交数据是否正确（失败了可以用新的输入数据重新做，这样想必是为了防止穷举答案～～～）
• 通过答题结果，系统自动筛选出进入下一轮的选手
• 感觉１：这个比赛很适合搞数据结构 算法设计的 Master or PhD 学生 也很适合有志于去google工作的程序员
• 感觉２：这一轮应该不会很难，估计到了后面和人（其他选手）斗（在线斗）才是真正的其乐无穷！

找了上一节比赛的题目来看了一下，非常有意思

Problem：拯救宇宙？！（深受超人哲学毒害的美国人。。。）

The urban legend goes that if you go to the Google homepage and search for "Google", the universe will implode. We have a secret to share… It is true! Please don’t try it, or tell anyone. All right, maybe not. We are just kidding. 有个秘密，在google主页上搜“Google” 宇宙就会爆炸！！！

The same is not true for a universe far far away. In that universe, if you search on any search engine for that search engine’s name, the universe does implode! 诸如此类，在搜索引擎X上面搜“X” 宇宙就会爆炸！

To combat this, people came up with an interesting solution. All queries are pooled together. They are passed to a central system that decides which query goes to which search engine. The central system sends a series of queries to one search engine, and can switch to another at any time. Queries must be processed in the order they’re received. The central system must never send a query to a search engine whose name matches the query. In order to reduce costs, the number of switches should be minimized.人们想了个办法，把所有的query都先送到一个地方（central system）去预处理（按照队列模型），然后由这个系统分发到不同的搜索引擎去，并且保证“X”不要被送到X搜索引擎去。这里的切换次数应该被最小化。

Your task is to tell us how many times the central system will have to switch between search engines, assuming that we program it optimally.告诉我们：这个处理系统需要在不同搜索引擎之间切换多少次？

Input

The first line of the input file contains the number of cases, N. N test cases follow.

Each case starts with the number S — the number of search engines. The next S lines each contain the name of a search engine. Each search engine name is no more than one hundred characters long and contains only uppercase letters, lowercase letters, spaces, and numbers. There will not be two search engines with the same name.

The following line contains a number Q — the number of incoming queries. The next Qlines will each contain a query. Each query will be the name of a search engine in the case.

Output

For each input case, you should output:

Case #X: Y

where X is the number of the test case and Y is the number of search engine switches. Do not count the initial choice of a search engine as a switch.

解答可见这里：http://code.google.com/codejam/contest/dashboard?c=32013#s=a&a=0， 跟我的感觉差不多，就是排序 or 分类， 把相同字段放在一起。官方答案的分类办法还是比较naive的，我想的还稍微复杂了一点，先建个hash table index来存储一个segment里面的字段，然后计数每类字段有几个，这样就可以计算switch个数了，复杂度是O(N)。

Share on Facebook

      地名 初亏   全食始(食既)   食甚   全食终(生光)   复圆

上海 8时23分25秒 9时36分44秒 9时39分16秒 9时41分49秒 11时01分36秒

重庆 8时07分54秒 9时12分59秒 9时15分08秒 9时17分17秒 10时30分34秒

常州 8时21分44秒 9时35分23秒 9时36分28秒 9时37分34秒 10时57分55秒

无锡 8时22分03秒 9时35分10秒 9时37分05秒 9时39分01秒 10时58分48秒

苏州 8时22分21秒 9时35分13秒 9时37分41秒 9时40分10秒 10时59分41秒

杭州 8时21分26秒 9时34分11秒 9时36分55秒 9时39分40秒 10时59分21秒

宁波 8时23分07秒 9时37分20秒 9时39分34秒 9时41分50秒 11时02分44秒

嘉兴 8时22分20秒 9时35分01秒 9时37分59秒 9时40分57秒 11时00分21秒

湖州 8时21分31秒 9时33分50秒 9时36分45秒 9时39分41秒 10时58分50秒

绍兴 8时21分52秒 9时35分19秒 9时37分42秒 9时40分05秒 11时00分26秒

舟山 8时23分54秒 9时38分01秒 9时40分38秒 9时43分16秒 11时03分53秒

合肥 8时18分39秒 9时30分48秒 9时31分48秒 9时32分49秒 10时52分07秒

芜湖 8时19分37秒 9时31分06秒 9时33分38秒 9时36分10秒 10时54分45秒

鞍山 8时19分57秒 9时32分15秒 9时33分52秒 9时35分29秒 10时54分47秒

铜陵 8时18分49秒 9时29分47秒 9时32分39秒 9时35分31秒 10时53分46秒

安庆 8时17分46秒 9时28分30秒 9时31分15秒 9时34分01秒 10时52分15秒

黄山 8时18分58秒 9时32分40秒 9时33分29秒 9时34分19秒 10时55分27秒

巢湖 8时19分10秒 9时30分47秒 9时32分46秒 9时34分46秒 10时53分29秒

六安 8时17分45秒 9时28分58秒 9时30分29秒 9时32分00秒 10时50分31秒

宣州 8时19分55秒 9时31分26秒 9时34分17秒 9时37分10秒 10时55分47秒

贵池 8时18分19秒 9时29分13秒 9时32分03秒 9时34分54秒 10时53分10秒

九江 8时16分19秒 9时28分46秒 9时29分23秒 9时30分00秒 10时50分15秒

武汉 8时14分53秒 9时23分56秒 9时26分39秒 9时29分24秒 10时46分15秒

黄石 8时15分31秒 9时25分32秒 9时27分53秒 9时30分16秒 10时48分05秒

荆州 8时12分48秒 9时20分47秒 9时23分21秒 9时25分57秒 10时41分56秒

宜昌 8时12分11秒 9时19分27秒 9时22分07秒 9时24分48秒 10时40分01秒

荆门 8时13分09秒 9时20分58秒 9时23分32秒 9时26分07秒 10时41分48秒

鄂州 8时15分25秒 9时25分00秒 9时27分37秒 9时30分14秒 10时47分37秒

孝感 8时14分41秒 9时23分25秒 9时26分08秒 9时28分53秒 10时45分22秒

黄冈 8时15分25秒 9时24分56秒 9时27分35秒 9时30分15秒 10时47分33秒

咸宁 8时14分35秒 9时24分52秒 9时26分31秒 9时28分12秒 10时46分26秒

随州 8时14分36秒 9时24分08秒 9时25分30秒 9时26分53秒 10时44分02秒

恩施 8时10分28秒 9时16分50秒 9时19分23秒 9时21分58秒 10时36分26秒

成都 8时07分05秒 9时11分06秒 9时12分47秒 9时14分29秒 10时26分22秒

自贡 8时06分44秒 9时10分55秒 9时13分01秒 9时15分07秒 10时27分27秒

遂宁 8时07分51秒 9时12分09秒 9时14分25秒 9时16分43秒 10时28分59秒

内江 8时07分01秒 9时11分08秒 9时13分26秒 9时15分45秒 10时27分59秒

乐山 8时06分15秒 9时09分31秒 9时11分54秒 9时14分19秒 10时25分38秒

南充 8时08分22秒 9时13分10秒 9时15分12秒 9时17分15秒 10时30分00秒

广安 8时08分30秒 9时13分16秒 9时15分42秒 9时18分09秒 10时30分56秒

达州 8时09分34秒 9时15分44秒 9时17分07秒 9时18分30秒 10时32分34秒

雅安 8时06分05秒 9时08分57秒 9时11分16秒 9时13分36秒 10时24分24秒

眉山 8时06分35秒 9时09分52秒 9时12分14秒 9时14分38秒 10时25分53秒

资阳 8时07分05秒 9时10分46秒 9时13分11秒 9时15分37秒 10时27分18秒

康定 8时05分34秒 9时08分06秒 9时10分10秒 9时12分16秒 10时22分38秒

Share on Facebook

   大地震过去3天了，在全国大动员展开救援的同时，全世界的地质学家的目光也聚集在了四川。

   这次地震震波波及范围远至3300公里处，台湾岛内都有震感，几乎半个亚洲都在摇晃，据说它释放的能量相当于两百多颗原子弹的能量。

   中国的一个地质学家最近说，这次发生的原因相当罕见，并不是板块之间相互推挤，它是欧亚板块内部释放百年累积的能量所导致。

   印度洋板块一直在向东北方向挤压，促使青藏高原板块向东北方向移动，这股能量不断向内集中，在四川平原与平原西部山区地下岩层处积累，蓄积很慢，蓄积规模大（从汶川附近到雅安附近大概300公里长的岩层），但上百年的积累终于挤破大岩层，释放出巨大能量。由于它是浅层地震，震波相当长，能量衰减慢，所以传播距离相当长。

   而三峡水库对这次地震造成的影响难以准确判断，三峡库区距振源700公里，新形成的水库对地层构成压力并造成一定形变，但这种形变对汶川附近地层的影响程度无法估计，有可能促使汶川处地层提前断裂，也有可能减缓汶川处地层压力，这种影响需要大规模长期性的研究才能得出结论。

   而震前动物行为异常的报告也很普遍。据父母说当天中午睡觉的时候就被外面喳喳乱叫的各种鸟惊醒。不过目前对动物在震前行为异常的研究还不够精确到位，还无法根据动物行为异常就断定有地震而疏散大量人群。

   据说这次地震余震持续时间将会比较长，从几个星期到一年的可能性都不小。

   题外话：除此之外，这次地震当中暴露出来的大量学校建筑豆腐渣工程值得大家思考，为什么在很多地方学校校舍塌了，但是紧挨着的一些六七十年代的老房子或者商品房就没有垮？据记者说破裂的柱子里面暴露出的是细如发丝的钢筋。

日本的学校建筑要求比普通建筑的抗震性更强。在日本，地震时，学校体育馆和教学楼一般都是用来供学生和周边居民躲避的地方，而中国的学校地震时是大批大批埋葬可爱的孩子们的坟墓，值得大家深思和改进啊~~~愿悲剧不再重演~~~！！！

Share on Facebook