软件大赛算法设计练习题目.pdf

1、母牛生小牛

Problem

设有一头小母牛，从出生第四年起每年生一头小母牛，按此规律，第N年时有几

头母牛？

Input

本题有多组数据。每组数据只有一个整数N，独占一行。(1≤N≤50)

Output

对每组数据，输出一个整数（独占一行）表示第N年时母牛的数量

SampleInput

1

4

5

20

SampleOutput

1

2

3

872

2、座位调整

题目描述：

百度办公区里到处摆放着各种各样的零食。百度人力资源部的调研发现，员工如果可以

在自己喜欢的美食旁边工作，工作效率会大大提高。因此，百度决定进行一次员工座位的大

调整。

调整的方法如下：

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个区域的喜好度。

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

输入样例

33

111

1005025

1005025

1005025

输出样例

175

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

100+50+25=175

最优解

3、剪刀石头布

剪刀石头布

N个小孩正在和你玩一种剪刀石头布游戏。N个小孩中有一个是裁判，其

余小孩分成三组（不排除某些组没有任何成员的可能性），但是你不知道谁是裁

判，也不知道小孩们的分组情况。然后，小孩们开始玩剪刀石头布游戏，一共玩

M次，每次任意选择两个小孩进行一轮，你会被告知结果，即两个小孩的胜负情

况，然而你不会得知小孩具体出的是剪刀、石头还是布。已知各组的小孩分别只

会出一种手势（因而同一组的两个小孩总会是和局），而裁判则每次都会随便选

择出一种手势，因此没有人会知道裁判到底会出什么。请你在M次剪刀石头布

游戏结束后，猜猜谁是裁判。如果你能猜出谁是裁判，请说明最早在第几次游戏

结束后你就能够确定谁是裁判。

输入格式：

输入文件包含多组测试数据。每组测试数据第一行为两个整数N和M（1

≤N≤500，0≤M≤2000），分别为小孩的个数和剪刀石头布游戏进行

的次数。接下来M行，每行两个整数且中间以一个符号隔开。两个整数分别为

进行游戏的两个小孩各自的编号，为小于N的非负整数。符号的可能值为“=”、

“”和“”，分别表示和局、第一个小孩胜和第二个小孩胜三种情况。

输出格式：

每组测试数据输出一行，若能猜出谁是裁判，则输出身为裁判的小孩的编号，

并输出在第几次游戏结束后就能够确定谁是裁判。如果无法确定谁是裁判，或者

发现剪刀石头布游戏的胜负情况不合理（即无论谁是裁判都会出现矛盾），则输

出相应的信息。具体输出格式请参考输出样例。

输入样例

33

01

12

20

35

01

01

12

12

02

44

01

01

23

23

10

输出样例

Cannotdetermine

Player1canbedeterminedtobethejudgeafter4lines

Impossible

Player