百度之星2010程序设计大赛 复赛试题（上）

百度爱好者（Baiduer.com.cn）消息 2010年6月19日，2010百度之星大赛复赛展开。百度爱好者给大家带了复赛题目，供有兴趣的朋友研究。复赛共十题，上期五期。分别是A+B问题、i-Doctor、url规范化、并行修复、猜猜你在哪儿。

1.A+B问题（时限：5000ms）

问题描述

Suzumiya最近开始无端刁难她的同学ViVo，总是莫名其妙的问他一些简单而又离谱、没有实际意义的数 学问题，比如三千加上五百等于多少。回答一次两次还可以，但不断这样的纠缠致使ViVo已经无法忍受了。所以ViVo决定制作一个语音装置来自动回答 Suzumiya提出的无聊问题。

ViVo知道你是个伟大的算法艺术家，所以希望该装置核心的数学计算模块你能够来帮忙。装置接收到的语音会自 动为你转化为对应的中文字符串，经过你的模块处理完成后输出中文字符串，传递给装置来朗读出来。

为了给你带来方便，ViVo已经提前收集好了Suzumiya可能会问到的问题，发现这些问题中大部分是数学 加法，也还有一些不是加法的问题，但答案依然都可以用数字来表示。

输入格式

输入的第一行是一个数字n，表示接下来有n个问题，每个问题占一 行。

提示：最终评测时所用的输入数据可以在这里(windows)和这里(linux)下载。

输出格式

每行包含一个没有语病的中文表示最终的结果。

样例输入

2

一加一等于几？

三千加上五百等于多少？

样例输出

二

三千五百

提示

请注意：不要提交你的输出文件，而应当像其他题目一样，提交你的源代码。本题的最终得分计算如下：

假设输入除第一行数字n外有n个非空行，你的输出必须也恰好包含n个非空行，否则本题得 0分。

从前向后一一比较，如果你的输出有m行和标准答案一致，你将得到本题的100*(m/n)³%。换句话说，如果你的程序有 70%的行和标准答案一致，你将得到本题约34.3%的分数。

2.i-Doctor（时限：3000ms）

问题描述

百度计划开发一个在线的健康专家系统，帮助用户足不出户就能初步了解自己所患的疾病，并以此向用户推荐适合的 医院就诊。经过对海量数据的分析，百度提取出了若干表征疾病性状的特征，并把每种疾病是否符合某项特征都进行了标记，最终得到如下数据表格：

其中，D₀,D₁,…,D_m-1表 示疾病名称，A₀,A₁,…, A_n-1表示疾病的特征。m、n均为正整数且m < 4096，n < 128。特征的取值为Yes（符合该项特征）， Probably（有可能符合该项特征）或No（不符合该项特征）。

这个专家系统被命名为i-Doctor，因为它的工作方式很人性化，就像医院的专家一样通过与病人的一问一答 来得出诊断。每当开始一个诊断时，i-Doctor首先提问：”你是否感觉到有A症状？” 其中，A为一疾病特征。用户依据自己的感觉回答。 不幸的是，有时候病人对自己是否有A症状不能肯定，甚至会给出错误的回答。统计表明，病人的回答及置信度如下：

注意：每个病人在诊断之前患有一种（且仅一种）确定的疾病，且该疾病保证存在于上述疾病数据库中。

现在，请你编写一个程序来让i-Doctor开始工作。

交互

你的程序应当读写标准输入输出，以便与测试库交互。交互方式如下：

首先，你的程序（doctor）应从标准输入读取疾病特征表。第一行是两个正整数m和n，表示疾病的种类数和特征的种类数。m和n之间以一个空格 隔开。接下来共有m行，其中每一行描述一种疾病，格式为：

疾病名称 特征值0 特征值1 … 特征值n-1

开头的字符串为疾病名称，长度不超过7字节；一个空格之后依次是各特征值，取值为英文字母Y或N或P，分别表示Yes、No和Probably。相邻特征 值以一个空格隔开。

接下来，你的程序可以向病人（patient）提问，提问方式为在标准输出上打印一行，格式为：Do you feel Ai? 其中Ai表示特征特i。 此后，你的程序应当从标准输入读取病人的回答。病人每次的回答也为一行，内容为Yes、Probably yes、Probably no、No和Don’t know之一。

如此一问一答，直到你的程序诊断出病人所患疾病，此时应在标准输出上打印一行：I think of Dj! 其中Dj为此疾病名称

如果无法确诊，你的程序可以在标准输出上打印一行：Give up. 表示你放弃诊断该病人。注意：很快你将看到，放弃诊断总比错误的诊断要好。

