2007年5月31日星期四

Astar2007 初赛第二阶段题

由于第二场初赛没有参加,所以从NINSTEIN'S BLOG转贴了这场比赛的题目。唉 看看吧~

1.百度时间

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



现在就请大家设计一个程序将北京时间转换为百度时间。在本题中,闰年的年份是400的倍数,或者是4的倍数但不是100的倍数。比如2000和8888均为闰年,但6100不是。

输入格式

输入数据的每一行为一个待转化的北京时间(不含空格和TAB),正确的格式包括两种:

一种为:YYYY-MM-DD,(YYYY表示四位数年份,MM为两位月份,DD为两位日期);

另一种为:MM/DD/YYYY,(YYYY表示四位数年份,MM为两位月份,DD为两位日期);

输出格式

每个数据输出一行。如果可以成功转换,输出一个正整数,否则输出Error。

输入样例

2000-01-01

AStar2007

05/26/2007

输出样例

0

Error

2702

评分规则

  1. 程序将运行在一台Linux机器上(内存使用不作严格限制),在每一测试用例上运行不能超过1秒,否则该用例不得分;

  2. 要求程序能按照输入样例的格式读取标准输入数据,按照输出样例的格式将运行结果输出到标准输出上。如果不能正确读入数据和输出数据,该题将不得分;

  3. 该题共有5个测试数据集,数据1和数据2中的所有日期均能成功转换。所有数据中,每行不超过20个字符,每组数据最多包含100行;

  4. 该题目20分。

2.实习生小胖的百度网页过滤器

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

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

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

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

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

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

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

 

输入格式

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

作为“网页”的字符串中同时包含中文和ASCII字符,每个汉字占2个字节。并非“网页”中的所有字都在词典中。

输出格式

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

样例输入

小胖之喷火龙骑士!!

小胖 6

喷火 -1

喷火龙 -1

火龙 -1

龙 4

龙骑 3

龙骑士 2

骑士 -2

士 3

样例输出

7

样例解释

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

注意事项

输入数据的中文采用GBK编码。

GBK: 是又一个汉字编码标准,全称《汉字内码扩展规范》。采用双字节表示,总体编码范围为 8140-FEFE,首字节在 81-FE 之间,尾字节在 40-FE 之间,排除xx7F。总计 23940 个码位,共收入 21886 个汉字和图形符号,其中汉字(包括部首和构件)21003 个,图形符号 883 个。

评分规则

  1. 程序将运行在一台Linux机器上(内存使用不作严格限制),在每一测试用例上运行不能超过1秒,否则该用例不得分;

  2. 要求程序能按照输入样例的格式读取标准输入数据,按照输出样例的格式将运行结果输出到标准输出上。如果不能正确读入数据和输出数据,该题将不得分;

  3. 该题共有10个测试数据集,前7组数据的大小不超过1K字节,数据8和数据9不超过600K字节,数据10的网页正文不超过1M字节。所有数据的词典不超过50,000项,且词典中的词保证由1到5个汉字组成。词典不包含重复的单词;

  4. 该题目20分。

3.Wii游戏开始啦!

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



Wii游戏机有两个手柄,每个手柄使用两节电池(这两个电池可以是不同的品牌),其中至少一块电池没电时该手柄没电。



工程师们在玩游戏时,总是用最简单的方式更换电池:有手柄没电时把所有没电的电池拿走,一一换上新电池即可(有电的电池总是继续使用)。当有手柄没电且没有新电池可用时才停止玩Wii。



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

输入格式

输入第一行为一个正整数n,表示电池的种数。接下来n行,每行两个整数L和F,表示使用时间为L的电池有F个(电池不必成对出现,即F可以是奇数)。

输出格式

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

输入样例

3

3 2

5 2

8 2

输出样例

5 8

样例解释

有三对电池,使用时间分别为3小时、5小时和8小时。

方案1:一开始给手柄1使用一对3小时的电池,给手柄2使用一对5小时的电池,则3小时后手柄1没电,换上一对8小时的。再过2小时后,手柄2没电。此时已经没有电池可用了。总时间为5小时。

方案2:一开始给手柄1使用一对8小时的电池,给手柄2使用一对5小时的电池,则5小时后手柄2没电,换上一对3小时的。再过3小时后,手柄1和手柄2同时没电。此时已经没有电池可用了。总时间为8小时。

评分规则

  1. 程序将运行在一台Linux机器上(内存使用不作严格限制),在每一测试用例上运行不能超过2秒,否则该用例不得分;

  2. 要求程序能按照输入样例的格式读取标准输入数据,按照输出样例的格式将运行结果输出到标准输出上。如果不能正确读入数据和输出数据,该题将不得分;

  3. 该题共有15个测试数据集,均满足n<=10, L<=200, F的总和不超过30;

  4. 该题目30分。

4.百度的高级搜索方法

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

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

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



现在我们有一个inurl查询列表和一个url列表,你能找出所有至少被查询过一次的url吗?

输入格式

输入第一行是一个整数n,表示一共有n个查询。以下n行每行一个查询。查询的site部分和inurl部分中间恰好用一个空格分割,且每行不包含其他空格。下一行是一个整数m,表示url列表中一共有m个url。以下m行每行一个url。

输出格式

每个url输出一行。如果至少符合一条查询,输出1,否则输出0。

输入样例

3

site:www.baidu.com inurl:/more

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

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

7

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

输出样例

1

1

0

0

0

0

1

评分规则

  1. 程序将运行在一台Linux机器上(内存使用不作严格限制),在每一测试用例上运行不能超过2秒,否则该用例不得分;

  2. 要求程序能按照输入样例的格式读取标准输入数据,按照输出样例的格式将运行结果输出到标准输出上。如果不能正确读入数据和输出数据,该题将不得分;

  3. 该题共有6个测试数据集,数据1,2,3,4,5,6的大小分别约为4K, 750K, 1.5M, 6.5M, 12M, 18M。所有查询和url均合法,url均以http://开头。url和查询中可能包含中文。输入文件的每行不超过256个字节;

  4. 该题目30分




Technorati Tags:



Powered by ScribeFire.

没有评论: