百度之星赛题

2005年百度之星程序设计大赛试题初赛题目

第一题（共四题 100 分）：连续正整数（ 10 分）

题目描述：一个正整数有可能可以被表示为 n(n>=2) 个连续正整数之和，如：

15=1+2+3+4+5
15=4+5+6
15=7+8

请编写程序，根据输入的任何一个正整数，找出符合这种要求的所有连续正整数序列。

输入数据：一个正整数，以命令行参数的形式提供给程序。

输出数据：在标准输出上打印出符合题目描述的全部正整数序列，每行一个序列，每个序列都从该序列的最小正整数开始、以从小到大的顺序打印。如果结果 有多个序列，按各序列的最小正整数的大小从小到大打印各序列。此外，序列不允许重复，序列内的整数用一个空格分隔。如果没有符合要求的序列，输出 “NONE” 。

例如，对于 15 ，其输出结果是：
1 2 3 4 5
4 5 6
7 8
对于 16 ，其输出结果是：
NONE

评分标准：程序输出结果是否正确。

百度之星程序设计大赛试题 -2

第二题（共四题 100 分）：重叠区间大小（ 20 分）

题目描述：请编写程序，找出下面 “ 输入数据及格式 ” 中所描述的输入数据文件中最大重叠区间的大小。

对一个正整数 n ，如果 n 在数据文件中某行的两个正整数（假设为 A 和 B ）之间，即 A<=n<=B 或 A>=n>=B ，则 n 属于该行；如果 n 同时属于行 i 和 j ，则 i 和 j 有重叠区间；重叠区间的大小是同时属于行 i 和 j 的整数个数。
例如，行（ 10 20 ）和（ 12 25 ）的重叠区间为 [12 20] ，其大小为 9 ；行（ 20 10 ）和（ 12 18 ）的重叠区间为 [10 12] ，其大小为 3 ；行 (20 10) 和（ 20 30 ）的重叠区间大小为 1 。

输入数据：程序读入已被命名为 input.txt 的输入数据文本文件，该文件的行数在 1 到 1,000,000 之间，每行有用一个空格分隔的 2 个正整数，这 2 个正整数的大小次序随机，每个数都在 1 和 2^32-1 之间。（为便于调试，您可下载测试 input.txt 文件，实际运行时我们会使用不同内容的输入文件。）

输出数据：在标准输出上打印出输入数据文件中最大重叠区间的大小，如果所有行都没有重叠区间，则输出 0 。

评分标准：程序输出结果必须正确，内存使用必须不超过 256MB ，程序的执行时间越快越好。

百度之星程序设计大赛试题 -3

第三题（共四题 100 分）：字符串替换（ 30 分）

题目描述：请编写程序，根据指定的对应关系，把一个文本中的字符串替换成另外的字符串。

输入数据：程序读入已被命名为 text.txt 和 dict.txt 的两个输入数据文本文件， text.txt 为一个包含大量字符串（含中文）的文本，以 whitespace 为分隔符； dict.txt 为表示字符串（ s1 ）与字符串（ s2 ）的对应关系的另一个文本（含中文），大约在 1 万行左右，每行两个字符串（即 s1 和 s2 ），用一个 \t 或空格分隔。 dict.txt 中各行的 s1 没有排序，并有可能有重复，这时以最后出现的那次 s1 所对应的 s2 为准。 text.txt 和 dict.txt 中的每个字符串都可能包含除 whitespace 之外的任何字符。 text.txt 中的字符串必须和 dict.txt 中的某 s1 完全匹配才能被替换。（为便于调试，您可下载测试 text.txt 和 dict.txt 文件，实际运行时我们会使用不同内容的输入文件。）

输出数据：在标准输出上打印 text.txt 被 dict.txt 替换后了的整个文本。

评分标准：程序输出结果必须正确，内存使用越少越好，程序的执行时间越快越好。

第四题（共四题 100 分）：低频词过滤（ 40 分）

题目描述：请编写程序，从包含大量单词的文本中删除出现次数最少的单词。如果有多
个单词都出现最少的次数，则将这些单词都删除。

输入数据：程序读入已被命名为 corpus.txt 的一个大数据量的文本文件，该文件包含英
文单词和中文单词，词与词之间以一个或多个 whitespace 分隔。（为便于调试，您可下载
测试 corpus.txt 文件，实际运行时我们会使用不同内容的输入文件。）

输出数据：在标准输出上打印删除了 corpus.txt 中出现次数最少的单词之后的文本（
词与词保持原来的顺序，仍以空格分隔）。

2006年百度之星程序设计大赛试题初赛题目

2006 年百度之星程序设计大赛初赛题目 1

饭团的烦恼

“午餐饭团“是百度内部参与人数最多的民间组织。

同一个部门的，同一间大学的，同一年出生的，用同一种型号电脑的，员工们总是以各种理由，各种借口组织各种长久的，临时的饭团。

参加饭团，不仅可以以优惠的价格尝到更加丰富的菜式，还可以在吃饭的时候和同事们唠唠嗑，吹吹水，增进感情。

但是，随着百度的员工越来越多，各个饭团的管理随即变得烦杂。特别是为了照顾员工们越来越挑剔的胃口，饭团的点菜负责人背负的责任越来越大。现在，这个重担落在百度之星的肩上，因为，你们将要为所有的百度饭团设计一个自动点菜的算法。

饭团点菜的需求如下：

1 ． 经济是我们要考虑的一个因素，既要充分利用百度员工的午餐补助，又不能铺张浪费。因此，我们希望最后的人均费用越接近 12 元越好。

2 ． 菜式丰富是我们要考虑的另一个因素。为简单起见，我们将各种菜肴的属性归结为荤菜，素菜，辛辣，清淡，并且每个菜只能点一次。

3 ． 请紧记，百度饭团在各大餐馆享受 8 折优惠。

输入数据描述如下：

第一行包含三个整数 N ， M ， K （ 0<N<=16 ， 0<M<=N ， 0<K<=12 ），分别表示菜单上菜的数目，饭团需要点的菜的数目，就餐的人数。

紧接着 N 行，每行的格式如下：

菜名（长度不超过 20 个字符） 价格（原价，整数） 是否荤菜（ 1 表示是， 0 表示否） 是否辛辣（ 1 表示是， 0 表示否）

例：

水煮鱼 30 1 1

紧接着是 a b c d 四个整数，分别表示需要点的荤菜，素菜，辛辣，清淡菜的数目。

输出数据：

对于每一测试数据，输出数据包含 M+1 行，前 M 行每行包含一个菜名（按菜名在原菜单的顺序排序）。第 M+1 行是人均消费，结果保留两位小数。

说明：

1 ．结果菜单的数目应该恰好为 M ，荤菜，素菜，辛辣，清淡菜的数目恰好为 a ， b ， c ， d 。在满足这样的前提下，选择人均消费最接近 12 元的点菜方案。题目数据保证有且仅有一个解。

2 ．每组测试数据的结果用一个空行隔开。末尾不要有多余的空行。

输入样例

3 2 2

水煮鱼 30 1 1

口水鸡 18 1 1

清炖豆腐 12 0 0

1 1 1 1

输出样例

口水鸡

清炖豆腐

12.00

时间要求： 1S 之内

 

2006 年百度之星程序设计大赛初赛题目 2

题目名称：蝈蝈式的记分

内容描述：

蝈蝈小朋友刚刚学会了 0-9 这十个数字 , 也跟爸爸妈妈来参加百度每周进行的羽毛球活动。但是他还没有球拍高，于是大人们叫他记录分数。聪明的蝈蝈发现只要记录连续得分的情况就可以了，比如用“ 3 2 4 ” 可以表示一方在这一局中连得三分后，输了两分，接着又连得到四分。可是，后来大人们发现蝈蝈只会用 0-9 这十个数字，所以当比赛选手得分超过 9 的时候，他会用一个 X 来表示 10 完成记分。但问题是，当记录为“ X 3 5 ” 的时候，蝈蝈自己也记不起来是一方连续得到十三分后，再输五分；还是先赢十分输三分再赢五分。

因为百度内部就要开始进行羽毛球联赛了，要先摸清大家的实力才好分组比赛呢～于是，大人们想知道以前每局的比分是怎样的，以及谁获得了胜利。要是遇到了根据比赛记录无法确认比赛进程的情况，也要输出相应的提示哦。

