大家也许想过，如果玩家足够牛 B 的话，俄罗斯方块游戏是不是永远也玩不死呢？不是的。我曾经在这里介绍过，理论上说，俄罗斯方块游戏是不能永无止境地玩下去的，总有一个时候你会死掉。事实上，如果允许电脑不随机出牌，可以有意为难你的话，电脑可以利用一个简单的算法迅速把你整死。倘若电脑真的能故意陷害你，玩俄罗斯方块会是什么样的呢？
    今天，我还真找到了这么一个在线俄罗斯方块游戏 HATETRIS 。在这个游戏中，下一个方块并不是随机给的，游戏将用一套确定性算法精心为你挑选一个对你最不利的方块，让你感受一下想要什么偏没有什么的痛苦。毫不夸张地说，在这个游戏中，即使想消掉一行也是一件很困难的事。
    游戏是用 JavaScript 写的，你可以在下面这个框架中点 start new game 直接开始游戏。游戏没有重力因素（方块不会自动下落），这可以给你充分长的思考时间。技术细节和高分记录请移步这里。
    想让俄罗斯方块更变态一些，方法不止一种。如果喜欢这个游戏，欢迎挑战我自己原创的变态俄罗斯方块 PiTetris 。

查看更多 »

    早上好！今天是 3 月 14 日，一年一度的圆周率日。为了和大家庆祝这个日子，我下载了一个 JavaScript 俄罗斯方块游戏 Js Tetris 的源代码，并且小小地修改了一下。那 7 种四联骨牌已经不复存在了，你将看到圆周率中的数字一个接一个地依次落下。这恐怕有希望成为史上最变态的俄罗斯方块了吧。
    游戏改造完毕后，我自己居然沉迷了好久。把积木换成数字后游戏变得不是一般的困难，有很多小技巧有待大家慢慢去摸索。我个人的最好成绩是第 32 位。你呢？

 

    大学生活混起来很快，不知不觉又是一年过去了。去年5月10日的ACM校内赛给我留下了许多美好的回忆，因此今年我主动去报了名（上次是被人给拖去的）。今年有点装怪，题目数量不变，但时间缩短为4个小时。原计划是从8:00做到12:00，结果可能是因为我们所在的7号机房迟迟没有开门，时间临时改成了8:15到12:15。总的来说，今年的题目比去年要糟糕得多，但也不乏一些精彩的题目。

    和去年一样，第一题依旧是所有题目中最科学的一道。题目给定一个不超过2000*2000的网格，你在最左下角的位置（即(0,0)点），你的目的地在(x,y)。要求你的路线不得经过同一个交叉点两次，且不允许左转（题目背景让这个条件顺理成章：街道靠右行，左转不方便），问合法的路线共有多少种。题目难点就是你不一定要走最近的路，完全允许你绕上一大圈；这破坏了有序性，很难构造出递推公式或动态规划模型。稍微画一下图，我们发现了一些显然但很有启发性的规律：每一次右转后，你左手边方向的所有区域都不能再走了，这很可能产生出规模更小的子问题来。另外，所有合法路线必然是有如螺旋线一样的一圈一圈绕着终点走，这种隐藏的有序性也为动态规划提供了可能。但顺着这个思路想下去屡屡碰壁，我猜不少队伍都卡在这儿了吧。

    后来我完全打翻前面的全部思路，猛然想到了一个具有决定意义的想法：街道的选取唯一地决定了整个路线。例如，假设我想计算转弯恰好11次的路线有多少条。这样的路线一定含有三条向上走的路、三条向右走的路、三条向下走的路和三条向左走的路。除去第一条路和最后一条路的位置都是确定的，其它的路选在哪一行或者哪一列唯一地决定了整个路线。因此，我们可以用排列组合直接计算出答案来。向上走的路是五选二，向右走的路是七选三，向下走的路是四选三，向左走的路是三选二。把它们各自的选取方案数乘起来就得到了拐弯11次的合法路径。于是，计算所有的路线数只需要从小到大枚举拐弯的次数，每一次计算都是常数的，总复杂度是O(n)的；整个算法的瓶颈反倒是O(n^2)的组合数预处理，不过这个复杂度完全可以承受。

查看更多 »

摘录几道题目。

计算1·2^2 + 2·3^2 + 3·4^2 + ... + 19·20^2
原式 = (1^3 + 2^3 + ... + 20^3) - (1^2 + 2^2 + ... + 20^2) = 44100 - 2870 = 41230

