2006年05月27日

共6个题目,
要求在8个小时内完成。
可以使用c/c++语言,要求可以gcc/g++编译通过。

题目如下:

1.百度语言翻译机

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

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

输入要求:

输入数据包含三部分:

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小组。

样例:in.txt

输出要求:

输出将缩略语转换成日常语言后的文档。(将缩略语转换成日常语言,其他字符保留原样)。例:

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

样例:out.txt

评分规则:

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

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

3.该题目共有4个测试用例,每个测试用例为一个输入文件。各测试用例占该题目分数的比例分别为25%,25%,25%,25%;

4.该题目20分。

注意事项:

1.输入数据是中英文混合的,中文采用GBK编码

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



2.为保证答案的唯一性,缩略语的转换采用正向最大匹配(从左到右为正方向)原则。请注意样例中PMD的翻译。


2.饭团的烦恼

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

同一个部门的、同一所大学的、同一年出生的、使用同一种型号电脑的员工们总是以各种理由组织各种长期的、临时的饭团。

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

但是,随着百度的员工越来越多,各个饭团的管理变得繁杂起来。特别是为了照顾员工们越来越挑剔的胃,饭团的点菜负责人的压力也越来越大。现在,这个任务就交给“百度之星”了,因为,你将要为所有的百度饭团设计一个自动点菜的算法。

饭团点菜的需求如下:

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

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

3.请谨记,百度饭团在各大餐馆享受8折优惠

输入要求:

1.输入数据第一行包含三个整数N,M,K(0<N<=16,0<M<=N,0<K<=12),分别表示菜单上菜的数目,饭团需要点的菜的数目,就餐的人数;

2.紧接着N行,每行的格式如下:

菜名(长度不超过20个字符) 价格(原价,整数) 是否荤菜(1表示是,0表示否) 是否辛辣(1表示是,0表示否);

3.第N+2行是 a b c d 四个整数,分别表示需要点的荤菜,素菜,辛辣,清淡菜的数目。例:

3 2 2

水煮鱼 30 1 1

口水鸡 18 1 1

清炖豆腐 12 0 0

1 1 1 1

样例:in.txt

输出要求:

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

口水鸡

清炖豆腐

12.00

样例:out.txt

评分规则:

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

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

3.该题目共有5个测试用例,每个测试用例为一个输入文件。各测试用例占该题目分数的比例分别为20%,20%,20%,20%,20%;

4.该题目10分。


3.变态比赛规则

为了促进各部门员工的交流,百度举办了一场全公司范围内的“拳皇”(百度内部最流行的格斗游戏)友谊赛,负责组织这场比赛的是百度的超级“拳皇”迷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)。例:

2 0

2 1

3 1

3 2

样例:in.txt

输出要求:

对输入的N,K 如果N个员工通过一定的分组方式可以使比赛场数恰好为K,则输出"YES",否则输出"NO"(请全部使用大写字母),每组数据占一行。例:

YES

YES

NO

YES

样例:out.txt

评分规则:

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

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

3.该题目共有3个测试数据集,每个测试数据集为一个输入文件。各测试数据集占该题目分数的比例分别为30%,30%,40%;

4.该题目20分。


4.蝈蝈计分

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

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

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

输入要求:

1.文件中第一行只有一个整数M,表示蝈蝈记录了多少场比赛的分数;

2.在接下来的2M行里,每场比赛用两行记录,第一行是一个整数N(N<=1000)表示当前这个记录中有多少个字符,第二行就是具体的N个字符表示记录的分数(相邻字符用空格隔开)。例:

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

样例:in.txt

输出要求:

对应每一个分数记录,输出相应的每局分数,每局分数都使用两个整数表示,表示两个选手的得分,中间用":"分隔开;每组分数记录间使用一个空行分隔开。如果相应的比赛结果无法预测,以“UNKNOWN”一个单词独占一行表示(请全部使用大写字母)。例:

21:17