需要帮蝈蝈进一步说明的是，比赛是五局三胜的，每局先获得二十一分的为胜，但是胜方必须领先对手两分或以上，否则必须继续比赛直到一方超出对手两分 为止，比分多的一方获胜。任何一方先获得三局的胜利后就获得胜利，比赛也相应的结束。而且蝈蝈保证是完整的无多余信息的记录了比赛。

输入数据：

以 point.in 为输入文件，文件中首行只有一个整数 M ，表示蝈蝈记录了多少场比赛的分数。每场比赛用两行记录，第一行是一个整数 N(N<=1000) 表示当前这个记录中有多少个字符，第二行就是具体的 N 个字符表示记录的分数。

输出数据：

相应的内容将输出到 point.out 文件中，对应每一个分数记录，输出相应的每局分数，每局分数都使用两个整数表示，表示两个选手的得分，中间用 ":" 分隔开；每组分数记录间使用一个空行分隔开。如果相应的比赛结果无法预测的时候，以” Unknown “一个单词独占一行表示。

??输入和输出结果数据样例：

Sample Input ：

3

23

9 7 3 6 2 4 7 8 3 2 7 9 X 2 2 1 2 1 X 1 X 1 1

25

9 3 8 5 4 8 3 9 8 4 X X X X 2 X X X X 2 8 4 9 2 4

43

7 7 7 7 7 3 4 5 6 7 6 5 4 2 1 3 5 7 9 7 5 3 1 3 0 9 9 3 9 3 2 1 1 1 5 1 5 1 5 1 5 5 1

Sample Output ：

21:17

24:22

21:3

Unknown

21:14

20:22

21:23

21:16

21:9

 

2006 年百度之星程序设计大赛初赛题目 3

变态的比赛规则

为了促进各部门员工的交流，百度 (baidu) 举办了一场全公司范围内的 " 拳皇友谊赛 " ，负责组织这场比赛的是百度的超级 " 拳皇 " 迷 W.Z. W.Z 不想用传统的淘汰赛或者循环赛的方式，而是自己制定了一个比赛规则。

由于一些员工（比如同部门或者相临部门员工）平时接触的机会比较多，为了促进不同部门之间的交流， W.Z 希望员工自己组成不同组。不同组之间的每两个人都会进行一场友谊赛而同一组内的人则之间不会打任何比赛。

比如 4 个人，编号为 1--4, 如果分为两个组并且 1,2 一个组， 3 ， 4 一个组，那么一共需要打四场比赛： 1 vs 3,1 vs 4,2 vs 3,2 vs 4. 而如果是 1,2,3 一组， 4 单独一组，那么一共需要打三场比赛 : 1 vs 4,2 vs 4,3 vs 4.

很快 W.Z 意识到，这样的比赛规则可能会让比赛的场数非常多。 W.Z 想知道如果有 N 个人 , 通过上面这种比赛规则，总比赛场数有可能为 K 场吗？比如 3 个人，如果只分到一组则不需要比赛，如果分到两组则需要 2 场比赛 , 如果分为三组则需要 3 场比赛。但是无论怎么分都不可能只需要 1 场比赛。

相信作为编程高手的你一定知道该怎么回答这个问题了吧？ 那么现在请你帮助 W.Z 吧。

输入

每行为一组数据，包含两个数字 N, K 。 (0<N<=500, K>=0)

输出

对输入的 N,K 如果 N 个员工通过一定的分组方式可能会一共需要 K 场比赛，则输出 "YES", 否则输出 "NO", 每组数据占一行。

所有的输入输出均为标准输入输出。

例子

输入文件 :

2 0

2 1

3 1

3 2

输出 :

YES

YES

NO

YES

 

2006 年百度之星程序设计大赛初赛题目 4

2007-05-14 17:39

剪刀石头布

N 个小孩正在和你玩一种剪刀石头布游戏。 N 个小孩中有一个是裁判，其余小孩分成三组（不排除某些组没有任何成员的可能性），但是你不知道谁是裁判，也不知道小孩们的分组情况。然后，小孩们开始玩剪 刀石头布游戏，一共玩 M 次，每次任意选择两个小孩进行一轮，你会被告知结果，即两个小孩的胜负情况，然而你不会得知小孩具体出的是剪刀、石头还是布。已知各组的小孩分别只会出一 种手势（因而同一组的两个小孩总会是和局），而裁判则每次都会随便选择出一种手势，因此没有人会知道裁判到底会出什么。请你在 M 次剪刀石头布游戏结束后，猜猜谁是裁判。如果你能猜出谁是裁判，请说明最早在第几次游戏结束后你就能够确定谁是裁判。

