搜索
2005年百度之星程序设计大赛试题初赛题目第一题（共四题100分）：连续正整数（10分）题目描述：一个正整数有可能可以被表示为n(n=2)个连续正整数之和，如：15=1+2+3+4+515=4+5+615=7+8请编写程序，根据输入的任何一个正整数，找出符合这种要求的所有连续正整数序列。输入数据：一个正整数，以命令行参数的形式提供给程序。输出数据：在标准输出上打印出符合题目描述的全部正整数序列，每行一个序列，每个序列都从该序列的昀小正整数开始、以从小到大的顺序打印。如果结果有多个序列，按各序列的昀小正整数的大小从小到大打印各序列。此外，序列不允许重复，序列内的整数用一个空格分隔。如果没有符合要求的序列，输出“NONE”。例如，对于15，其输出结果是：1234545678对于16，其输出结果是：NONE评分标准：程序输出结果是否正确。百度之星程序设计大赛试题-2第二题（共四题100分）：重叠区间大小（20分）题目描述：请编写程序，找出下面“输入数据及格式”中所描述的输入数据文件中昀大重叠区间的大小。对一个正整数n，如果n在数据文件中某行的两个正整数（假设为A和B）之间，即A=n=B或A=n=B，则n属于该行；如果n同时属于行i和j，则i和j有重叠区间；重叠区间的大小是同时属于行i和j的整数个数。例如，行（1020）和（1225）的重叠区间为[1220]，其大小为9；行（2010）和（1218）的重叠区间为[1012]，其大小为3；行(2010)和（2030）的重叠区间大小为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中出现次数昀少的单词之后的文本（词与词保持原来的顺序，仍以空格分隔）。评分标准：程序输出结果必须正确，内存使用越少越好，程序的执行时间越快越好。2005年百度之星程序设计大赛试题总决赛题目题目描述：八方块移动游戏要求从一个含8个数字（用1-8表示）的方块以及一个空格方块（用0表示）的3x3矩阵的起始状态开始，不断移动该空格方块以使其和相邻的方块互换，直至达到所定义的目标状态。空格方块在中间位置时有上、下、左、右4个方向可移动，在四个角落上有2个方向可移动，在其他位置上有3个方向可移动。例如，假设一个3x3矩阵的初始状态为：803214765目标状态为：123804765则一个合法的移动路径为：803813813013103123214=204=024=824=824=804765765765765765765另外，在所有可能的从初始状态到目标状态的移动路径中，步数昀少的路径被称为昀短路径；在上面的例子中，昀短路径为5。如果不存在从初试状态到目标状态的任何路径，则称该组状态无解。请设计有效的（细节请见评分规则）算法找到从八方块的某初试状态到某目标状态的所有可能路径中的昀短路径，并用C/C++实现。输入数据：程序需读入已被命名为start.txt的初始状态和已被命名为goal.txt的目标状态，这两个文件都由9个数字组成（0表示空格，1-8表示8个数字方块），每行3个数字，数字之间用空格隔开。输出数据：如果输入数据有解，输出一个表示昀短路径的非负的整数；如果输入数据无解，输出-1。自测用例：如果输入为：start.txt和goal.txt，则产生的输出应为：5又例，如果用784356102替换start.txt中的内容，则产生的输出应为：21评分规则：1）我们将首先使用和自测用例不同的10个start.txt以及相同的goal.txt，每个测试用例的运行时间在一台IntelXeon2.80GHz4CPU/6G内存的Linux机器上应不超过10秒（内存使用不限制），否则该用例不得分；2）每个选手的总分（精确到小数点后6位）=10秒钟内能产生正确结果的测试用例数量x10+（1/产生这些正确结果的测试用例的平均运行毫秒)；3）如果按此评分统计仍不能得出总决赛将决出的一、二、三等奖共计九名获奖者，我们将先设N=2，然后重复下述过程直至产生昀高的9位得分：用随机生成的另外10个有解的start.txt再做测试，并对这10*N个测试用例用2）中公式重新计算总分，N++。2006年百度之星程序设计大赛初赛题目1饭团的烦恼“午餐饭团“是百度内部参与人数昀多的民间组织。同一个部门的，同一间大学的，同一年出生的，用同一种型号电脑的，员工们总是以各种理由，各种借口组织各种长久的，临时的饭团。参加饭团，不仅可以以优惠的价格尝到更加丰富的菜式，还可以在吃饭的时候和同事们唠唠嗑，吹吹水，增进感情。但是，随着百度的员工越来越多，各个饭团的管理随即变得烦杂。特别是为了照顾员工们越来越挑剔的胃口，饭团的点菜负责人背负的责任越来越大。现在，这个重担落在百度之星的肩上，因为，你们将要为所有的百度饭团设计一个自动点菜的算法。饭团点菜的需求如下：1．经济是我们要考虑的一个因素，既要充分利用百度员工的午餐补助，又不能铺张浪费。因此，我们希望昀后的人均费用越接近12元越好。2．菜式丰富是我们要考虑的另一个因素。为简单起见，我们将各种菜肴的属性归结为荤菜，素菜，辛辣，清淡，并且每个菜只能点一次。3．请紧记，百度饭团在各大餐馆享受8折优惠。输入数据描述如下：第一行包含三个整数N，M，K(0=16，0N=16，0=N，0M=N，0=12)，分别表示菜单上菜的数目，饭团需要点的菜的数目，就餐的人数。K=12)，分别表示菜单上菜的数目，饭团需要点的菜的数目，就餐的人数。紧接着N行，每行的格式如下：菜名（长度不超过20个字符）价格（原价，整数）是否荤菜（1表示是，0表示否）是否辛辣（1表示是，0表示否）例：水煮鱼3011紧接着是abcd四个整数，分别表示需要点的荤菜，素菜，辛辣，清淡菜的数目。输出数据：对于每一测试数据，输出数据包含M+1行，前M行每行包含一个菜名（按菜名在原菜单的顺序排序）。第M+1行是人均消费，结果保留两位小数。说明：1．结果菜单的数目应该恰好为M，荤菜，素菜，辛辣，清淡菜的数目恰好为a，b，c，d。在满足这样的前提下，选择人均消费昀接近12元的点菜方案。题目数据保证有且仅有一个解。2．每组测试数据的结果用一个空行隔开。末尾不要有多余的空行。输入样例322水煮鱼3011口水鸡1811清炖豆腐12001111输出样例口水鸡清炖豆腐12.00时间要求：1S之内2006年百度之星程序设计大赛初赛题目2题目名称：蝈蝈式的记分内容描述：蝈蝈小朋友刚刚学会了0-9这十个数字,也跟爸爸妈妈来参加百度每周进行的羽毛球活动。但是他还没有球拍高，于是大人们叫他记录分数。聪明的蝈蝈发现只要记录连续得分的情况就可以了，比如用“324”可以表示一方在这一局中连得三分后，输了两分，接着又连得到四分。可是，后来大人们发现蝈蝈只会用0-9这十个数字，所以当比赛选手得分超过9的时候，他会用一个X来表示10完成记分。但问题是，当记录为“X35”的时候，蝈蝈自己也记不起来是一方连续得到十三分后，再输五分；还是先赢十分输三分再赢五分。因为百度内部就要开始进行羽毛球联赛了，要先摸清大家的实力才好分组比赛呢～于是，大人们想知道以前每局的比分是怎样的，以及谁获得了胜利。要是遇到了根据比赛记录无法确认比赛进程的情况，也要输出相应的提示哦。需要帮蝈蝈进一步说明的是，比赛是五局三胜的，每局先获得二十一分的为胜，但是胜方必须领先对手两分或以上，否则必须继续比赛直到一方超出对手两分为止，比分多的一方获胜。任何一方先获得三局的胜利后就获得胜利，比赛也相应的结束。而且蝈蝈保证是完整的无多余信息的记录了比赛。输入数据：以point.in为输入文件，文件中首行只有一个整数M，表示蝈蝈记录了多少场比赛的分数。每场比赛用两行记录，第一行是一个整数N(N=1000)表示当前这个记录中有多少个字符，第二行就是具体的N个字符表示记录的分数。输出数据：相应的内容将输出到point.out文件中，对应每一个分数记录，输出相应的每局分数，每局分数都使用两个整数表示，表示两个选手的得分，中间用:分隔开；每组分数记录间使用一个空行分隔开。如果相应的比赛结果无法预测的时候，以”Unknown“一个单词独占一行表示。输入和输出结果数据样例：SampleInput：323973624783279X22121X1X11259385483984XXXX2XXXX284924437777734567654213579753130993932111515151551SampleOutput：21:1724:2221:3Unknown21:1420:2221:2321:1621:92006年百度之星程序设计大赛初赛题目3变态的比赛规则为了促进各部门员工的交流，百度(baidu)举办了一场全公司范围内的拳皇友谊赛，负责组织这场比赛的是百度的超级拳皇迷W.Z.W.Z不想用传统的淘汰赛或者循环赛的方式，而是自己制定了一个比赛规则。由于一些员工（比如同部门或者相临部门员工）平时接触的机会比较多，为了促进不同部门之间的交流，W.Z希望员工自己组成不同组。不同组之间的每两个人都会进行一场友谊赛而同一组内的人则之间不会打任何比赛。比如4个人，编号为1--4,如果分为两个组并且1,2一个组，3，4一个组，那么一共需要打四场比赛：1vs3,1vs4,2vs3,2vs4.而如果是1,2,3一组，4单独一组，那么一共需要打三场比赛:1vs4,2vs4,3vs4.很快W.Z意识到，这样的比赛规则可能会让比赛的场数非常多。W.Z想知道如果有N个人,通过上面这种比赛规则，总比赛场数有可能为K场吗？比如3个人，如果只分到一组则不需要比赛，如果分到两组则需要2场比赛,如果分为三组则需要3场比赛。但是无论怎么分都不可能只需要1场比赛。相信作为编程高手