2009年7月21日，百度之星Astar2009程序设计大赛现场总决赛在北京开展，50强在现场进行了激烈的“打斗”。百度爱好者（Baiduer.com.cn）给大家带了总决赛题目，供有兴趣的朋友研究。总决赛共两题，分别是Spider和限制性图灵测试。现场总决赛今年采用的比赛的形式是以spider题选出前15名，作为后面的图灵题（被称为复活赛题）的程序员，剩下35名作图灵题（被称为复活赛题）题的测试者。百度之星程序设计大赛，由百度公司发起创办于2005年。
1、Spider
Spider是百度用来抓取网页的程序的名字。面对信息几乎无穷无尽的互联网， 如何快速，有效的抓取到优质的网页是一个艰巨的任务。
在本次任务中，我们以站点为单位，你的任务就是设计一个特殊的Spider，这个Spider以站点为单位进行抓取，目标就是在有限的抓取次数下抓到尽量多的优质站点。
你的Spider所处的具体环境描述如下：
假设互联网上有n个站点，编号从 0n-1，注意，编号是纯随机的。你有m次的抓取机会，一次抓取一个站点，抓取完成后，你将被告知该站点是否是高质量站点（GOOD/BAD），并且告诉你该站点指出去的所有站点的ID，站点A指向B当且仅当A站点上某个页面里面包含有“指向B站点某个页面”的链接。
下面是一个样例程序：
#include “spider.h” // 所需函数的声明
//#include // 不要输出任何东西， 否则得0分
int rand_long（） {
return abs（（rand（）< <16）+rand（））;
}
int main（） {
int n,m;
spider_init（n,m）; // n:站点数， m:你能抓取的最大次数
vector crawled（n,false）;
while （1） {
int k=rand_long（）%n;
if （crawled[k]） continue;
vector link_out;
// 所有站点k指出去的站点都在link_out中
int ret = spider_crawl（k, link_out）;
// <0表示你的抓取行为非法（如id<0）或者已经到达最大抓取次数
// =0 表示站点k为BAD, =1表示GOOD
if （ret<0）
break;
/* 调试代码
string t=spider_get_name_by_id（k）; //该函数在系统测试时不可用
if （t!=”"）
printf（”%s\n”，t.c_str（））;
*/
}
// 抓取完毕， 系统计分
spider_done（）;
}
运行时间限制为3分钟（最终测试数据）, 赛时评测的时限为30秒（数据量较小）。
实际使用的测试数据约有千万级别的站点， 样例数据是随机抽取出来的300万个站点的的链接子图， 并且同一个站点的ID号与实际测试数据是不一样的。
评分方式
设站点总数为n， 则最多允许抓取m=n/8次， 假设当程序分别进行了m/8，m/4，m/2，m次抓取后抓到的GOOD站点数分别为 g1，g2，g3，g4，则最终的得分为g1*8+g2*4+g3*2+g4， 重复抓取的只计一次。
选手可随时提交代码， 并选择代码进行测试（数据规模小于实际数据但大于提供给选手的样例数据）， 但测试的次数限制为每个选手最多8次。 在本机选手可任意使用样例数据进行测试。 选手的最终得分依据最后一次提交在最终测试数据集上测试所得的分数。
注意：DON’T CHEAT。（例如对文件系统进行读写或HACK， 以及其它明显违反比赛公平性的行为），
我们会人工检查前几名选手的代码。另外，测试时使用的数据格式和处理方式和提供的样例是不一样的。实际测试时程序流程如下：
初始化，把需要的数据全部load进内存（<10秒）
每个函数调用使用的时间与返回的数据量成正比。 并且全部是内存操作
时空限制
选手内存限制使用500MB（不包括系统使用的内存）
背景知识
一般来说，互联网上的链接代表一种”推荐”的关系，如果A发出一条链接指向B，则可以认为A在某种程度上推荐了B. 但是由于作弊者的存在，使得实际的情况远比单纯的推荐来得复杂，作弊者经常制造大量的所谓的link farm，即一堆BAD的结点相互链接在一起。 有一个直观的简单想法认为，一个GOOD的结点一般指向GOOD的结点，而一个BAD的结点既有可能指向GOOD也有可能指向BAD，被很多GOOD指向的结点很有可能是VERY GOOD的，然而，实际的情况仍然要比这种观点复杂得多。
2、限制性图灵测试：搜索引擎的非法用户检测
用户使用百度时会发生以下行为：
查询一个Query，记为 QI，其中I是0…99的整数
点击一条搜索结果，记为 CI，其中I是1…10的整数
点击”下一页”链接进行翻页，记为 N
点击”相关检索”中的结果，记为 R
例如用户查询了一个Query “美女”，点了1,2,3,10条结果，然后翻页，然后再点了3,4条结果，然后点了相关检索 “帅哥”，然后
又点了1,2,3条结果，然后离开了。这个用户的行为可以表示如下：
Q1 C1 C2 C3 C10 N C3 C4 R C1 C2 C3
由于各种各样的原因，并不是每个用户都是人在做这个动作序列的，例如有些人会写程序会在百度上做以下事情： 检索 “sex”，翻页，翻页，点第3条结果，如此不断重复。这个怪异的”用户”的行为可以表示如下：
Q1 N N C3 Q1 N N C3 Q1 N N C3 Q1 N N C3 Q1 N N C3
当你面对着数亿的正常用户和不计其数的“机器人”时，你会怎么做呢？
如果你是程序员
给出搜索引擎一个用户行为序列，这个序列是在较短时间（如分钟级）内完成的，你的任务是写一个程序，判断其是否是正常的用户行为。如果是，输出yes,否则输出no
输入样例
Q1 C2 Q1 C2 Q1 C2 Q1 C2 Q1 C2 Q1 C2
Q1 C1 Q2 C2 Q3 C3
输出样例
no
yes
如果你是测试者
你的任务是给出一系列的测试数据（最多20组），每一行的格式如下：
answer behavior_sequence # comment
其中answer是yes或no，behavior_sequence 是用户行为序列片断，不超过64个元素，每个元素格式如题目开头所述，必须是 QI，CI，N，R 中的一个。comment是诠释，可选。例如：
yes Q1 C1 Q2 C1 Q3 C1 # a normal user
no Q1 C1 Q1 C1 Q1 C1
注意 测试者给的answer只是参考答案，请诚实给出，我们会对所有的答案进行检查并进行必要修正，如果有明显非诚实的行为，将取消该测试者的所有测试数据。测试者提供的测试数据中，要求参考答案为yes和no的数据数目一样多。请所有测试者在30分钟内提交4组测试数据，这4组数据将作为测试者提交的前4组测试数据。我们会尽快把所有提交打包发送给15名程序员
计分方法
如果程序对测试数据输出的答案和测试者提供的答案一样，令15名程序员中得到正确结果的个数为C，那么程序在此测试点得1/C分。如果程序对测试数据输出的答案和测试者提供的答案不一样，测试者得1/R分，其中R为该选手的本场比赛排名。总分为所有测试数据的得分和。