Google Code Jam 2016资格赛

周六醒来习惯性刷微博,Google Code Jam 2016资格赛已经在早上七点开始了。于是赶紧跑来实验室注册+看题,当然以我的水平,估计也就能通过资格赛了。不知道是不是这次的比较简单,第一题是“一道送分题”,第二题能想到解决方案,但是不确定是正确的答案,第三题第一遍读题没读懂。。。因为整个资格赛持续27个小时,于是就先陪女朋友去了北海公园,晚上回来的路上想的具体算法方案,八点多回实验室才答的题。

附一张北海公园的照片,可以直接看到白塔、景山(左侧有个亭子的山)、国家大剧院(右侧一个圆弧形的建筑),不知道为什么,即使在空气质量还可以的天气,远处依旧是灰蒙蒙的。

北海公园

能直接看到白塔、景山、国家大剧院

目前资格赛已经结束,每道题目都有题目分析,而且可以看到别人提交的答案的代码。感觉能学到挺多东西的。(为什么之前我不知道!!……)我把自己当时做题时的解法,以及自己看懂的分析做一个记录。毕竟第一次参加,第一次晋级第一轮……

A 题(这真的是一道送分题)

题意:数羊。提供一个数 N,每次数羊只会数 i*N 这个数,然后算每一位出现的数字,当0~9全部出现时,输出这个时候的 i*N(感觉好像表述的不清楚),如果不能,则输出 IMPOSSIBLE。

Solution:开始的时候想,i 从1~10,即可,之后发现不对。因为如果 N 是偶数的话,i~10很可能只找到了一半的数字。最终的提交是设定的100作为 i 的上界,避免 IMPOSSIBLE 的时候会死循环。但是看分析,似乎除了0,其他所有数字都是有界的,于是可以直接计算,不会无限循环。

B 题

题意:翻煎饼。煎饼分正反,要求把所有煎饼都翻成正面朝上。当时搜了一下,发现竟然还有一种排序方法叫“翻煎饼排序”……不过两个的场景一样,但求解的问题不同。

Solution:看了题目的输入输出,发现:从前往后扫,每次遇到前后煎饼面不同时,翻一次;最后如果所有煎饼都朝下,再翻一次。不过感觉自己不能证明这种方法所用到的次数是最小的,代码实现一遍提交,结果是对的。。。这也是唯一一次搞定代码,一次提交通过的题目。

提交过后又想了一下:每次翻转,最多只能减少一个相邻煎饼不同的情况,于是这种方法应该是正确的。最后一次翻转,是为了让正面朝上

C 题

题意:我应该是读了三遍左右才彻底明白题目的含义。满足某种条件的string,叫 jamcoin, 它起始是1,末尾是1,只包含01,按2~10进制解读,其结果均为非素数。求解满足这一条件的数字。

Solution:暴力算啊!因为只有01,且最后一位为1,按二进制转为十进制后,就是奇数啊,根据题条件,可以确定一个上下界。然后按其他进制进行转变,算是否存在因子。因为 Python 中的 int 函数可以直接做 base 转换,就直接用 Python 写了,这也是我第一次用 Python 做题。

因为代码中,一个 if 分支的解读错误,导致最后输出了一些不是 jamcoin 的数字,两次提交都错了。不过解题思想似乎是对的(暴力除了复杂度高,代码比较冗余,为什么不对……)。

看分析,对 Small 数据结果的观察,可以发现一些规律。利用这些功率,构造 Large 数据的答案。

D 题

题意:我感觉以我的语言,似乎解释不清楚。。。大意是,将一个包含字母 L 和字母 G 的串,按照一定规则进行扩展:当某一位是 L 是,复制一遍这个串,当某一位是 G 时,添加原始串长度的 G。然后求解,需要哪几位,可以判定原始串中,是否包含 G。

Solution:这题看题意就知道,是一个不可能用暴力求解。在 Small 数据下,需要的位数和原始串的长度是相同的;Large 数据集时,所需位数小于等于原始串长,这种的结题方法还没有看。由构造规则可以知道,当原串第一个字母是 L 时,扩展串第一部分就是原串;当原串第一个字母是 G 时,扩展串第一部分全是 G。于是利用前 n 位(n 是原串长度),即可判定是否包含 G。(但是这个解答,直到第 n 遍看题不懂后,询问了以为大神,才明白怎么做)

Large 数据集的解答。。。我再慢慢看

总结:

发现几道题目,代码都不难,甚至也都不包含什么算法。更多的是看懂题目(ಥ_ಥ),找到所需的规律即可。毕竟资格赛,可能考察的是大家的逻辑思维能力,和写代码能力。估计第一轮会被虐的很惨。。。看了一下时间,应该第一场和第三场的时间可以做。第二场对应周日0点,考虑到周一要开组会,应该会放弃掉……

发表评论

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