输入格式：

输入文件包含多组测试数据。每组测试数据第一行为两个整数 N 和 M （ 1 ≤ N ≤ 500 ， 0 ≤ M ≤ 2000 ），分别为小孩的个数和剪刀石头布游戏进行的次数。接下来 M 行，每行两个整数且中间以一个符号隔开。两个整数分别为进行游戏的两个小孩各自的编号，为小于 N 的非负整数。符号的可能值为“ = ”、“ > ”和“ < ”，分别表示和局、第一个小孩胜和第二个小孩胜三种情况。

输出格式：

每组测试数据输出一行，若能猜出谁是裁判，则输出身为裁判的小孩的编号，并输出在第几次游戏结束后就能够确定谁是裁判。如果无法确定谁是裁判，或者发现剪刀石头布游戏的胜负情况不合理（即无论谁是裁判都会出现矛盾），则输出相应的信息。具体输出格式请参考输出样例。

输入样例：

3 3

0<1

1<2

2<0

3 5

0<1

0>1

1<2

1>2

0<2

4 4

0<1

0>1

2<3

2>3

1 0

输出样例：

Can not determine

Player 1 can be determined to be the judge after 4 lines

Impossible

Player 0 can be determined to be the judge after 0 lines

说明：

共有 5 个测试数据集，每个测试数据集为一个输入文件，包含多组测试数据。每个测试数据集从易到难分别为 5 、 10 、 15 、 30 和 40 分，对每个测试数据集分别执行一次程序，每次必须在运行时限 3 秒内结束程序并输出正确的答案才能得分。

所有数据均从标准输入设备（ stdin/cin ）读入，并写出到标准输出设备 （ stdout/cout ）中。

五个测试数据集中输入 N 分别不大于 20 、 50 、 100 、 200 和 500 ，各有 10 组测试数据。

 

2006 年百度之星程序设计大赛初赛题目 5

座位调整

题目描述：

百度办公区里到处摆放着各种各样的零食。百度人力资源部的调研发现，员工如果可以在自己喜欢的美食旁边工作，工作效率会大大提高。因此，百度决定进行一次员工座位的大调整。

调整的方法如下：

1 ． 首先将办公区按照各种零食的摆放分成 N 个不同的区域。（例如：可乐区，饼干区，牛奶区等等）。

2 ． 每个员工对不同的零食区域有不同的喜好程度（喜好程度度的范围为 1 — 100 的整数， 喜好程度越大表示该员工越希望被调整到相应的零食区域）。

3 ． 由于每个零食区域可以容纳的员工数量有限，人力资源部希望找到一个最优的调整方案令到总的喜好程度最大。

数据输入：

第一行包含两个整数 N ， M ，（ 1<=N ， M<=300 ）。分别表示 N 个区域和 M 个员工。

第二行是 N 个整数构成的数列 a ，其中 a[i] 表示第 i 个区域可以容纳的员工数， (1<=a[i]<=M ， a[1]+a[2]+..+a[N]=M) 。

紧接着是一个 M*N 的矩阵 P ， P （ i ， j ）表示第 i 个员工对第 j 个区域的喜好度。

答案输出：

对于每个测试数据，输出可以达到的最大的喜好程度。

输入样例：

3 3

1 1 1

100 50 25

100 50 25

100 50 25

输出样例：

175

数据解释：此数据只存在一种安排方法，三个员工分别安置在三个区域。最终的喜好程度为 100+50+25=175

 

2006 年百度之星程序设计大赛初赛题目 6

2007-05-14 17:42

百度语言翻译机

时限 1s

百度的工程师们是非常注重效率的，在长期的开发与测试过程中，他们逐渐创造了一套他们独特的缩率语。他们在平时的交谈，会议，甚至在各中技术文档中都会大量运用。

为了让新员工可以更快地适应百度的文化，更好地阅读公司的技术文档，人力资源部决定开发一套专用的翻译系统，把相关文档中的缩率语和专有名词翻译成日常语言。

输入数据：

输入数据包含三部分

1. 第一行包含一个整数 N （ N<=10000 ），表示总共有多少个缩率语的词条。