在确诊或放弃后，你的程序应自行终止。

可以在这里 (windows)和这里 (linux)下载测试库（内附使用说明）。

程序举例

下面是一个示例程序（省略了include），它能正确的与测试库进行交互，尽管它的得分可能不高：

int main()

{

int m, n;

char name[10], line[256];

char table[4096][128][2];

int i, j, q;

srand(time(0));

scanf(“%d %d\n”, &m, &n);

for(i = 0; i < m; i++)

{

scanf(“%s”, name);

for(j = 0; j < n; j++)

scanf(“%s”, table[i][j]);

fgetc(stdin); /* consume ‘\n’ */

}

for(q = 0; q < 4; q++)

{

printf(“Do you feel A%d?\n”, rand() % n);

fflush(stdout); /* Important */

fgets(line, sizeof(line), stdin);

}

if(rand() % 3 == 0)

printf(“I think of D%d!\n”, rand() % m);

else

printf(“Give up.\n”);

fflush(stdout); /* Important */

return 0;

}

注意，你的程序应当像上面的程序一样，在每次输出后立即执行 fflush(stdout)语句，使输出的内容立即被送入测试库（而不是留在输出缓冲区中）。另外，你的程序应能独立编译，不能依赖于任何其他外部文件 （包括测试库）。

评分方法

本题一共有25个测试点，每个测试点分值相同。每个测试点对应一个病人，如果你诊断错误或者放弃诊断，则得分 为0。如果你成功诊断，你的得分取决于你询问的次数和其他选手成功诊断该病人所用的询问次数。当然，次数越少得分越高。注意：所有测试点的得分相加后，还 要扣除错误诊断的惩罚。具体来说，每次错误的诊断将扣掉两个测试点的满分（哪怕你没有任何测试点得到了满分）。如果扣除惩罚后，所得的分数为负，总分将调 整为0。

3.url规范化 (时限：5000ms )

问题描述

互联网上很多不同url都是指向同一页面的，比如：

http://tieba.baidu.com/f?kw=%C9%CF%BA%A3%CA%C0%B2%A9%BB%E1

http://tieba.baidu.com/f?kw=%C9%CF%BA%A3%CA%C0%B2%A9%BB%E1&fr=tb0_search

http://tieba.baidu.com/f?kw=%C9%CF%BA%A3%CA%C0%B2%A9%BB%E1&fr=tb0_search&ie=utf-8

都指向的是同一页面：http://tieba.baidu.com/f?kw=%C9%CF%BA%A3%CA%C0%B2%A9%BB%E1。

我们需要把不同形式的url规范化，用统一的url代替。目前已经定义了一批规范化规则，你的任务是把一些待处理的url按规则替 换成新的url。

每条规则都是一个字符串。为了方便理解，我们定义如下术语：

通配符：字符’#'或者’*'，以及紧跟其后的长度限定符（可选）。其中’#'匹配数字，’*'匹配任意字 符。

长度限定符：紧跟通配符后，格式为[min-max]，表示该通配符匹配的字符个数的最小值和最大值，其中 min和max均可以省略（但不能同时省略），当min=max时可以简写为[min]。’#'的默认最小长度为1，’*'为0。二者的默认最大长度均为 无穷大。例如，”#[3]“表示3个连续数字，’*[3-9]‘表示3到9个任意字符，’*[-8]‘表示0-8个任意字符，’#[7-]‘表示至少七个 连续数字。注意，当通配符的后一个字符为左方括号’['时，它总是应当被看作长度限定符的开始标志。

尖括号：成对的小于符号"<"和大于符号">"。尖括号总是两两配对，不存在无法配对的孤立尖括 号，且尖括号内部不会出现通配符，也不会嵌套另一对尖括号。

规则片段：在处理规则之前，我们把规则分成若干个连续的片段，每个片段是单个通配符（以及紧随其后的长度限定 符，如果有的话）、一对尖括号（以及括号内的字符，如果有的话），或者若干个连续的普通字符（不含通配符和尖括号）。为了避免歧义，规则应当被划分成最少 的片段。不难证明，此时的划分方法是惟一的。

例如，规则"abc*d#[4-7]eeef<gh>i”包含7个规则片段：abc、*、d、#[4-7]、 eeef、<gh>、i。

用某一条规则处理url时，我们遵循以下步骤：