求2^x = 3^y - 1的所有正整数解
x=1时(1,1)是一个解；当x>1时，方程模4后左边永远等于0，右边则是(-1)^y - 1，可知y为偶数。令y=2z，那么有2^x = (3^z - 1)(3^z + 1)，这就要求3^z-1和3^z+1都是2的幂；但它们只相差2，因此它们只有可能是2和4，于是z=1，即原方程的另一个解为(3,2)。

圆周上有2008个点。选择两个点连成一条线，再选另外两点连一条线，这两条线段相交的概率为多少？
给定四个点，在三种连接方案中恰有一种会发生相交。取遍所有C(2008,4)种组合，相交的总情况数总是占了1/3，因此所求的概率就是1/3。

查看更多 »

    创意C/C++编程挑战赛Time Limit Exceeded结束，题目果然非常有创意。大家可以在这里看到比赛题目和获胜选手的代码。其中两道题很有意思，我特别喜欢。

    一道叫做Compile Error的题目要求你写一个叫做multiply的类，里面包含一个mult(int a,int b)的函数，该函数用于打印出a和b的乘积。代码中不允许出现空格、“/”和“#define”。

    第一个问题就是，定义一个类的语句是class multiply{...}，这个空格要怎么避免？只要你知道typedef int foo也可以写成int typedef foo，我们就可以利用typedef来消除空格，把类的定义写成class{...}typedef multiply。但这下后面又冒出一个空格来，这个空格怎么消呢？一个巧妙的方法就是利用int typedef foo,bar的语句，把类定义语句写成class{...}typedef*foo,multiply，其中*foo是一个不会用到的类型，但是它帮助我们奇迹般地消除了一个空格。巧妙利用星号可以消除很多空格，例如我们在定义mult函数时就可以写成void*mult(...){...}。最后一个难题就是，定义函数mult(int a,int b)，参数表里面的两个空格怎么办？其实办法依然很多。不少网友都用到了typeof，这样便可以把int a写成typeof(int)a了。完整的类定义如下：

class{public:void*mult(typeof(int)a,typeof(int)b){cout<<a*b<<endl;return(0);}}typedef*m,multiply;

    在gcc下，即使警告全开，下面这个程序编译时也一声不吱。

#include <iostream>
using namespace std;
 
class{public:void*mult(typeof(int)a,typeof(int)b){cout<<a*b<<endl;return(0);}}typedef*m,multiply;
 
int main()
{
    multiply foo;
    foo.mult(23,67);
}

查看更多 »

    上次提到，我非常关注一个即将举办的另类编程挑战赛Time Limit Exceeded，这个比赛的得分算法很另类，它将根据你代码的总长度和特定字符的多少而定。在刚刚结束的测试赛中，有几个题目非常具有挑战性，参赛者提交的代码也是牛气冲天。

 
Power of 2
问题：
    输入数据含有多行，每行一个正整数。对每个数，检查看它是否是2的幂，是则输出yes，不是则输出no。
    你的程序不允许使用分号。
    规定0也是2的幂。

得分：
    S= length of code + number of whitespaces;
    score = (250000)/(S^2);

查看更多 »

刚过完年回到家，也跟大家说一声新年快乐。
今天莫名其妙地收到一封邮件，邀请我参加felicity.iiit.ac.in举办的几个编程比赛。我看了一下介绍，这些比赛还是挺有意思的，这里向大家推荐一下。

http://felicity.iiit.ac.in/codecraft/
CodeCraft，举办了两三年了，一个传统方式的编程比赛。
测试赛：14th Feb, 6pm - 8pm IST (GMT +5:30).
正式比赛：15th Feb, 2pm - 10pm IST (GMT +5:30).

http://felicity.iiit.ac.in/~math/
MathematiKa，已经举办过一年了，这是第二年的比赛。比赛共12道数学题，你只需要提交答案即可。例如，去年的第四题叫你计算前30个正整数x使得F(x) = 5x^2 + 14x + 1是一个完全平方数。提交时，把所有30个数从小到大连接在一起即可。最大的那个x有十几位，因此这题硬算是不行的。
测试赛：12th Feb, 6pm - 9pm IST (GMT +5:30).
正式比赛：13th Feb, 2pm - 10pm IST (GMT +5:30)

查看更多 »

    在网上闲逛时发现了这么一个有趣的网站。Code Golf是一个另类的编程挑战网站。这个网站定期发布一个编程题目，你所提交的代码越短越好（keystroke越少越好，就像Golf一样要求尽可能少的stroke）。目前网站支持Perl、PHP、Python和Ruby语言。