acm题库[大全]
座位调整
题目描述:
百度办公区里到处摆放着各种各样的零食。百度人力资源部的调研发现,员工如果可以在自己喜欢的美食旁边工作,工作效率会大大提高。因此,百度决定进行一次员工座位的大调整。
调整的方法如下:
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
3 10
2 4 4
100 50 25
100 50 25
100 50 25
100 50 25
100 50 25
100 50 25
100 50 25
100 50 25
100 50 25
100 50 25
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 年百度之星程序设计大赛初赛题目 6
百度语言翻译机
时限 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 的翻译。
题目名称:蝈蝈式的记分
内容描述:
蝈蝈小朋友刚刚学会了 0-9 这十个数字 , 也跟爸爸妈妈来参加百度每周进行的羽毛球活动。但是他还没有球拍高,于是大人们叫他记录分数。聪明的蝈蝈发现只要记录连续得分的情况就可以了,比如用“ 3 2 4 ” 可以表示一方在这一局中连得三分后,输了两分,接着又连得到四分。可是,后来大人们发现蝈蝈只会用
0-9 这十个数字,所以当比赛选手得分超过 9 的时候,他会用一个 X 来表示 10
完成记分。但问题是,当记录为“ X 3 5 ” 的时候,蝈蝈自己也记不起来是一方连续得到十三分后,再输五分;还是先赢十分输三分再赢五分。
因为百度内部就要开始进行羽毛球联赛了,要先摸清大家的实力才好分组比赛呢,于是,大人们想知道以前每局的比分是怎样的,以及谁获得了胜利。要是遇到了根据比赛记录无法确认比赛进程的情况,也要输出相应的提示哦。
需要帮蝈蝈进一步说明的是,比赛是五局三胜的,每局先获得二十一分的为胜,但是胜方必须领先对手两分或以上,否则必须继续比赛直到一方超出对手两分为止,比分多的一方获胜。任何一方先获得三局的胜利后就获得胜利,比赛也相应的结束。而且蝈蝈保证是完整的无多余信息的记录了比赛。
输入数据:
以 point.in 为输入文件,文件中首行只有一个整数 M ,表示蝈蝈记录了多少场比赛的分数。每场比赛用两行记录,第一行是一个整数 N(N<=1000) 表示当前这个记录中有多少个字符,第二行就是具体的 N 个字符表示记录的分数。
输出数据:
相应的内容将输出到 point.out 文件中,对应每一个分数记录,输出相应的每局分数,每局分数都使用两个整数表示,表示两个选手的得分,中间用 ":" 分隔开;每组分数记录间使用一个空行分隔开。如果相应的比赛结果无法预测的时候,以” Unknown “一个单词独占一行表示。
输入和输出结果数据样例:
输入样例
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
输出样例
21:17
24:22
21:3
Unknown
21:14
20:22
21:23
21:16
21:9
2006 年百度之星程序设计大赛初赛题目 1
饭团的烦恼
“午餐饭团“是百度内部参与人数最多的民间组织。
同一个部门的,同一间大学的,同一年出生的,用同一种型号电脑的,员工们总是以各种理由,各种借口组织各种长久的,临时的饭团。
参加饭团,不仅可以以优惠的价格尝到更加丰富的菜式,还可以在吃饭的时候和同事们唠唠嗑,吹吹水,增进感情。
但是,随着百度的员工越来越多,各个饭团的管理随即变得烦杂。特别是为了照顾员工们越
来越挑剔的胃口,饭团的点菜负责人背负的责任越来越大。现在,这个重担落在百度之星的肩上,因为,你们将要为所有的百度饭团设计一个自动点菜的算法。
饭团点菜的需求如下:
1 ( 经济是我们要考虑的一个因素,既要充分利用百度员工的午餐补助,又不能铺张浪费。因此,我们希望最后的人均费用越接近 1
2 元越好。
2 ( 菜式丰富是我们要考虑的另一个因素。为简单起见,我们将各种菜肴的属性归结为荤菜,素菜,辛辣,清淡,并且每个菜只能点一次。
3 ( 请紧记,百度饭团在各大餐馆享受 8 折优惠。
输入数据描述如下:
第一行包含三个整数 N , M , K ( 0 紧接着 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 之内 Run Length Encoding Description Your task is to write a program that performs a simple form of run-length encoding, as described by the rules below. Any sequence of between 2 to 9 identical characters is encoded by two characters. The first character is the length of the sequence, represented by one of the characters 2 through 9. The second character is the value of the repeated character. A sequence of more than 9 identical characters is dealt with by first encoding 9 characters, then the remaining ones. Any sequence of characters that does not contain consecutive repetitions of any characters is represented by a 1 character followed by the sequence of characters, terminated with another 1. If a 1 appears as part of the sequence, it is escaped with a 1, thus two 1 characters are output. Input The input consists of letters (both upper- and lower-case), digits, spaces, and punctuation. Every line is terminated with a newline character and no other characters appear in the input. Output Each line in the input is encoded separately as described above. The newline at the end of each line is not encoded, but is passed directly to the output. 输入样例 AAAAAABCCCC 12344 输出样例 6A1B14C 11123124 Source Ulm Local 2004 Sorting It All Out Description An ascending sorted sequence of distinct values is one in which some form of a less-than operator is used to order the elements from smallest to largest. For example, the sorted sequence A, B, C, D implies that A < B, B < C and C < D. in this problem, we will give you a set of relations of the form A < B and ask you to determine whether a sorted order has been specified or not. Input Input consists of multiple problem instances. Each instance starts with a line containing two positive integers n and m. the first value indicated the number of objects to sort, where 2 <= n <= 26. The objects to be sorted will be the first n characters of the uppercase alphabet. The second value m indicates the number of relations of the form A < B which will be given in this problem instance. Next will be m lines, each containing one such relation consisting of three characters: an uppercase letter, the character "<" and a second uppercase letter. No letter will be outside the range of the first n letters of the alphabet. Values of n = m = 0 indicate end of input. Output For each problem instance, output consists of one line. This line should be one of the following three: Sorted sequence determined after xxx relations: yyy...y. Sorted sequence cannot be determined. Inconsistency found after xxx relations. where xxx is the number of relations processed at the time either a sorted sequence is determined or an inconsistency is found, whichever comes first, and yyy...y is the sorted, ascending sequence. 输入样例 4 6 A