2. 紧接着有 N 行的输入，每行包含两个字符串，以空格隔开。第一个字符串为缩率语（仅包含大写英文字符，长度不超过 10 ），第二个字符串为日常语言（不包含空格，长度不超过 255 ） .

3. 从第 N+2 开始到输入结束为包含缩略语的相关文档。（总长度不超过 1000000 个字符）

输出数据：

输出将缩率语转换成日常语言的文档。（将缩率语转换成日常语言，其他字符保留原样）

输入例子：

6

PS 门户搜索部

NLP 自然语言处理

PM 产品市场部

HR 人力资源部

PMD 产品推广部

MD 市场发展部

百度的部门包括 PS ， PM ， HR ， PMD ， MD 等等，其中 PS 还包括 NLP 小组。

输出例子：

百度的部门包括门户搜索部，产品市场部，人力资源部，产品推广部，市场发展部等等，其中门户搜索部还包括自然语言处理小组。

注意：

1 ． 输入数据中是中英文混合的，中文采用 GBK 编码。

2 ． 为保证答案的唯一性，缩率语的转换采用正向最大匹配（从左到右为正方向）的原则。请注意输入例子中 PMD 的翻译。

2007年百度之星程序设计大赛试题初赛题目

百度的高级搜索方法 (2007 年初赛）

题面描述：

你尝试过在百度上使用 site inurl 语法查询吗 ? 如果还没有的话可以试一下 :)

如输入 site:www.baidu.com inurl:news

则会搜出所有在 www.baidu.com 站点上的包含 "news" 子串的 url 。

现在我们有两份数据，一份是 site_inurl.txt 一份是 url.txt

site_inurl.txt 中每行是一个 site inurl 语法组成的查询串， url.txt 中保存的是 url 列表。

你能否在 url 列表中找出所有能被 site_inurl.txt 中的查询串检索到的 url?

如 site_inurl.txt 内容如下：

site:www.baidu.com inurl:/more

site:zhidao.baidu.com inurl:/browse/

site:www.sina.com.cn inurl:www20041223am

url.txt 内容如下：

http://www.baidu.com/more/

http://www.baidu.com/guding/more.html

http://www.baidu.com/events/20060105/photomore.html

http://hi.baidu.com/browse/

http://hi.baidu.com/baidu/

http://www.sina.com.cn/head/www20021123am.shtml

http://www.sina.com.cn/head/www20041223am.shtml

则你的程序运行完输出的结果应该为：

http://www.baidu.com/more/

http://www.baidu.com/guding/more.html

http://www.sina.com.cn/head/www20041223am.shtml

程序以命令行形式传入这两个文件名，第一个参数为 site_inurl 文件对应的文件名，第二个参数为 url 列表对应的文件名，程序的输出请输出到标准输出。

 

Wii 游戏开始啦！（ 2007 年初赛）

题目描述

为了在紧张的上班时间让员工们轻松些，百度休息室里放置着按摩椅、 CD 、高尔夫套装和 Wii 游戏机等休闲用品。其中最受欢迎的当然是游戏机。

wii 游戏机每个手柄需要使用两节电池（这两个电池可以是不同的品牌）。工程师们在玩游戏时。如果手柄没有电，他们都是将其中没电的电池拿走，并换上一个全新的电池，有电的必须继续使用。

例如，已知三种电池的使用时间分别为 3 小时、 5 小时和 8 小时。一开始，工程师使用 3 小时和 5 小时的电池。 3 小时后，换上一个 8 小时的，再过 2 小时后，手柄再次没电时，已经没有电池可用了。但如果一开始就使用那个 8 小时电量的电池，可以玩满 8 个小时。

告诉你每个品牌电池的使用时间以及该品牌电池的个数，请计算工程师们玩游戏时间的最小值和最大值。

输入格式

输入第一行为一个正整数 n ，表示电池的种数。接下来 n 行，每行两个整数 L 和 F ，表示使用时间为 L 的电池有 F 个。

输出格式

输出仅一行，包含两个整数，分别表示工程师们的最短游戏时间和最长游戏时间（短的时间在前）。两个整数之间以空格隔开。

输入样例

3

3 2

5 2

8 2

输出样例

5 8

 

实习生小胖的百度网页过滤器（ 2007 年初赛）