第一步：匹配。首先，忽略含有尖括号的规则片段，用其他片段来匹配url，使得每个片段所匹配的字符串从左到右 连接之后和该url完全相等。注意，连接顺序必须按照规则片段的顺序从左到右进行。根据定义，由普通字符组成的片段只能匹配和它完全相同的字符串，而通配 符可以匹配多样化的字符串，规则如前所述。例如，abc<x>def*[3-5]ghi在忽略尖括号后得到四个片段：abc、def、* [3-5]、ghi，因此，abc<x>def*[3-5]ghi能匹配到的url是那些以abcdef开头，ghi结尾，中间有3到5个字 符的字符串。

如果无法匹配，说明该规则不适用于此url，处理结束；但有时会出现匹配方式不止一种的情况，还需要消除歧义。 例如*bc<d>*<xyz>匹配abcabca的方法有两种：

在本题中，如果出现像这样匹配方法不惟一的情况，你应当选择让从左到右第一个通配符匹配字符数最少的方案。如果还有多种方案，再选择其中让第二个通 配符匹配字符串最少的方案，以此类推。 在上面的例子中，应选择第一种方案。

第二步：替换。对于每对尖括号，把它左边相邻的url片段替换为尖括号内的 文本，然后连接所有url片段（输入数据保证规则不以左尖括号开头，并且相邻两对尖括号之间至少包含一个字符）。我们仍然借助上例说明问题：

也就是说，”abcabca”被规则”*bc<d>*<xyz>”处理后变成了”adxyz”。

再举一个实际的例子：*/viewthread.php?tid=#&<>*<> 表示将url文件名为viewthread.php，第一个参数名为tid且参数值为数字时，把其它参数删除。 换句话说，这条规则将把 www.baidu.com/dir/viewthread.php?tid=123&arg=aa 替换为 www.baidu.com/dir/viewthread.php?tid=123。

输入格式

第一行为一个正整数M，说明共有M条规则。第二行为一个正整数N，说明共有N条url。接下来M行，每行代表一条规则，不超过256个字符。 再接下来N行，每行代表一条url。所有URL都去掉了 http:// 头，且不含#*<>四种特殊字符，也不超过256个字符。M<=1000，N<=10000，输入的url和规则均不含汉字。

输出格式

输出共N行。对每一行输入的url，按照输入顺序依次考虑所有规则，直到某个规则修改url时输出替换后的新 url（如果匹配成功，但修改前后url并没有发生变化，不算修改，应继续尝试剩下的规则），然后忽略剩下的规则。如果没有匹配的规则，则把输入的url 按照原样重新输出。

样例输入

5

7

blog.sina.com.cn/s/blog_*.html*~type=<>*<>

