竞赛题目.txt

这是学校ACM程序设计大赛的题目,拿出来大家算是当练习

问题一：木棒问题

输入文件：woods.in，标准输出

问题描述：

有一堆木棒，木棒数量为n，并且每一根木棒的长度和重量都是已知的。现在要将这些木棒逐个通过机器进行加工。机器在对木棒进行加工前需要用一些时间进行安装，包括机器的清洁、更换工具及调整形状。机器的安装时间由以下两方面决定：

（a）加工第一根木棒需要一分钟；

（b）加工完长度为l，重量为w的木棒后，再加工长度为l’和重量为w’的木棒，如果l<=l’且w<=w’，则机器将不需要安装时间，意即可以直接加工。否则需要一分钟时间重新安装机器。

你的任务就是对于给定的木棒数，寻找最少的机器安装时间。例如，如果有5根木棒，每根木棒用长度和重量构成的有序对表示，分别为(9，4)，(2，5)，(1，2)，(5，3)和(4，1)，则最少的机器安装时间为2分钟，即加工( 4 , 1 ) , ( 5 , 3 ) , ( 9 , 4 )前需要安装一分钟机器，加工( 1 , 2 ) , ( 2 , 5 )前需要安装一分钟。

输入：

输入包含若干个测试用例。第一行为给定的测试用例个数T(T<1000)，接下来的T个测试用例，每个测试用例占两行，第一行为一个正整数n(1<=n<=5000)，表示木棒数量，第二行为2n个正整数， ，每一个数最大值为10000， 分别表示第i木棒的长度和重量，这2n个正整数用一个或若干个空格隔开。

输出：

对每一个测试用例，用一行输出对应的最少的时间。

输入样例：

3 
5 
4 9 5 2 2 1 3 5 1 4 
3 
2 2 1 1 2 2 
3 
1 3 2 2 3 1 
输出样例：

2
1
3
 



问题二：谋士

输入文件：brainman.in，标准输出

 

背景：

Raymon疯狂地驱使着他的弟弟Charlie。最近，Raymon可以只用眼睛看洒落在地上的牙签而计算出其有246根，并且他也可能计算扑克牌。Charlie也喜欢做这种有趣的事情。他想以相类似的游戏来打击他的哥哥。

 

问题：

这就是Charlie所想的游戏。假设你得到了一串包含N个数的数列，目标是通过移动相邻的两个数，使得最后得到一串有序的数列。该游戏唯一的操作就是交换相邻的两个数。例如(swap为交换操作)：

开始数列为: 2 8 0 3 
swap (2 8) 8 2 0 3 
swap (2 0) 8 0 2 3 
swap (2 3) 8 0 3 2 
swap (8 0) 0 8 3 2 
swap (8 3) 0 3 8 2 
swap (8 2) 0 3 2 8 
swap (3 2) 0 2 3 8 
swap (3 8) 0 2 8 3 
swap (8 3) 0 2 3 8

因此，序列（2 8 0 3）可以经过9次交换相邻两个数而得到有序序列。

然而，也可以只通过3次交换操作就可以得到有序序列，例如：

开始数列为: 2 8 0 3 
swap (8 0) 2 0 8 3 
swap (2 0) 0 2 8 3 
swap (8 3) 0 2 3 8

于是，该问题就成了：对于给定的数列，最少需要通过多少次交换而得到有序序列？既然Charlie没有Raymond聪明，他决定去打击Raymond。这就是要你来的原因，他希望你写一个程序解决这问题。

输入：

第一行为测试用例（scenarios）的个数T（T<100）。

接下来的每一个测试用例占用一行，每行的第一个数为N（1<=N<=1000）表示序列的长度，然后就是表示序列的N个数，每一个数为[-1000000, 1000000]内的整数。每一行数之间由一个空格隔开。

输出：

对于每一个测试用例，用一行输出“Scenario #i:”，i表示测试用例序号，起始为1，然后用一行输出结果，即排成有序序列所需用的交换相邻两数的最少次数。

样例输入：