题目描述

     百度网页采集器 (Baiduspider) 每天从互联网收录数亿网页，互联网的网页质量参差不齐。百度的工程师们每天都在改进方法来判断一个网页质量的好坏，使质量差的网页出现在检索结果中较后的 位置。现在实习生小胖想到一个很简单的方法来判断一个网页内容的好坏，方法如下：

     1. 利用数据挖掘技术在互联网语料库中挖掘出一批有特点的词汇，分为好词和坏词两种，好词标上正的权重，坏词标上负的权重；

     2. 通过好词和坏词词典对每个网页计算网页总权重：从第一个字开始匹配，找到一个好词则加上相应的权重，找到一个坏词则减去相应的权重，下一次匹配将从找到的词末尾的下一个位置开始。

     3. 坏词采用正向最短匹配：从当前匹配位置开始的若干连续汉字，如果形成多个坏词，则只计算最短的那个坏词的权重，下一次匹配将从这个最短坏词末尾的下一个位置开始。

     4. 好词采取正向最长匹配：从当前匹配位置开始的若干连续汉字，如果形成多个 “ 有效 ” 好词，则只计算最长 “ 有效 ” 好词的权重，下一次匹配从这个最长 “ 有效 ” 好词末尾的下一个位置开始。

     5. “ 无效 ” 好词的定义：好词的一部分本身是一个坏词；或者好词的一部分与后续相邻的若干字组成一个坏词。

     现在小胖已经做好了第 1 步的工作，有一个好词和坏词的列表（词典），但是由于没有对中文文本处理的程序经验，他想请未来的百度之星们帮他完成这个程序。

输入格式

输入第一行为一个字符串（网页正文）。从第二行开始为词典，格式为 “ 词 空格 词的权重 ” 。权重为一个带符号 32 位整数。如果权重为正，则为好词，反之则为坏词；不存在重复的词，不存在权重为 0 的词。

测试数据中的词全部为 1-5 个字的中文，但作为 “ 网页 ” 的字符串中同时包含中文和 ASCII 字符，每个汉字占 2 个字节。并非 “ 网页 ” 中的所有字都在词典中。

样例输入

小胖之喷火龙骑士 !!

小胖 6

喷火 -1

喷火龙 -1

火龙 -1

龙 4

龙骑 3

龙骑士 2

骑士 -2

士 3

输出格式

输出仅一行，为网页总权重（答案保证不超过带符号 32 位整数的范围）。

样例输出

7

样例解释

从 “ 网页 ” 中找到的好词为 “ 小胖 ” 和 “ 龙 ” ，坏词为 “ 喷火 ” 和 “ 骑士 ” 。特别要说明一下 “ 龙 ” 被识别为好词的原因 ——“ 喷火 ” 和 “ 喷火龙 ” 均为坏词，按正向最短匹配得到 “ 喷火 ” ，接着往下匹配到好词 “ 龙 ” 、 “ 龙骑 ” 和 “ 龙骑士 ” ，但是由于 “ 骑士 ” 是坏词，所以 “ 龙骑 ” 、 “ 龙骑士 ” 无效而 “ 龙 ” 是最长的有效好词。注意题目描述中的匹配规则，好词的 “ 有效 ” 和 “ 无效 ” 只考虑该好词的一部分与后续字是否能够组成坏词，而不考虑和前面的字是否能够组成坏词 —— 样例中的 “ 龙 ” 虽然可以与前面的字组成坏词 “ 喷火龙 ” 和 “ 火龙 ” ，但由于这两个词都是未能匹配成功的坏词，因此对好词 “ 龙 ” 的词性没有影响，可以累积 “ 龙 ” 的权重。

 

百度时间（ 2007 年初赛）

题目描述

        Baidu 的服务器上使用的不是北京时间，而是 Baidu 时间。 Baidu 时间的时分秒与北京时间相同，但是日期与北京时间不同，是用一个正整数表示从 2000 年 1 月 1 日 起的第几天。

现在就请大家设计一个程序将北京时间转换为百度时间。

输入格式

        输入数据的每一行为一个待转化的北京时间，格式包括两种：

一种为： YYYY-MM-DD ，（ YYYY 表示四位数年份， MM 为两位月份， DD 为两位日期）；

另一种为： MM/DD/YYYY ，（ YYYY 表示四位数年份， MM 为两位月份， DD 为两位日期）；