you.video.sina.com.cn/*[0]falsepage/<>#<>.html<>

club.*<club>.sina.com.cn/*[1]*

www.sitea.com.cn:#[2-4]<80>/*

blog.sina.com.cn/s/circleinfo_<blog.sina.com.cn/>*<>.html<>

blog.sina.com.cn/s/blog_4ab97cd40100hwx9.html?t=j1~type=v5_one&label=rela_prevarticle

you.video.sina.com.cn/falsepage/123456789.html

club.edu.sina.com.cn/index.html

www.163.com/

blog.sina.com.cn/s/circleinfo_4859f1fa010004zx_1.html

www.sitea.com.cn:8080/a/index.asp

www.baidu.com/

样例输出

blog.sina.com.cn/s/blog_4ab97cd40100hwx9.html?t=j1

you.video.sina.com.cn/

club.club.sina.com.cn/index.html

www.163.com/

blog.sina.com.cn/

www.sitea.com.cn:80/a/index.asp

www.baidu.com/

评分方法

本题按测试点评分，每个测试点的得分计算方法如下：

假设输入有n条url，你的输出必须也恰好包含n行，否则本题得0分。

从前向后一一比较，如果你的输出有m行和标准答案一致，你将得到本题的100*(m/n)³%。换句话说，如果你的程序有 70%的行和标准答案一致，你将得到本题约34.3%的分数。

50%的数据保证N<=100，90%的数据保证N<=1000。

4.并行修复 ( 时限：5000ms )

问题描述

百度的网页按照某种标准均匀划分为N组，每组数据编号为0到N-1的整数。一组网页可以全部存入一个数据库 中。 为了保证数据的可靠性，每一组网页按X份镜像存储，互为备份，且任两份镜像不会分布在同一台主机上。 当有F台机器因故障而失效时，部分网页组对应的镜像数目可能会低于X份，此时需要复制镜像，使系统重新恢复到每组网页均有X份镜像的状态。

假设系统中一共有M台主机，主机编号从0到M-1。每台主机的性能和网络带宽均相同。一台主机最多可以存储T 个大小相同的数据库。每台主机任意时刻最多允许C个并发网络连接。一次复制操作占用源主机和目标主机各一个网络连接，源主机和目标主机不允许相同。若一对 源主机和目标主机在同一时刻进行多次(B > 1)复制操作，则占用源主机和目标主机各B个网络连接。记一份镜像的一次复制用时为1单位。假定每次复制的启动时间点必须为非负整数，请设计一种修复算 法，对于给定的某种镜像分布状态和失效的主机编号集合，输出一种恢复方案，使数据恢复的总用时尽可能短。输入集合保证系统能够从故障中恢复。

下图中给出了当N=4，X=3，M=6，T=6，C=1时，0号主机故障时的一种恢复方案，箭头表示复制的方 向，箭头盘旁的数字代表该次复制的启动时间点。

输入格式

输入包含N+2行。第一行包含五个正整数N，X，M，T，C，接下来的N行依次表示第0到N-1组网页的镜像 分布状态，每行有X列整数，为该组网页的镜像所在的主机编号。 最后一行由F个整数组成，表示故障主机的编号（注意：F本身不在输入中出现，你需要统计最后一行的整数个数，以获取F的值）。 N<=40000，2<=X<=8，2<=M<=4000，T<=600，C<=4，F<=10。

输出格式

输出一个数据恢复方案。方案包含若干行，每行代表一次镜像复制操作，由四个整数W, S, D, T组成。W代表网页组编号，S为源镜像所在主机编号，D为目标镜像所在主机编号，T为复制的启动时间点（起始时间为0）。各复制操作应按照T从小到大排 序。

样例输入

4 3 6 6 1

0 2 3

0 1 4

0 2 3

1 2 3

0

样例输出

0 3 4 0

2 2 5 0

1 1 2 1

样例说明

该方案用了2单位时间（耗时最多的主机编号为2）。

评分方法

本题采用相对评分。对于每个测试点，你的最终得分取决于你输出的方案和其他选手输出的方案的相对优劣程度。

5.猜猜你在哪儿 ( 时限：1000ms )

问题描述

有一个半径为1米的圆，圆心位于(0,0)点。你和圆处在同一平面上，准备和这个圆一起玩游戏。这个圆每过一 分钟会随机移动一次，一共移动t次。 圆有一个移动距离限制参数s，每次圆心从(x1,y1)移动到(x2,y2)时总是满足：|x1-x2|<=s, |y1-y2|<=s。

每次圆移动完成后，你可以依次询问k个点是否在圆内，然后任意走到一个新的位置，结束这个 回合。你的目标是尽量让自己位于圆内，并且离圆心越近越好。 每个回合结束后, 若你在圆的边界上或者圆外, 得0分; 若在圆内, 得分为(1-你到圆心的距离/圆的半径)。所有t个回合结束后，每个回合的平均得分就是你对于该测试点的原始得分。

交互

你的程序应当读写标准输入输出，以便与测试库交互。交互方式如下：

首先，你的程序应从标准输入读入三个数t, s, k，分别表示总回合数、圆心移动的距离限制，以及每回合你可以询问的点数。1<=t<=100, 0 < s < 1, 1<=k<=10。

接下来，你应当分k行给出各个询问点的坐标——每行两个数x和y，即询问坐标为(x,y)的点。每次询问一个点之后，你的程序应当从标准输入读入 一个数a，1表示询问点在圆上或者圆的边界上，0表示在圆外。

再接下来，你的程序应当往标准输出写两个数x和y，表示你要走到的新位置的坐标。

完成所有t个回合之后，你的程序应当自行退出，否则将按超时处理。

可以在这 里(windows)和这里 (linux)下载测试库（内附使用说明）。

程序举例

下面是一个示例程序（省略了include），它能正确的与测试库进行交互，尽管它的得分可能不高：

int main()

{

int t, k;

float s;

scanf(“%d%f%d”, &t, &s, &k);

for(int i = 0; i < t; i++)

{

for(int j = 0; j < k; j++)

{

int ans = 0;

printf(“0.%d 0.%d\n”, rand(), rand());

fflush(stdout);

scanf(“%d”, &ans); // 1表示仍然在圆里或圆的边界上，0表示在圆外

}

printf(“0.%d 0.%d\n”, rand(), rand());

}

}

注意，你的程序应当像上面的程序一样，在每次读取新的输入之前调用 fflush(stdout)，以确保这之前输出的内容立即被送入测试库（而不是留在输出缓冲区中）。另外，你的程序应能独立编译，不能依赖于任何其他外 部文件（包括测试库）。

评分方法

本题采用相对评分。对于每个测试点，你的最终得分取决于你的原始得分和其他选手的原始得分的相对优劣程度。

百度之星2010程序设计大赛 复赛试题（下）>>