4
4 2 8 0 3
10 0 1 2 3 4 5 6 7 8 9
6 -42 23 6 28 -100 65537
5 0 0 0 0 0
样例输出：

Scenario #1:
3
 
Scenario #2:
0
 
Scenario #3:
5
 
Scenario #4:
0
 



问题三：Polynomial Remains

输入文件：Polyn.in，标准输出


描述：

给定的多项式如下：a(x) = anxn + ... + a1 x + a0, 

计算该多项多除以xk+1后的余数r(x)

输入：

输入包含若干个用例，每个用例包含两行，其中第一行为两个整数n和k（0 <= n, k <= 10000）表示多项式的最高次幂和除数项的最高次幂。第二行包含n+1个整数，代表被除数项的各项系数，排序顺序为a0到an，即第一个数为常数项，最后一个数为最高次幂的系数。当n=k=-1时，表示输入结束。

输出：

对每一个用例，用一行输出余数的系数，要求从r0开始，即先输出常数项，依次到最高项的系数。如果余数为0，则只输出常数项r0，否则输出项数为d+1,其中d为余数项的最高次幂。系数项之间用一个空格隔开。

你可以假定余数的系数项都可用32位的整数表示。

样例输入：

5 2
6 3 3 2 0 1
5 2
0 0 3 2 0 1
4 1
1 4 1 1 1
6 3
2 3 -3 4 1 0 1
1 0
5 1
0 0
7
3 5
1 2 3 4
-1 -1
样例输出：

3 2
-3 -1
-2
-1 2 -3
0
0
1 2 3 4
 



问题四：Look and Say

看和说

输入文件：LookSay.in，标准输出

Description

描述：

看和说序列定义如下：在序列中数字串从第一个数字开始，每一个字串可以用说的方式描述。例如：原数字串“122344111”可以说成一个1，两个2，一个3，两个4，三个1，因此，原数字串“122344111”可以说成1122132431。同理，“1111111111”可以说成十个1，表示为101。注意：说的串不一定唯一地表示一个串，例如原数字串为“12234411□1”(□为空格)也可以说成1122132431

输入：

输入的第一行为用例个数n，接下来n行的每一行为一个用例。每行最多1000个数字。

输出：

对每一个用例，输出对应的说的串。

样例输入：

3
12234□4111
11111□□1□1111
12345
样例输出：

1122132431
101
1112131415
 



问题五：Faster, Higher, Stronger

 

2008年8月，第29届奥林匹克运动会将在北京隆重举行，这意味着中国的繁荣，以及北京奥林匹克运动会将是全世界人民共同的盛宴。

奥林匹克运动会的主题是"Citius, Altius, Fortius",其意思是"Faster, Higher, Stronger"。


在本题中，有许多奥林匹克运动会的各项比赛记录，你的任务是找出哪个是最快的，哪个是最高的，哪个是最强的。

输入：

从文件“FasterHS.in”输入数据，文件包含了很多行，第一行是一个整数M表示有M个测试用例，接下来是M个测试用例的具体数据，每个测试用例有3行的数据，第一行是记录的类型，可能是"Faster"、"Higher" 或"Stronger"中的任一一种类型；第二行是一个整数N，表示测试用例的具体记录的个数；第三行是N个非负整数，表示具体比赛记录。

输出：

把结果输出到文件“FasterHS.out”。输出文件每行是一个测试用例的结果，如果记录的类型是"Faster"，表示记录数据是时间记录，你应该输出最快的那个记录；如果记录的类型是" Higher "，表示记录数据是跳高记录，你应该输出最高的那个记录；如果记录的类型是" Stronger "，表示记录数据是举重记录，你应该输出最重的那个记录。

输入样例：

3
Faster
3
10 11 12
Higher
4
3 5 4 2
Stronger
2
200 200
输出样例：

10
5
200
 



问题六：Solving Equation

CNS is a good student with good moral. But he is not very good at arithmetic because he has some trouble with his IQ, especially in solving equation. Although he can solve equations such as 2x = 2 with skill and ease, he can not manage equations such as {x + y = 3; x - y = 1}. So he wants you to help him. We guarantee that all equations are linear equations all the work can be done in the range of int.