24:22

21:3


UNKNOWN


21:14

20:22

21:23

21:16

21:9

样例:out.txt

评分规则:

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

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

3.该题目共有4个测试数据集,每个测试数据集为一个输入文件。各测试数据集占该题目分数的比例分别为20%,30%,40%,10%;

4.该题目10分。


5.座位调整

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

调整的方法如下:

1.首先将办公区按照各种零食的摆放分成N个不同的区域(例如:可乐区,饼干区,牛奶区等等);

2.每个员工对不同的零食区域有不同的喜好程度(喜好程度是1~100的整数, 喜好程度越大表示该员工越希望被调整到相应的零食区域);

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

输入要求:

文件第一行包含两个整数N,M(N>=1,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

样例:in.txt

输出要求:

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

175

样例:out.txt

数据解释:

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

评分规则:

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

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

3.该题目共有4个测试用例,每个测试用例为一个输入文件。各测试用例占该题目分数的比例分别为25%,25%,25%,25%;

4.该题目20分。


6.剪刀石头布

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

样例:in.txt

输出要求:

1.每组测试数据输出一行,若能猜出谁是裁判,则输出裁判的编号,并输出在第几次游戏结束后就能够确定谁是裁判,小孩的编号和游戏次数以一个空格隔开;

2.如果无法确定谁是裁判,输出-2;如果发现剪刀石头布游戏的胜负情况不合理(即无论谁是裁判都会出现矛盾),则输出-1。例:

-2

1 4

-1

0 0

样例:out.txt

评分规则:

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

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

3.该题目共有5个测试用例,每个测试用例为一个输入文件。各测试用例占该题目分数的比例分别为5%、10%、15%、30%和40%;

4.该题目20分。

2006年05月24日

中国人的特点:贪财怕死爱面子。
贪财,很好,不过要君子爱财,取之有道。要适度。
怕死,也是这样,不怕死得人走遍天下都不怕,太怕死不好。要适度。
爱面子,也是,一皮天下无难事。脸皮需要加厚,做个强人。要适度。

有句话叫做自作自受。
自己做的事情,无论好坏,最终还是作用在自己身上。



steve jobs创建了apple公司,
然后企图说服百事可乐老大斯卡利加盟apple,结果四个月起仍然没有动心,
最后一句:你是想卖苏打水度过余生呢,还是想有机会改变世界?
打动了斯卡利,于是进入apple……

看来steve jobs之流确实有过人的口才,非我辈所能匹敌的。

然而,stev jobs被迫离开apple(董事会的决定,看来一个公司的创始人也可能会被公司开掉的),一怒之下,stev卖掉了apple的所有股票,而只剩下一股来看财务报表。

果然很强,不过也反映了当时的stev确实还不够成熟吧,却有着非凡的魄力与勇气。

之后,它没有有自杀,相反的,它创建了Next公司,并同样的依靠自己非凡的口才说服了apple董事会利用Next作为苹果的下一代操作系统。

于是乎,一场复仇行动就这样的开始了。ipod,itune,imusic等风靡世界。

stev jobs不愧为高手,学习,口才,为人等,都一流。向你学习,stev jobs.

2006年05月23日

有些网站是可能把你封掉的,比如封掉你的user_agent,BaiduSpider好像就被n多网站封过。哈哈,所以可以把user_agent改成可以配置,不过这样rp不好。

有些网站虽然可以先head一下,再确认其状态,决定是否进行下一步的抓取,但是有些网站比较奇怪:
当你head的时候,会返回404:Object not Found,而事实上当你去世纪抓去的时候,它还活得好好的……比如www.51study.net:
当你直接GET的时候
返回正常,能够正常地抓取。
$ wget www.51study.net
–11:25:07–  http://www.51study.net/
           => `index.html’
Resolving www.51study.net… done.
Connecting to www.51study.net[218.85.134.162]:80… connected.
HTTP request sent, awaiting response… 200 OK
Length: 49,752 [text/html]

100%[=================================================================================>] 49,752       269.92K/s    ETA 00:00

11:25:08 (269.92 KB/s) – `index.html’ saved [49752/49752]

而当你进行head的时候:

$ wget –spider www.51study.net 
–11:26:30–  http://www.51study.net/
           => `index.html.1′
Resolving www.51study.net… done.
Connecting to www.51study.net[218.85.134.162]:80… connected.
HTTP request sent, awaiting response… 404 Object Not Found
11:26:30 ERROR 404: Object Not Found.

哈哈,竟然是404,bt吧?

2006年05月19日

google notebook只有很小的164 K,
而其功能以及实用性都十分不错,
下面是一些我使用的截图。


google notebook


google notebook note this right click button


google notebook note this button


google notebook

不过,google notebook有一些很明显的as_design的bug,
比如说,mini模式下,窗口的大小高度不能够调整,
而且有的时候,比如在iframe中note this的话,有可能会出现add to notebook error的错误。

希望google notebook能够改进之。


据悉,为了支持奥委会工作,配合2008年奥运会主管的建设开展,
联合国组织决定对中国进行一次大规模的支援,
但是为了避开一些国家的反对,
所以采取了将黄金磨成金粉然后进行空投的形式,
目前看来,已经取得了很好的效果。

居各地区统计,北京市海淀地区金分数量已经累计达到惊人的30cm,
属于北京地区的降金量最多的地区之一。
但居某市民反映,所谓的金粉中含有部分的沙尘,这一发现有可能属于联合国内部贪污受贿的重要线索。

2006年05月17日


1.男人是社会的主体,不管你信或不信。所以男人应该有种责任感 

2.25岁之前,请记得,爱情通常是假的,或者不是你所想象的那样纯洁和永远。如果你过了25岁,那么你应该懂得这个道理。   

3.吃饭7成饱最舒服。对待女友最多也请你保持在7成。

4.30岁之前请爱惜自己的身体,前30年你找病,后30年病找你。如果你过了30岁,你自然也会懂得这个道理。 

5.事业远比爱情重要。如果说事业都不能永恒,那么爱情只能算是昙花一现。

6.不要轻易接受追求你的女孩。女追男隔层纱。如果你很容易就陷进去,你会发现你会错过很多东西,失去很多东西。 

7.请你相信,能用钱解决的问题,都不是问题。如果你认为钱索王道,有钱有女人,没钱没女人,那么。女人不是问题。
 
8.请永远积极向上。每个男人都有他可爱的地方,但是不可爱的地方只有不积极面对生活。 

9.不要连续2次让同一个女人伤害。好马不吃回头草,是有他道理的。如果认真考虑过该分手,那么请不要做任何舍不得的行动。 

10.如果你和你前女友能做朋友,那么你要问自己:为什么?如果分手后还是朋友,那么只有2个可能:。你们当初都只是玩玩而已,没付出彼此最真的感情。或者:必定有个人是在默默的付出无怨无悔!

11.永远不要太相信女人在恋爱时的甜言蜜语。都说女人爱听甜言蜜语,其实,男人更喜欢。
 
12.请不要为自己的相貌或者身高过分担心和自卑。人是动物,但是区别于动物。先天条件并不是阻挡你好好生活的借口。人的心灵远胜于相貌,请相信这点。如果有人以相貌取人,那么你也没必要太在意。因为他从某种意义来讲,只是只动物。你会跟动物怄气吗? 

13.失恋时,只有2种可能,要么你爱她她不爱你,或者相反。那么,当你爱的人不再爱你,或者从来没爱过你时。你没有遗憾,因为你失去的只是一个不爱你的人

14.请不要欺骗善良的女孩。这个世界上,善良的女孩太少。
 
15.不能偏激的认为金钱万能,至少,金钱治不好艾滋病。 

16.请一定要有自信。你就是一道风景,没必要在别人风景里面仰视。 

17.受到再大的打击,只要生命还在,请相信每天的太阳都是新的。 

18.爱情永远不可能是天平。你想在爱情里幸福就要舍得伤心 

19.如果你喜欢一个认为别人应该对她好的mm,请尽早放弃。没有人是应该对一个人好的。如果她不明白这个道理,也就是她根本不懂得珍惜。 

20.不要因为寂寞而“找”gf,寂寞男人请要学会品味寂寞。请记住:即使寂寞,远方黑暗的夜空下,一定有人和你一样,寂寞的人不同,仰望的星空却是唯一。 

21.任何事没有永远。也别问怎样才能永远。生活有很多无奈。请尽量充实自己,充实生活。请善待生活。 

22.男人有很多无奈,生活很累但是因为生活才有意义。当你以为你一无所有时,你至少还有时间,时间能抚平一切创伤。所以请不要流泪。

2006年05月15日



一、卡巴就好象西毒,凶猛强悍,神功盖世,对敌决不留情,出手狠辣,招招夺命,绝少失手,不愧为一代枭雄,但毕竟练的不是纯正内功,容易走火入魔,导致系统出问题。

二、麦咖啡就象东邪,玉树临风,俊朗潇洒,对敌招式繁多,机关重重,杀伐决断从不迟疑,为江湖第一机智聪明之人,但因其心机太深,令人难以掌握。

三、诺顿就象南帝,雍容华贵,稳沉厚重,胸怀博大,练的是纯正内功,靠的是教化感人,对敌有慈悲心肠,一般采取隔离教化,使其不再作恶,很少杀人,称的上是一代宗师,但因其过于敦厚,不仅自己活的累,别人也为他感到累。

四、nod32就想北丐,来无影去无踪,潇潇洒洒,笑傲江湖,对敌用的是逍遥游和打狗棍法,江湖上少有对手,但因其过于轻浮,难免误事。

国产的就像全真七子
,一起上还凑合。

 

2006年05月14日

记得有一家咖啡店的名字叫做时光底片,
而在这段要离开的日子,
我爱上了这个名字。

那些快乐的时光,永远的一去不返了。
而或许时光底片可以给我们一丝生活的勇气,
时光流逝,什么都没有得到,或许我们可以在时光的底片中找到曾经的快乐
以及痛苦。

还有另外一家咖啡店叫做雕刻时光(SIT,sculpting in time),是我们第一次约会的地方。
那时的约定,每次生日都要在那里度过,
并且在精致的餐巾纸上面留下了我们的约定。
而誓言毕竟只是誓言,
而雕刻时光,我们已经很久没有光顾了。
那家小店,
那个靠窗的位子,
那个三月的三明治的精致的卡片,
是否能够在时光中长存呢?

而这个北京的温暖的家,在要走的时候,我还是充满着留恋的。
曾经一起坐在地上看电影,
到后来在地上睡的不省人事……
曾经一起杀人,
通宵不眠……
曾经一块在街上闲逛……
而那些日子风一样,
刮过我的06年消失不见了。

或许,这是真正的分手,
生活就是这样,
压力总是将人们无情的分开,
无论他们是多么的不情愿。
虽然依然在同一个城市中生活,呼吸,崩波
而心灵相通的时候毕就像网络上流传的数据一样,
ttl到了的时候,就要消失了。

没有爱情,
只有生活的琐碎,
只有烦恼,
等待,挂念,愤怒。
而点缀中央的些许幸福,将使我幸福一生。

感谢我的这一年,2005年3月到2006年5月。
我将终生铭记。

2006年05月11日

送给自己几句话:


第一:hard work,成功必经之路。

积极工作才是硬道理。


第二:别人的意见近供参考,靠自己去成功。

把握住自己。


第三:下定决心去成功,给别人以及老板一个承诺。

痛下决心,你就能成功。


第四:找个时间,在那一天看8本书。