TLE比赛结束 经典题目回顾

    创意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);
}


    另一个牛题目是Print ‘D Penguin,要求你写一个打印企鹅ASCII Art的程序,程序的输出结果必须和这个文件一模一样,代码越短越好。最牛的代码有点让人摸不着头脑:

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号字符为“_”就行了,这是该图片中出现次数最少的字符,而且每次它都是单独出现的。

16 条评论

发表评论

  ×  7  =  28