程序设计大赛题目

注：1、在比赛时我们将从以下三题选出一题作为比赛内容。

2、另两道题目我们将在现场给出。

3、地点：实验楼305

4、时间：12月15日下午1点到四点

5、请带上有效证件：学生证、身份证（任一）

试题1 某年轻导演准备拍摄一部名为《大学生活》的喜剧电影。由于预算紧张导演绞尽脑汁想节省开支。作为剧务的你提醒他：“演员的出场费很高，能不能让他们一人分演多个角色？充分挖掘他们的潜力，也可以节省我们的开支嘛！”导演大呼“有创意”，并顺手把剧本塞给你，“你研究研究剧本，看最少需要几个演员”，说着就准备出门去再拉几个广告赞助商，临走前他又补充了几点要求：

              1、男演员只能演男角色，女演员只能演女角色。

              2、角色的扮演者确定下来后，在演出的过程中就不能中途更改。

              3、如果两个角色会同时在一个场景中出现，则这两个角色必须由两个不同的演员扮演。

导演走后，你翻开剧本看了看，发现了一张场景清单，也就是本题目的输入文件。

输入：输入文件的第一行包含用空格分隔的3个正整数，M, F和S。其中M代表剧中的男角色数目，取值在[1, 10]之间；F代表剧中的女角色数目，取值在[1, 10]之间；S代表剧中的场景数目，取值在[1, 100]之间。第二行和第三行分别列出了男角色和女角色的名字，每个名字都是一个英文字符串，名字之间有空格分隔。下面的S行分别描述了每个场景中出现的角色数和角色名（有空格分隔）。

输出：本剧需要的男女演员的最少数目，具体格式如下：

“You need x actors and y actresses” 其中x和y分别代表男、女演员的最少数目

示例

输入：

4 3 6

输出：

You need 3 actors and 2 actresses

Tarzan Jim John Tom

Lucy Cynthia Jane

3 Jim John Tom

2 Tarzan Lucy

2 Jane Cynthia

2 Jim Jane

2 Tarzan Jim

2 Tarzan Jane

试题2 设2n张扑克牌分别标记为1, 2, ..., n, n+1, ..., 2n，初始时这2n张牌按其标号从小到大排列。经一次洗牌后，原来的排列顺序变成n+1, 1, n+2, 2, ..., 2n, n。即前n张牌被放到偶数位置2, 4, ..., 2n，而后n张牌被放到奇数位置1, 3, ..., 2n-1。可以证明对于任何一个自然数n，经过若干次洗牌后可恢复初始状态。现在你的的任务是计算对于给定的n的值(n≤10^5)，最少需要经过多少次洗牌可恢复到初始状态。

输入输出格式

输入数据由多组数据组成。每组数据仅有一个整数，表示n的值。

对于每组数据，输出仅一行包含一个整数，即最少洗牌次数。

样例输入

10

样例输出

6

试题3：一年一度的面试又快要来临了。为了测试学生对树结构的认识，同时也检验他们的编程能力，学院面试的一项内容定为：要求学生们编程按编号顺序打印出节点个数不少于m的所有二叉树。

二叉树编号规则如下：

●仅有一个节点的树编号为1。

●当满足以下条件之一时，定义二叉树a的编号比b大：

  1. a的节点数比b多。

  2. 若a的节点数与b相等，且a的左子树编号比b的左子树大。

  3. a的节点数和左子树编号都和b相等，且a的右子树编号比b的右子树大。

二叉树的节点用大写X表示，例如：

当然当m较大时，检验答案对错的工作也是很繁重的，所以教授只打算对其中的若干个编号的二叉树进行抽查，他想麻烦你编制一个程序能够产生编号为n的二叉树的标准答案。

输入输出格式

输入数据由多组数据组成。每组数据仅一个整数，表示n (1≤n≤10^8)的值。输入数据以n=0表示结束，该数据不要处理。

对于每组数据，输出仅一行，即你求出的标准答案。

二叉树的输出格式为：

(左子树){若左子树为空则省略}X{根}(右子树){若右子树为空则省略}

其中{…}中的内容是说明，不必输出。例如，在上图中编号为5的树可表示为X((X)X)；编号为6的树表示为(X)X(X)。

样例输入

20

0

样例输出

((X)X(X))X