不符合任何一种格式的输入视为非法输入。

输出格式

        每个数据输出一行。如果格式正确，输出一个正整数，否则输出 Error 。

输入样例

2006-03-21

AStar2007

04/22/2007

输出样例

2149

Error

2463

 

SQL 中的 SELECT 语句（ 2007 年初赛）

题目描述：

SQL 中 SELECT 语句用于从数据库中查询记录。某个工程项目数据库中有一个表，表中满足某个条件的记录数要被频繁查询。查询表中满足某条件的记录数的 SELECT 语句如下：

SELECT 记录数语句： “ SELECT COUNT(*) ” + “ ” + FROM 部分 + “ ” +WHERE 部分

                       或者

                       “ SELECT COUNT(*) ” + “ ” + FROM 部分

SELECT 记录语句：     “ SELECT * ” + “ ” + FROM 部分 + “ ” +WHERE 部分

                       或者

                       “ SELECT * ” + “ ” + FROM 部分

TABLENAME ：            基本单元

FROM 部分： “ FROM ” + “ ” +TABLENMAE 或者 “ FROM （ ” +SELECT 记录语句 + “ ） ”

PROPERTY ：          基本单元

VALUE ：              基本单元

条件部分： PROPERTY + “ = ” +VALUE 或者 PROPERTY + “ = ” +VALUE+ “ ” + “ and ” + “ ” + 条件部分

WHERE 部分： “ WHERE ” + “ ” + 条件部分

基本单元：由大小写字母和数字字符（ 0-9 ）组成的长度不超过 10 的非空字符串

给定表中的所有记录，根据给定的 SELECT 记录数语句要求输出相应的结果（满足条件的总记录数）。

数据输入：

        有多个测试例子：

        每个测试例子：第一行两个整数 N （ 2 < N <= 1000 ）和 M(0< M <= 10000) 分别表示数据库中表的记录数和查询次数；第二行是一个表名 (TABLENAME) ；第三行表中的 C 列属性名（ PROPERTY ）（ 0 < C < 11 ），之间用空格隔开，列属性名各不相同；接下来 N 行，每行表示一个记录，有 C 个 VALUE ，之间用空格隔开；接下去有 M 行，每行一个 SELECT 记录数语句，每个 SELECT 记录数语句长度（包括空格）不超过 1000 ，输入数据保证每条 SELECT 记录数语句满足上面的定义，并且 SELECT 记录数语句中出现的表名和输入的表名一致。

数据输出：

        每个测试例子输出 M 行每行一个整数表示 SELECT 语句输出的结果。

输入样例：

5 6

Book

BookName Price PublishDate Author

NBAsports 10    2004         dearboy

SQL        20     2002         absorbed

IntrotoAlgorithm 59 2002     Thomas

MultipeView      60   2002     RichardHautley

NBAsports   10     2004         dearboy

SELECT COUNT(*) FROM Book WHERE BookName=NBAsports and Author=dearboy

SELECT COUNT(*) FROM Book WHERE Price=20

SELECT COUNT(*) FROM Book WHERE Author=lala

SELECT COUNT(*) FROM (SELECT * FROM Book WHERE BookName=NBAsports)

SELECT COUNT(*) FROM (SELECT * FROM Book WHERE BookName=NBAsports) WHERE Price=20

SELECT COUNT(*) FROM Book

输出样例：

2

1

0

2

0

5

注意 ：大量数据建议使用 scanf(), printf(),gets() 读写数据

 

繁忙的会议室预定问题（ 2007 年初赛）

题目描述

        百度由最开始的 7 人团队迅速发展为几千人的大团队，而工程师们经常需要在一起进行 “ 头脑风暴 ” ，这样会议室就成了紧缺资源。为了有效利用资源，大家决定制定规则， 自动安排会议室的使用。

为了公平起见，应按照申请时间从早到晚依次考虑，先到先得，且申请一旦被接受就不能取消。注意同一时间开的不同会议必须在不同的会议室，而同一个人不能同时参加两个会议。

输入格式

输入第一行为会议室总数 n 和请求总数 m ；第二行是 n 个整数，表示会议室能够容量的人数。以下 m 行每行是一个请求，按请求时间先后顺序排列（即应优先满足在输入中更早出现的请求）。

