TLE比赛结束 经典题目回顾

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

一道叫做Compile Error(http://felicity.iiit.ac.in/tle/judge/CLASS.html)的题目要求你写一个叫做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(http://en.wikipedia.org/wiki/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);
}

另一个牛题目是Print ‘D Penguin(http://felicity.iiit.ac.in/tle/judge/PENGUIN.html)，要求你写一个打印企鹅ASCII Art的程序，程序的输出结果必须和这个文件(http://felicity.iiit.ac.in/tle/Penguin.txt)一模一样，代码越短越好。最牛的代码有点让人摸不着头脑：

main(i,z,n){for(;z="_���?��T���G�T��J��T��N�T��P�T�Qp�T�:�?�@�T��9��<��?T��9�8č;�9č?T��9�:�;�;��>T��9��9�;�Č9��?T�9��9�Ď?T�9�����?T��8�����@�T��9�먎AT��9�稐�A�T��9��㨓�A�T��;��@�T��;��@�T��<�A�T��<ਥB�T��=�ĖĒ���B��T��>���⩗��C�T�=���CT��;ਗ�C�T��<���CT�;ਧ��CT�;�ġ�C�T���=���C�T�?���D�T�?���D�T���=����C�T���Č9�ħ���D�T��Ĩ9�ė���B��T���Ĩ;ħ�?���T��Ĩ<��Ĩ�9Ĩ��T��Ĩ;�Ģ�ĩ�T���Ĩ9ਠĨ��T��Ĩ9����T���Č9���;��T��Ĩ:œ��>��T���N��T���N��T����=��A���T����騣���T"[i++]&255;)for(n=z%28;putchar(" `xnX '.:_"[z/28]),n--;);}

这个代码实质上是将整个图片压缩为了一个字符串。由于图片中连续字符出奇的多，我们便想到把“n个字符c”编码为一个字节。字符串的每一个字节取值都是0到255，而图片中只有10种字符（用0到9编号），因此一个字节最多可以表示出255/9=28个连续的相同字符。对于每一个0到255的数，令字符c等于它除以28的商所对应的字符，令n等于它除以28的余数，然后程序打印出n个连续的字符c出来。例如，106=3*28+22，它就代表了22个连续的3号字符。一个麻烦问题是，9*28已经等于252了，因此你最多只能处理连续的三个9号字符。不过没关系，令9号字符为“_”就行了，这是该图片中出现次数最少的字符，而且每次它都是单独出现的。