【试题七】
The Number of the Same BST
【Description】
Many people knows binary search tree. The keys in a binary search tree are always stored in such a way as to satisfy the BST property:
Let X be a node in a binary search tree. If Y is a node in the left subtree of X , then Y<= X. If Y is a node in the right subtree of X , then Y > X.
For example,
It is a binary search tree. And it can be built by inserting the elements of vector A= (12, 6, 3, 18, 20, 10, 4, 17, 20) sequentially. But it can also be built by the vector B= (12, 18, 17, 6, 20, 3, 10, 4, 20).
Now given a vector X, then you may get a binary search tree from X. Your job is to calculate how many different vectors can build the same binary search tree. To make it easy, you should just output the number of different vectors mod 9901.
【Input】
Input consists of several cases. Each case starts with a line containing one positive integer n, which is the length of test vector. The integer n is less than 20. Following this there will be n positive integers, which are less then 1000, on the next line. The input will end with a case starting with n = 0. This case should not be processed.
【Output】
For each test case, print a line with a single integer, which is the number of different vectors mod 9901.
【Sample Input】
3
2 1 3 9
5 6 3 18 20 10 4 17 20 0
【Sample output】
2 168
【试题八】
DNA Evolution
【Description】
Evolution is a seemingly random process which works in a way which resembles certain approaches we use to get approximate solutions to hard combinatorial problems. You are now to do something completely different.
Given a DNA string S from the alphabet {A,C,G,T}, find the minimal number of copy operations needed to create another string T. You may reverse the strings you copy, and copy both from S and the pieces of your partial T. You may put these pieces together at any time. You may only copy contiguous parts of your partial T, and all copied strings must be used in your final T.
Example: From S = ―ACTG‖ create T = ―GTACTAATAAT‖
1. 2. 3. 4. 5.
Get GT......... by copying and reversing \S. Get GTAC... by copying \S.
Get GTACTA….. by copying \l T.
Get GTACTAAT by copying and reversing \T. Get GTACTAATAAT by copying \T.
【Input】
The first line of input gives a single integer, 1 ≤ k ≤ 10, the number of test cases. Then follow, for each test case, a line with the string S , length of S is less then 19, and a line with the string T , length of T is less then 19.
【Output】
Output for each test case the number of copy operations needed to create T from S, or \
【Sample Input】
4 ACGT TGCA A C ACGT
TCGATCGA A
AAAAAAAAAAAAAAAAAA
【Sample output】
1
impossible 4 6
第三届河南省大学生程序设计竞赛
所有的题目 时间限制： 1秒
【T1】 房间安排
2010年上海世界博览会（Expo 2010），是第41届世界博览会。于2010年5月1日至10月31日期间，在中国上海市举行。本次世博会也是由中国举办的首届世界博览会。上海世博会以“城市，让生活更美好”（Better City, Better Life）为主题，将充分探索21世纪城市生活。
这次世博会总投资达450亿人民币，创造了世界博览会史上最大规模记录。吸引200个国家和国际组织参展。预计有7000万人次的参观者。
为了更好地接待在这期间来自世界各地的参观者，如何合理安排各宾馆的住房问题提到了日程。组委会已接到了大量的客房住宿定单，每张定单的内容包括要住宿的房间数，开始住宿时间和要
住的天数。为了便于整个城市各宾馆的管理，组委会希望对这些定单进行安排，目的是用尽可能少的房间来满足这些定单，以便空出更多的房间用于安排流动游客。
组委会请求DR. Kong来完成这个任务，对这些定单进行合理安排，使得满足这些定单要求的房间数最少。
假设：某个定单上的游客一旦被安排到某房间，在他预定住宿的期间内是不换房间的。为了简化描述，定单上的开始住宿时间为距离现在的第几天。例如，定单为（10，30，5）表示游客要求使用10个房间，第30天开始连住5天。 【标准输入】
第一行： N 表示定单数
接下来有N行，每行有三个整数 A B C 表示房间数，开始住宿时间和天数 【标准输出】
输出一个整数，为满足所有定单要求的最少房间数。 【约束条件】
1≤N≤10000 1≤A≤10，1≤B≤180， 1≤C≤10 【 样 例 】 标准输入 3 3 10 4 4 9 3 3 12 6
标准输出 7 素 数
走进世博园某信息通信馆，参观者将获得前所未有的尖端互动体验，一场充满创想和喜悦的信息通信互动体验秀将以全新形式呈现，从观众踏入展馆的第一步起，就将与手持终端密不可分，人类未来梦想的惊喜从参观者的掌上展开。
在等候区的梦想花园中，参观者便开始了他们奇妙的体验之旅，等待中的游客可利用手机等终端参与互动小游戏,与梦想剧场内的虚拟人物Kr. Kong进行猜数比赛。当屏幕出现一个整数X时，若你能比Kr. Kong更快的发出最接近它的素数答案，你将会获得一个意想不到的礼物。
例如：当屏幕出现22时，你的回答应是23；当屏幕出现8时，你的回答应是7；若X本身是素数，则回答X；若最接近X的素数有两个时，则回答大于它的素数。 【标准输入】
第一行： N 要竞猜的整数个数 接下来有N行， 每行有一个正整数 X
【标准输出】
输出有N行，每行是对应X的最接近它的素数。 【约束条件】
1≤N≤5 1≤X≤1000
【 样 例 】 标准输入 4 22 5 18 8 标准输出 23 5 19 7