Input
The first line of input file “sequ.in” is a integer M(M≤100) showing the number of cases. In each case, the first line is a integer N(1 ≤ N ≤ 100) indicating the number of unknown numbers and it's also the number of equations. 

From the second line to the N+1th line, each line contains N+1 numbers. The first N numbers indicate the coefficients of N unknown numbers. The N+1th number indicate the number on the right side of the equation. 

Output
Output file “sequ.out” contains M lines,For each case print in a single line with N numbers indicating the value of the N unknown numbers. 

Sample Input
2
2
1  1  3
1 -1  1
3
1 1 1 4
1 2 –2 1
2 –1 1 7
Sample Output
2 1
3 0 1
 



问题七：数字金字塔问题

问题描述：

给定一个由N行数字组成的数字金字塔，如下图所示，现在要你从该数字金字塔的顶到底找出一条路径，使得该路径经过的数字总和最大。

7
3  8
8  1  0
2  7  4  4
4  5  2  6  5
 

数据输入：

由文件szjzt.in提供输入数据，文件的第一行是测试用例的个数M，接着是每个测试用例的具体数据内容，每个测试用例的第一行是一个数字N，表示数字金字塔的层数为N层，接下来的N行是数字金字塔的每层的具体数字，K层有K个数字。每个数字不超过10000.

 

结果输出：

将计算的结果输出到文件szjzt.out中，每行一个数字，M行的数字表示是测试用例M的计算结果。

 

输入样例：

3
5
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5
2
2
2 3
3
1
2 3
4 5 6
 

输出样例：

30
5
10
 



问题八：渊子赛马

题目描述:

赛马是一古老的游戏，早在公元前四世纪的中国，处在诸侯割据的状态，历史上称为“战国时期”。在魏国作官的孙膑，因为受到同僚庞涓的迫害，被齐国使臣救出后，到达齐国国都。 

赛马是当时最受齐国贵族欢迎的娱乐项目。上至国王，下到大臣，常常以赛马取乐，并以重金赌输赢。田忌多次与国王及其他大臣赌输赢，屡赌屡输。一天他赛马又输了，回家后闷闷不乐。孙膑安慰他说：“下次有机会带我到马场看看，也许我能帮你。” 

孙膑仔细观察后发现，田忌的马和其他人的马相差并不远，只是策略运用不当，以致失败。

比赛前田忌按照孙膑的主意，用上等马鞍将下等马装饰起来，冒充上等马，与齐王的上等马比赛。第二场比赛，还是按照孙膑的安排，田忌用自己的上等马与国王的中等马比赛，在一片喝彩中，只见田忌的马竟然冲到齐王的马前面，赢了第二场。关键的第三场，田忌的中等马和国王的下等马比赛，田忌的马又一次冲到国王的马前面，结果二比一，田忌赢了国王。 

就是这么简单，现在渊子也来赛一赛马。假设每匹马都有恒定的速度，所以速度大的马一定比速度小的马先到终点（没有意外！！）。不允许出现平局。最后谁赢的场数多于一半(不包括一半)，谁就是赢家(可能没有赢家)。渊子有N (1≤N≤1000)匹马参加比赛。对手的马的数量与渊子马的数量一样，并且知道所有的马的速度。聪明的你来预测一下这场世纪之战的结果，看看渊子能否赢得比赛。 

输入描述:

输入有多组测试数据。

每组测试数据包括3行：

第一行输入N(1≤N≤1000)。表示马的数量。

第二行有N个整型数字，即渊子的N匹马的速度。

第三行有N个整型数字，即对手的N匹马的速度。

当N为0时退出。

输出描述:

若通过聪明的你精心安排，如果渊子能赢得比赛，那么输出“YES”。

否则输出“NO”。

样例输入:

5
2 3 3 4 5
1 2 3 4 5
4
2 2 1 2 
2 2 3 1
0  
样例输出:

YES
NO