每个请求中第一个是整数，表示会议需要的时间长度（单位：小时）；之后为与会人名单。人名由不超过四个汉字组成，用半角 逗号分隔（每人名字固定且唯一，有重名的也在登记时区分开）。名单后的数字表示可以安排会议的时间，也以半角逗号分隔，如 10,11,14,15 表示第 10, 11, 14, 15 个小时可以开会（会议时间为 9 到 19 之间的正整数）。

输出格式

输出 m 个数，依次表示每个请求是否被接受。 1 表示接受， 0 表示不接受。

输入样例：
4
20 2

3 张三 , 李四 , 王五 10,11,12,14,15
1 张三 12

4 王六 , 王七 , 王八 , 王九 , 王十 9,10,11,12,13,14,15

2 张三 14,15

输出样例：
1 0 0 1

 

水果开会时段（ 2007 年初赛）

题目描述；

      每个百度工程师团队都有一笔还算丰裕的食品经费，足够每天购置多种水果。水果往往下午送达公司前台。前台的姐姐们只要看到同时出现五种或以上的水果，就称之为 “ 水果开会 ” 。

从搜索引擎切词的语法角度，只要两种水果的名字中有一个字相同就属于同样的类别。例如 “ 小雪梨 ” 和 “ 大雪梨 ” 是同一种水果，而 “ 核桃 ” 和 “ 水蜜桃 ” 也被认为是同一种水果。尤其要指出的是，如果有三种水果 x, y, z 同时在前台出现，且 x 和 y 是同一种水果， y 和 z 也是同一种水果的时候， x 和 z 也被认为是同一种水果。现在前台的姐姐们想知道，今天是否有 “ 水果开会 ”—— 五种或更多的水果同时在前台出现。

输入格式

输入的第一行只有一个整数 n ，表示购置水果的组数。接下来的 n 行表示水果 的到达时间、取走时间（时间用 1200 到 1900 之间的正整数表示，保证取走时间大于到达时间）。剩下的字符串以空格分割每一种水果。如 “ 1400 1600 雪梨 水蜜桃 ” ，表示下午两点到四点（包含两点和四点这两个时间点），雪梨和水蜜桃会在前台等待开会。每种水果名称由不超过十个汉字组成。

输出格式

     输出仅一行，包含一个字符串 Yes 或 No ，分别表示今天水果开会与否。

 

输入样例 1

3

1200 1400 雪梨 柠檬

1300 1400 西瓜 苹果

1400 1800 花生 水蜜桃

输出样例 1

Yes

输入样例 2

3

1200 1400 雪梨 柠檬

1400 1500 哦 大梨 呀

1500 1800 咦 大梨

输出样例 2

No

 

大话西游与数字游戏（ 2007 年初赛）

题目描述

“ 叉烧鸡翅膀，我呀最爱吃！ ……”

百度 spider 组的 “ 黑龙潭之行 ” 在烤着鸡翅，唱着星爷的经典时达到高潮。大家在篝火旁围成一圈，开始玩 “ 数 7 ” 加强版游戏，规则如下：

规则 1 ： 遇 7 的倍数或含 7 的数时 pass 。

规则 2 ： 遇有包含相同数字的数时 pass 。注意相同数字不必相邻。例如 121 。

数错的惩罚很残酷 —— 吞食烤全羊。为避免惩罚，百度工程师们需要你 —— 史上最强程序员的帮助。百度工程师想知道：

req1 x ：符合规则 1 的第 x 个数是什么？

req2 y ：符合规则 2 的第 y 个数是什么？

req12 z ：同时符合规则 1 、 2 的第 z 个数是什么？

query n ：数 n 是规则 1 中的第几个数，是规则 2 中的第几个数？

输入格式

输入的每一行为一个查询，由一个查询词和一个无符号整型数组成。共有四种查询，查询词分别为 req1 、 req2 、 req12 、 query （区分大小写）。

输出格式

前三种查询输出一个无符号整型的解。对于 “ query n ” 的查询，若 n 是规则中的数则输出相应的解，否则输出 -1 。

输入样例

req1 10

req2 10

req12 10

query 14

输出样例

11

10

12

-1 13

补充说明

输入数据共分五组，前四组中： 1<=x<=10000000,1<=y<1000000,1<=z<250000, 1<=n<24000000. ；第五组中的 y 可能达到 5000000