ACM练习题 - 图文

ACM练习题

（1）描述

浙江工商大学校园里绿树成荫，环境非常舒适，因此也引来一批动物朋友来此居住。

童心未泯的redraiment就经常带些碎面包什么的去广场喂鸽子和兔子，并和它们玩耍。一点也不像大学生，还是一副老不正经的样子，呵呵。

随着鸽子和兔子数目的增多，redraiment带的那点食物已经不够它们瓜分了。为了能让自己的好朋友吃的饱饱的，redraiment决定统计一下有多少只鸽子和有多少只兔子，以便带来足够的食物。一、二、三、四、五...他开始数了。

现在，他已经知道有这些鸽子和兔子一共有n个头和m只脚。请你帮他写个程序计算一下一共有多少只鸽子和兔子。 输入

输入包括多组数据。

每行包括2个数据：n、m(代表上面题目中提到的意思1≤n, m≤230)。 n、m都是整数。 输入以0 0作为结束。 输出

每组数据的输出都只有一行，分别是鸽子的数量和兔子数量。

如果输入的测试数据不能求得结果，那肯定是redraiment这个马大哈数错了，就输出\提示他。 样例输入 35 94 1 3 0 0 样例输出 23 12 Error

（2）念数字

时间限制(普通/Java):1000MS/10000MS 运行内存限制:65536KByte

总提交: 727 测试通过: 316 描述

编一个“念数字”的程序，它能让计算机完成以下工作：当你输入一个０至99 之 间的数后，计算机就会用汉语拼音印出这个数。

如果输入的数不在0到99 之间，就印出“CUO LE”。

注：为了使不熟悉汉语拼音的同学也能做这个题，把“零，一，二，三，……，九，十”的

拼音法写在下面。

零 LING 一 YI 二 ER 三 SAN 四 SI 五 WU 六 LIU 七 QI 八 BA 九 JIU 十 SHI 输入

输入数据有多组，每组数据占一行，内容为一个数字，数据以EOF作为结束。 输出

输出对应的汉语拼音，字母全部为大写。每组数据占一行 样例输入 35 0 11 100 样例输出 SAN SHI WU LING SHI YI CUO LE

（3）University

时间限制(普通/Java):1000MS/10000MS 运行内存限制:65536KByte

总提交: 698 测试通过: 304 描述

在大学里，很多单词都是一词多义，偶尔在文章里还要用引申义。这困扰Redraiment很长的时间。

他开始搜集那些单词的所有意义。他发现了一些规律，例如

“a”能用“e”来代替, “c”能用“f”来代替……

现在他给出了字母的替换规则，如下所示，A被E替换，B被C替换，依次类推。

A B C D E F G H I J K L M N O P Q R S T U V W X Y Z

E C F A J K L B D G H I V W Z Y M N O P Q R S T U X

a b c d e f g h i j k l m n o p q r s t u v w x y z

e r w q t y g h b n u i o p s j k d l f a z x c v m 输入

本题包括多组测试数据。

每组测试数据为一行：为仅由字母和空格组成的字符串(空格不变)。 输入以单行“#”结束。 输出

对应每组测试数据，替换后输出它的引申义。 样例输入 Ilttabaje zaujljg # 样例输出 Different meaning

（4）Least Common Multiple

时间限制(普通/Java):1000MS/10000MS 运行内存限制:65536KByte

总提交: 956 测试通过: 335 描述

求n个数的最小公倍数。 输入

输入包含多个测试实例，每个测试实例的开始是一个正整数n，然后是n个正整数。 输出

为每组测试数据输出它们的最小公倍数，每个测试实例的输出占一行。你可以假设最后的输出是一个32位的整数。 样例输入 2 4 6 3 2 5 7 样例输出 12 70

（5）求奇数的乘积

时间限制(普通/Java):1000MS/10000MS 运行内存限制:65536KByte

总提交: 1049 测试通过: 577 描述

给你n个整数，求他们中所有奇数的乘积。 输入

输入数据包含多个测试实例，每个测试实例占一行，每行的第一个数为n，表示本组数据一共有n个，接着是n个整数，你可以假设每组数据必定至少存在一个奇数。 输出

输出每组数中的所有奇数的乘积，对于测试实例，输出一行。 样例输入 3 1 2 3 4 2 3 4 5 样例输出 3

15

（6）平方和与立方和

时间限制(普通/Java):1000MS/10000MS 运行内存限制:65536KByte

总提交: 1377 测试通过: 469 描述

给定一段连续的整数，求出他们中所有偶数的平方和以及所有奇数的立方和。 输入

输入数据包含多组测试实例，每组测试实例包含一行，由两个整数m和n组成。 输出

对于每组输入数据，输出一行，应包括两个整数x和y，分别表示该段连续的整数中所有偶数的平方和以及所有奇数的立方和。 你可以认为32位整数足以保存结果。 样例输入 1 3 2 5 样例输出 4 28 20 152

（7）绝对值排序

时间限制(普通/Java):1000MS/10000MS 运行内存限制:65536KByte

总提交: 1008 测试通过: 555 描述

输入n(n<=100)个整数，按照绝对值从大到小排序后输出。题目保证对于每一个测试实例，所有的数的绝对值都不相等。 输入

输入数据有多组，每组占一行，每行的第一个数字为n,接着是n个整数，n=0表示输入数据的结束，不做处理。 输出

对于每个测试实例，输出排序后的结果，两个数之间用一个空格隔开。每个测试实例占一行。 样例输入 3 3 -4 2 4 0 1 2 -3 0 样例输出 -4 3 2 -3 2 1 0

（8）JudgeOnline

时间限制(普通/Java):1000MS/10000MS 运行内存限制:65536KByte

总提交: 440 测试通过: 202 描述

TZC终于也要有自己的JudgeOnline了！

但浏览器是不能直接显示一些特殊字符的。为了把选手的代码显示给大家看，需要把一些特殊的符号换成HTML标签。

比如:

1.'<'需要换成 \

2.'>'需要换成 \

3.' '(空格)需要换成 \

4.' '(TAB符)需要换成 \

5.其他字符保持不变。

现在请你来完成这项工作。

输入

输入一段代码(可能有多行)，把里面的符号按上面的规则替换掉。 输出

输出替换好的代码。 样例输入

#include

int main(void) { return 0; } 样例输出

#include

int main(void) { return 0; }

（9）蟠桃记

时间限制(普通/Java):1000MS/10000MS 运行内存限制:65536KByte

总提交: 808 测试通过: 505 描述

孙悟空在大闹蟠桃园的时候，第一天吃掉了所有桃子总数一半多一个，第二天又将剩下的桃子吃掉一半多一个，以后每天吃掉前一天剩下的一半多一个，到第n天准备吃的时候只剩下一个桃子。这下可把神仙们心疼坏了，请帮忙计算一下，第一天开始吃的时候桃子一共有多少个桃子。 输入

输入数据有多组，每组占一行，包含一个正整数n（1≤n≤30），表示只剩下一个桃子的时候是在第n天发生的。 输入以0结束。 输出

对于每组输入数据，输出第一天开始吃的时候桃子的总数，每个测试实例占一行。 样例输入 2 4 0 样例输出 4 22

（10）C语言实验题——三个整数

时间限制(普通/Java):1000MS/10000MS 运行内存限制:65536KByte

总提交: 3683 测试通过: 1494 描述

给出三个整数，请你设计一个程序，求出这三个数的和、乘积和平均数。 输入

输入只有三个正整数a、b、c。 输出

输出一行，包括三个的和、乘积、平均数。

数据之间用一个空格隔开，其中平均数保留小数后面两位。 样例输入 1 2 3 样例输出 6 6 2.00

（11）C语言实验题——大小写转换

时间限制(普通/Java):1000MS/10000MS 运行内存限制:65536KByte

总提交: 1326 测试通过: 798

描述

把一个字符串里所有的大写字母换成小写字母，小写字母换成大写字母。其他字符保持不变。 输入

输入为一行字符串，其中不含空格。长度不超过80个字符。 输出

输出转换好的字符串。 样例输入 ABCDefgh123 样例输出 abcdEFGH123

（12）C语言实验题——分数序列

时间限制(普通/Java):1000MS/10000MS 运行内存限制:65536KByte

总提交: 1916 测试通过: 1033 描述

有一个分数序列：2/1, 3/2, 5/3, 8/5, 13/8, …编写程序求出这个序列的前n项之和。 输入

输入只有一个正整数n，1≤n≤10。 输出

输出改序列前n项和，结果保留小数后6位。 样例输入 3 样例输出 5.166667

提示

结果需要用double类型来保存。

（13）C语言实验题——最值

时间限制(普通/Java):1000MS/10000MS 运行内存限制:65536KByte

总提交: 2507 测试通过: 614 描述

有一个长度为n的整数序列。请写一个程序，把序列中的最小值与第一个数交换，最大值与最后一个数交换。输出转换好的序列。 输入

输入包括两行。

第一行为正整数n（1≤n≤10）。 第二行为n个正整数组成的序列。 输出

输出转换好的序列。数据之间用空格隔开。 样例输入 5

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

（14）C语言实验题——时间间隔

时间限制(普通/Java):1000MS/10000MS 运行内存限制:65536KByte

总提交: 1373 测试通过: 513 描述

从键盘输入两个时间点(24小时制），输出两个时间点之间的时间间隔，时间间隔用“小时:分钟:秒”表示。 输入

输入包括两行。 第一行为时间点1。 第二行为时间点2。 输出

以“小时:分钟:秒”的格式输出时间间隔。 格式参看输入输出。 样例输入 12:01:12 13:09:43 样例输出 1:08:31

（15）C语言实验题——分割整数

时间限制(普通/Java):1000MS/10000MS 运行内存限制:65536KByte

总提交: 840 测试通过: 540 描述

从键盘输入一个长正整数（不超过10位），从高位开始逐位分割并输出。 输入

正整数n，不含前导零。 输出

分割的整数序列，各整数之间用空格格开。 注意，最后一个数字后面没有空格！ 样例输入 654321 样例输出 6 5 4 3 2 1

（16）C语言实验题——删除指定字符

时间限制(普通/Java):1000MS/10000MS 运行内存限制:65536KByte

总提交: 163 测试通过: 76 描述

从键盘输入一个字符串给str和一个字符给c，删除str中的所有字符c并输出删除后的字符串str。 输入

第一行是一个字符串； 第二行是一个字符。 输出

删除指定字符后的字符串。 样例输入 sdf$$$sdf$$ $ 样例输出 sdfsdf

（17）C语言实验题——单词统计

时间限制(普通/Java):1000MS/10000MS 运行内存限制:65536KByte

总提交: 169 测试通过: 85 描述

从键盘输入一行字符，统计其中单词的个数，各单词以空格分隔，且空格数可以是多个。 输入

输入只有一行句子。仅有空格和英文字母构成。 输出

单词的个数。 样例输入

stable marriage problem Consists of Matching members 样例输出 7

（18）C语言实验题——打印菱形

时间限制(普通/Java):1000MS/10000MS 运行内存限制:65536KByte

总提交: 2093 测试通过: 1056 描述

从键盘输入一个整数n(1≤n≤9)，打印出指定的菱形。 输入

正整数n（1≤n≤9）。 输出

指定的菱形。

第一行前面有n-1个空格，第二行有n-2个空格，以此类推。 样例输入 5 样例输出 * *** ***** ******* ********* ******* ***** *** *

（19）C语言实验题——字符逆序

时间限制(普通/Java):1000MS/10000MS 运行内存限制:65536KByte

总提交: 1560 测试通过: 898 描述

将一个字符串str的内容颠倒过来，并输出。str的长度不超过100个字符。 输入

输入包括一行。

第一行输入的字符串。 输出

输出转换好的逆序字符串。 样例输入 I am a student 样例输出 tneduts a ma I

（20）C语言实验题——矩阵下三角元素之和

时间限制(普通/Java):1000MS/10000MS 运行内存限制:65536KByte

总提交: 110 测试通过: 74 描述

输入一个正整数n（1 < =n <= 10),再输入n*n的矩阵，要求求该矩阵的下三角元素之和。 输入

输入包括n+1行 第一行为整数：n

接下来的n行为矩阵数据 输出

矩阵的下三角元素之和 样例输入 5

1 2 3 4 5 2 3 4 5 6 3 4 5 6 7 4 5 6 7 8 5 6 7 8 9 样例输出 75

（21）To and Fro

时间限制(普通/Java):1000MS/10000MS 运行内存限制:65536KByte

总提交: 127 测试通过: 99 描述

Mo and Larry have devised a way of encrypting messages. They first decide secretly on the number of columns and write the message (letters only) down the columns, padding with extra random letters so as to make a rectangular array of letters. For example, if the message is “There?s no place like home on a snowy night” and there are five columns, Mo would write down

t o i o y h p k n n e l e a i r a h s g e c o n h s e m o t n l e w x

Note that Mo includes only letters and writes them all in lower case. In this example, Mo used the character ?x? to pad the message out to make a rectangle, although he could have used any letter.

Mo then sends the message to Larry by writing the letters in each row, alternating left-to-right and right-to-left. So, the above would be encrypted as

toioynnkpheleaigshareconhtomesnlewx

Your job is to recover for Larry the original message (along with any extra padding letters) from the encrypted one. 输入

There will be multiple input sets. Input for each set will consist of two lines. The first line will contain an integer in the range 2. . . 20 indicating the number of columns used. The next line is a string of up to 400 lower case letters. The last input set is followed by a line containing a single 0, indicating end of input. 输出

Each input set should generate one line of output, giving the original plaintext message, with no spaces. 样例输入

5

toioynnkpheleaigshareconhtomesnlewx 3

ttyohhieneesiaabss 0 样例输出

theresnoplacelikehomeonasnowynightx thisistheeasyoneab

（22）最大连续子序列

时间限制(普通/Java):1000MS/10000MS 运行内存限制:65536KByte

总提交: 401 测试通过: 123 描述

给定K个整数的序列{ N1, N2, ..., NK }，其任意连续子序列可表示为{ Ni, Ni+1, ...,

Nj }，其中 1 <= i <= j <= K。最大连续子序列是所有连续子序列中元素和最大的一个，

例如给定序列{ -2, 11, -4, 13, -5, -2 }，其最大连续子序列为{ 11, -4, 13 }，最大和 为20。

在今年的数据结构考卷中，要求编写程序得到最大和，现在增加一个要求，即还

需要输出该

子序列的第一个和最后一个元素。 输入

测试输入包含若干测试用例，每个测试用例占2行，第1行给出正整数K( < 10000 )，第2行给出K个整数，中间用空格分隔。当K为0时，输入结束，该用例不被处理。 输出

对每个测试用例，在1行里输出最大和、最大连续子序列的第一个和最后一个元 素，中间用空格分隔。如果最大连续子序列不唯一，则输出序号i和j最小的那个（如输入样例的第2、3组）。若所有K个元素都是负数，则定义其最大和为0，输出整个序列的首尾元素。 样例输入

6

-2 11 -4 13 -5 -2 10

-10 1 2 3 4 -5 -23 3 7 -21 6

5 -8 3 2 5 0 1 10 3

-1 -5 -2 3

-1 0 -2 0 样例输出 20 11 13 10 1 4 10 3 5 10 10 10 0 -1 -2 0 0 0

（23）开门人和关门人

时间限制(普通/Java):1000MS/10000MS 运行内存限制:65536KByte

总提交: 166 测试通过: 79 描述

每天第一个到机房的人要把门打开，最后一个离开的人要把门关好。现有一堆杂乱的机房签到、签离记录，请根据记录找出当天开门和关门的人。 输入

测试输入的第一行给出记录的总天数N ( > 0 )。下面列出了N天的记录。每天的记录在第一行给出记录的条目数M ( 0

证件号码 签到时间 签离时间

其中时间按“小时:分钟:秒钟”（各占2位）给出，证件号码是长度不超过15的字符串。 输出

对每一天的记录输出1行，即当天开门和关门人的证件号码，中间用1空格分隔。注意：在裁判的标准测试输入中，所有记录保证完整，每个人的签到时间在签离时间之前，且没有多人同时签到或者签离的情况 样例输入

3 1

ME3021112225321 00:00:00 23:59:59 2

EE301218 08:05:35 20:56:35 MA301134 12:35:45 21:40:42 3

CS301111 15:30:28 17:00:10 SC3021234 08:00:00 11:25:25 CS301133 21:45:00 21:58:40 样例输出

ME3021112225321 ME3021112225321 EE301218 MA301134 SC3021234 CS301133

（24）回文数猜想

时间限制(普通/Java):1000MS/10000MS 运行内存限制:65536KByte

总提交: 9 测试通过: 7 描述

一个正整数，如果从左向右读（称之为正序数）和从右向左读（称之为倒序数）是一样的，这样的数就叫回文数。任取一个正整数，如果不是回文数，将该数与他的倒序数相加，若其和不是回文数，则重复上述步骤，一直到获得回文数为止。例如：68变成154（68+86），再变成605（154+451），最后变成1111（605+506），而1111是回文数。于是有数学家提出一个猜想：不论开始是什么正整数，在经过有限次正序数和倒序数相加的步骤后，都会得到一个回文数。至今为止还不知道这个猜想是对还是错。现在请你编程序验证之。 输入

每行一个正整数。

特别说明：输入的数据保证中间结果小于2^31。 输出

对应每个输入，输出两行，一行是变换的次数，一行是变换的过程。 样例输入 27228 37649 样例输出

3

27228--->109500--->115401--->219912 2

37649--->132322--->355553

（25）三角形

时间限制(普通/Java):1000MS/10000MS 运行内存限制:65536KByte

总提交: 283 测试通过: 189 描述

用N个三角形最多可以把平面分成几个区域? 输入

输入数据的第一行是一个正整数T(1<=T<=10000),表示测试数据的数量.然后是T组测试数据,每组测试数据只包含一个正整数N(1<=N<=10000). 输出

对于每组测试数据,请输出题目中要求的结果. 样例输入 2 1 2 样例输出 2 8

（26）三角形面积

时间限制(普通/Java):1000MS/10000MS 运行内存限制:65536KByte

总提交: 796 测试通过: 545 描述

给出三角形的三边的边长，求三角形的面积。 输入

输入数据分多组，每组占一行，每行输入三边边长，以空格隔开。输入以EOF结束。 输出

每行输出三角形的面积。精确到三位小数。 样例输入 1 2 2.5 3 4 4.5 5 6 6.5 样例输出 0.950

5.881 14.249

（27）求两直线的夹角

时间限制(普通/Java):1000MS/10000MS 运行内存限制:65536KByte

总提交: 424 测试通过: 177 描述

有两条直线，AB和CD，A、B、C、D的坐标已知，求这两条直线的所成夹角中较小的一个。 输入

输入包括多组数据，第一行为测试数据的组数n，接下来后面有n行，每一行有8个整数，依次代表A点的x坐标、A点的y坐标，B点的x坐标、B点的y坐标，C点的x坐标、C点的y坐标，D点的x坐标、D点的y坐标。 输出

输出夹角的近似值（角度值而非弧度值，保留1位小数）。 样例输入 2

0 0 0 1 0 0 1 0 0 0 1 1 1 1 1 0 样例输出 90.0 45.0

（28）等值数目

时间限制(普通/Java):1000MS/10000MS 运行内存限制:65536KByte

总提交: 685 测试通过: 284 描述

已知两个整数数组f[]和g[]，它们的元素都已经从小到大排列。例如f[]中可能有1，2，2，3，3，g[]中有1，2，2，2，3。

请写一个程序，算出这两个数组彼此之间有多少组相同的数据。就以上例而言:

f[0]于g[0]是第一组； f[1]于g[1]是第二组； f[2]于g[2]是第三组； f[3]于g[4]是第四组。 输入

第一行为两个整数m, n(1≤m, n≤1000)，分别代表数组f[], g[]的长度。 第二行有m个元素，为数组f[]。 第三行有n个元素，为数组g[]。 输出

输出等值数目。 样例输入 5 5

1 2 2 2 3 1 2 2 3 3 样例输出 4

（29）猴子分桃

时间限制(普通/Java):1000MS/10000MS 运行内存限制:65536KByte

总提交: 369 测试通过: 142 描述

老猴子辛苦了一辈子，给那群小猴子们留下了一笔巨大的财富——一大堆桃子。老猴子决定把这些桃子分给小猴子。

第一个猴子来了，它把桃子分成五堆，五堆一样多，但还多出一个。它把剩下的一个留给老猴子，自己拿走其中的一堆。

第二个猴子来了，它把桃子分成五堆，五堆一样多，但又多出一个。它把多出的一个留给老猴子，自己拿走其中的一堆。

后来的小猴子都如此照办。最后剩下的桃子全部留给老猴子。

这里有n只小猴子，请你写个程序计算一下在开始时至少有多少个桃子，以及最后老猴子最少能得到几个桃子。 输入

输入包括多组测试数据。

每组测试数据包括一个整数n(1≤n≤20)。 输入以0结束，该行不做处理。 输出

每组测试数据对应一行输出。 包括两个整数a，b。

分别代表开始时最小需要的桃子数，和结束后老猴子最少能得到的桃子数。 样例输入 5 1 0 样例输出 3121 1025 1 1

（30）Calculate a + b

TimeLimit: 1 Second MemoryLimit: 32 Megabyte Totalsubmit: 9975 Accepted: 4380 Description Calculate a + b Input

The input will consist of a series of pairs of integers a and b,separated by a space, one pair of integers per line. Output

For each pair of input integers a and b you should output the sum of a and b in one line,and with one line of output for each line in input.

Sample Input 1 5

Sample Output 6

（31）Forests

TimeLimit: 1 Second MemoryLimit: 32 Megabyte Totalsubmit: 1737 Accepted: 364 Description

If a tree falls in the forest, and there's nobody there to hear, does it make a sound? This classic conundrum was coined by George Berkeley (1685-1753), the Bishop and influential Irish philosopher whose primary philosophical achievement is the advancement of what has come to be called subjective idealism. He wrote a number of works, of which the most widely-read are Treatise Concerning the Principles of Human Knowledge (1710) and Three Dialogues between Hylas and Philonous (1713) (Philonous, the \Input

A forest contains T trees numbered from 1 to T and P people numbered from 1 to P. Standard input consists of a line containing P and T followed by several lines, containing a pair of integers i and j, indicating that person i has heard tree j fall. People may have different opinions as to which trees, according to Berkeley, have made a sound.

Input contains multiple test cases. Subsequent test cases are separated with a single blank line. Output

How many different opinions are represented in the input? Two people hold the same opinion only if they hear exactly the same set of trees. You may assume that P < 100 and T < 100. Sample Input 3 4 1 2

3 3 1 3 2 2 3 2 2 4

Sample Output 2

（32）A Star not a Tree?

TimeLimit: 1 Second MemoryLimit: 32 Megabyte Totalsubmit: 504 Accepted: 174 Description

Luke wants to upgrade his home computer network from 10mbs to 100mbs. His existing network uses 10base2 (coaxial) cables that allow you to connect any number of computers together in a linear arrangement. Luke is

particulary proud that he solved a nasty NP-complete problem in order to minimize the total cable length.

Unfortunately, Luke cannot use his existing cabling. The 100mbs system uses 100baseT (twisted pair) cables. Each 100baseT cable connects only two devices: either two network cards or a network card and a hub. (A hub is an electronic device that interconnects several cables.) Luke has a choice: He can buy 2N-2 network cards and connect his N computers together by inserting one or more cards into each computer and connecting them all together. Or he can buy N network cards and a hub and connect each of his N computers to the hub. The first approach would require that Luke configure his operating system to forward network traffic. However, with the installation of Winux 2007.2, Luke discovered that network forwarding no longer worked. He couldn't figure out how to re-enable forwarding, and he had never heard of Prim or Kruskal, so he settled on the second approach: N network cards and a hub.

Luke lives in a loft and so is prepared to run the cables and place the hub anywhere. But he won't move his computers. He wants to minimize the total length of cable he must buy. Input

The first line of input contains a positive integer N <= 100, the number of computers. N lines follow; each gives the (x,y) coordinates (in mm.) of a computer within the room. All coordinates are integers between 0 and 10,000. Output

Output consists of one number, the total length of the cable segments, rounded to the nearest mm. Sample Input 4 0 0

0 10000 10000 10000 10000 0 Sample Output 28284 （33）Trains

TimeLimit: 1 Second MemoryLimit: 32 Megabyte Totalsubmit: 10 Accepted: 6 Description

Trains are cool. You can get pretty much anywhere in Europe on a train, including little towns. In Canada, train service is not quite as good. Sometimes you have to change trains many times, and it's often hard to know the quickest route and where to switch. Depending on the time of day, the route may even pass through completely different cities. Fortunately, you can write a program to help you. Given the schedules of trains running between different places, your task is to find all the shortest

connections between two places. A shortest connection is one for which there is no other connection that would allow you to leave later and arrive at the same time or earlier, or leave at the same time and arrive earlier. Time to change trains need not be considered, as it is already built into the schedule. Input

The first line of input contains a positive integer N, the number of test cases. The first line of each test case contains T <= 20, the number of train routes. Each train route is described by one or more lines containing:

S <= 20 The number of stations on the route including origin and terminus.

? hh:mm The starting time of the route (in 24-hour clock notation; that is, in the range 00:00 to 23:59). You may assume that a train leaves the origin every day at this time. A station name is a string of no more than 40 alphabetic characters.

? A list of the names of the S stations, separated by the travel time between adjacent stations. Travel time is given in hours and minutes.

?

Finally, each test case gives the name of an origin and destination for which a schedule is to be generated. You may assume there is at least one route from the specified origin to the specified destination. Output

The output consists of a list of shortest connection departure and travel times from the origin to the destination, ordered by departure time. Each combination of departure and travel time should be listed only once, even if there are multiple routings yielding the same connection times. The departure time should be given as hh:mm (that is, exactly 2 digits each). Travel time on the other hand should be given as h:mm, hh:mm, hhh:mm, etc., as appropriate to avoid unnecessary leading 0's. Leave an empty line between the output for successive test cases.

For example, the first route in the sample input begins in Windsor at 08:00 a.m., arrives in London at 09:55, in Kitchener at 11:30, Guelph at 12:25, Toronto at 13:30 and Montreal at 18:20. To get from Waterloo to Toronto we can leave at 07:00 and travel direct for a total time of 1:45. Or we can leave at 08:00 and travel to Kitchener, then to Guelph and Toronto, arriving at 13:30 for a travel time of 5:30. Or we can depart Waterloo at 09:00 for Hamilton, Niagara, and Toronto, arriving at 14:00. Finally, we can depart Waterloo at 23:00 and arrive in Toronto at 07:05 the next morning, for a travel time of 8:05. Sample Input

1 7

6 08:00 Windsor 1:55 London 1:35 Kitchener 0:55 Guelph 1:05 Toronto 4:50

Montreal

2 08:00 Waterloo 0:45 Kitchener

3 09:00 Waterloo 1:45 Hamilton 1:05 Niagara 2 12:00 Niagara 2:00 Toronto 2 07:00 Waterloo 1:45 Toronto 2 23:00 Waterloo 0:55 Guelph 2 06:00 Guelph 1:05 Toronto Waterloo Toronto Sample Output

07:00 1:45 08:00 5:30 09:00 5:00 23:00 8:05

（34）Temple of Dune

TimeLimit: 1 Second MemoryLimit: 32 Megabyte Totalsubmit: 64 Accepted: 37 Description

The Archaeologists of the Current Millenium (ACM) now and then discover ancient artifacts located at the vertices of regular polygons. In general it is necessary to move one sand dune to uncover each artifact. After discovering three artifacts, the archaeologists wish to compute the minimum number of dunes that must be moved to uncover all of them. Input

The first line of input contains a positive integer n, the number of test cases. Each test case consists of three pairs of real numbers giving the x and y coordinates of three vertices from a regular polygon. Output

For each line of input, output a single integer stating the fewest vertices that such a polygon might have.

You may assume that each input case gives three distinct vertices of a regular polygon with at most 200 vertices.

Sample Input

4

10.00000 0.00000 0.00000 -10.00000 -10.00000 0.00000 22.23086 0.42320 -4.87328 11.92822 1.76914 27.57680

156.71567 -13.63236 139.03195 -22.04236 137.96925 -11.70517

129.400249 -44.695226 122.278798 -53.696996 44.828427 -83.507917 Sample Output 4 6 23 100

（35）Relatives

TimeLimit: 1 Second MemoryLimit: 32 Megabyte Totalsubmit: 1173 Accepted: 385 Description

Given n, a positive integer, how many positive integers less than n are relatively prime to n? Two integers a and b are relatively prime if there are no integers x > 1, y > 0, z > 0 such that a = xy and b = xz. Input

There are several test cases. For each test case, standard input contains a line with n <= 1,000,000,000. A line containing 0 follows the last case. Output

For each test case there should be single line of output answering the question posed above. Sample Input 7 12 0

Sample Output

6 4

（36）Square

TimeLimit: 1 Second MemoryLimit: 32 Megabyte Totalsubmit: 1263 Accepted: 350 Description

Given a set of sticks of various lengths, is it possible to join them end-to-end to form a square? Input

The first line of input contains N, the number of test cases. Each test case begins with an integer 4 <= M <= 20, the number of sticks. M integers follow; each gives the length of a stick - an integer between 1 and 10,000. Output

For each case, output a line containing \a square; otherwise output \Sample Input 3

4 1 1 1 1

5 10 20 30 40 50 8 1 7 2 6 4 4 3 5 Sample Output yes no yes

（37）Above Average

TimeLimit: 1 Second MemoryLimit: 32 Megabyte Totalsubmit: 2558 Accepted: 943 Description

It is said that 90% of frosh expect to be above average in their class. You are to provide a reality check. Input

The first line of standard input contains an integer C, the number of test cases. C data sets follow. Each data set begins with an integer, N, the number of people in the class (1 <= N <= 1000). N integers follow, separated by spaces or newlines, each giving the final grade (an integer between 0 and 100) of a student in the class. Output

For each case you are to output a line giving the percentage of students whose grade is above average, rounded to 3 decimal places. Sample Input

5

5 50 50 70 80 100

7 100 95 90 80 70 60 50 3 70 90 80 3 70 90 81

9 100 99 98 97 96 95 94 93 91 Sample Output

40.000% 57.143% 33.333% 66.667% 55.556%

（38）Guessing Game

TimeLimit: 1 Second MemoryLimit: 32 Megabyte Totalsubmit: 1330 Accepted: 438 Description

Stan and Ollie are playing a guessing game. Stan thinks of a number between 1 and 10 and Ollie guesses what the number might be. After each guess, Stan indicates whether Ollie's guess is too high, too low, or right on.

After playing several rounds, Ollie has become suspicious that Stan cheats; that is, that he changes the number between Ollie's guesses. To prepare his case against Stan, Ollie has recorded a transcript of several games. You are to determine whether or not each transcript proves that Stan is cheating. Input

Standard input consists of several transcripts. Each transcript consists of a number of paired guesses and responses. A guess is a line containing single integer between 1 and 10, and a response is a line containing \high\containing 0 follows the last transcript. Output

For each game, output a line \is dishonest\Stan's responses are inconsistent with the final guess and response. Otherwise, print \may be honest\Sample Input 10

too high 3

too low 4

too high 2

right on 5

too low 7

too high 6

right on 0

Sample Output Stan is dishonest Stan may be honest （39）Binomial Showdown

TimeLimit: 1 Second MemoryLimit: 32 Megabyte Totalsubmit: 1790 Accepted: 473 Description

In how many ways can you choose k elements out of n elements, not taking order into account?

Write a program to compute this number. Input

The input will contain one or more test cases.

Each test case consists of one line containing two integers n (n >= 1) and k (0 <= k <= n).

Input is terminated by two zeroes for n and k. Output

For each test case, print one line containing the required number. This number will always fit into an integer, i.e. it will be less than 2^31. Sample Input 4 2 10 5 49 6 0 0

Sample Output 6 252

13983816

（40）All in All

TimeLimit: 1 Second MemoryLimit: 32 Megabyte Totalsubmit: 1519 Accepted: 451 Description

You have devised a new encryption technique which encodes a message by inserting between its characters randomly generated strings in a clever way. Because of pending patent issues we will not discuss in detail how the strings are generated and inserted into the original message. To validate your method, however, it is necessary to write a program that checks if the message is really encoded in the final string.

Given two strings s and t, you have to decide whether s is a subsequence of t, i.e. if you can remove characters from t such that the concatenation of the remaining characters is s. Input

The input contains several testcases. Each is specified by two strings s, t of alphanumeric ASCII characters separated by whitespace. Input is terminated by EOF. Output

For each test case output, if s is a subsequence of t. Sample Input

sequence subsequence person compression

VERDI vivaVittorioEmanueleReDiItalia caseDoesMatter CaseDoesMatter Sample Output Yes No Yes No

（41）Max Sum

时间限制(普通/Java):1000MS/10000MS 运行内存限制:65536KByte

总提交: 585 测试通过: 171 描述

Given a sequence a[1],a[2],a[3]......a[n], your job is to calculate the max sum of a sub-sequence. For example, given (6,-1,5,4,-7), the max sum in this sequence is 6 + (-1) + 5 + 4 = 14. 输入

The first line of the input contains an integer T(1<=T<=20) which means the number of test cases. Then T lines follow, each line starts with a number N(1<=N<=100000), then N integers followed(all the integers are between -1000 and 1000). 输出

For each test case, you should output two lines. The first line is \number of the test case. The second line contains three integers, the Max Sum in the sequence, the start position of the sub-sequence, the end position of the sub-sequence. If there are more than one result, output the first one. Output a blank line between two cases. 样例输入 2

5 6 -1 5 4 -7

7 0 6 -1 1 -6 7 -5 样例输出 Case 1: 14 1 4

Case 2: 7 1 6

（42）u Calculate e

时间限制(普通/Java):1000MS/10000MS 运行内存限制:65536KByte

总提交: 362 测试通过: 196 描述

A simple mathematical formula for e is

where n is allowed to go to infinity. This can actually yield very accurate approximations of e using relatively small values of n. 输入 no input data 输出

Output the approximations of e generated by the above formula for the values of n from 0 to 9. The beginning of your output should appear similar to that shown below. 样例输入 样例输出 n e

- ----------- 0 1 1 2 2 2.5

3 2.666666667 4 2.708333333

（43）A + B Problem II

时间限制(普通/Java):1000MS/10000MS 运行内存限制:65536KByte

总提交: 655 测试通过: 215 描述

I have a very simple problem for you. Given two integers A and B, your job is to calculate the Sum of A + B. 输入

The first line of the input contains an integer T(1<=T<=20) which means the number of test cases. Then T lines follow, each line consists of two positive integers, A and B. Notice that the integers are very large, that means you should not process them by using 32-bit integer. You may assume the length of each integer will not exceed 1000. 输出

For each test case, you should output two lines. The first line is \number of the test case. The second line is the an equation \

means the result of A + B. Note there are some spaces int the equation. Output a blank line between two test cases. 样例输入

2 1 2

112233445566778899 998877665544332211 样例输出

Case 1: 1 + 2 = 3

Case 2:

112233445566778899 + 998877665544332211 = 1111111111111111110

（44）Simple Arithmetics

时间限制(普通/Java):1000MS/10000MS 运行内存限制:65536KByte

总提交: 65 测试通过: 4 描述

One part of the new WAP portal is also a calculator computing expressions with very long numbers. To make the output look better, the result is formated the same way as is it usually used with manual calculations.

Your task is to write the core part of this calculator. Given two numbers and the requested operation, you are to compute the result and print it in the form specified below. With addition and subtraction, the numbers are written below each other. Multiplication is a little bit more complex: first of all, we make a partial result for every digit of one of the numbers, and then sum the results together. 输入

There is a single positive integer T on the first line of input. It stands for the number of expressions to follow. Each expression consists of a single line containing a positive integer number, an operator (one of +, - and *) and the second positive

integer number. Every number has at most 500 digits. There are no spaces on the line. If the operation is subtraction, the second number is always lower than the first one. No number will begin with zero. 输出

For each expression, print two lines with two given numbers, the second number below the first one, last digits (representing unities) must be aligned in the same column. Put the operator right in front of the first digit of the second number. After the second number, there must be a horizontal line made of dashes (-).

For each addition or subtraction, put the result right below the horizontal line, with last digit aligned to the last digit of both operands.

For each multiplication, multiply the first number by each digit of the second number. Put the partial results one below the other, starting with the product of the last digit of the second number. Each partial result should be aligned with the corresponding digit. That means the last digit of the partial product must be in the same column as the digit of the second number. No product may begin with any additional zeros. If a particular digit is zero, the product has exactly one digit -- zero. If the second number has more than one digit, print another horizontal line under the partial results, and then print the sum of them.

There must be minimal number of spaces on the beginning of lines, with respect to other constraints. The horizontal line is always as long as necessary to reach the left and right end of both numbers (and operators) right below and above it. That means it begins in the same column where the leftmost digit or operator of that two lines (one below and one above) is. It ends in the column where is the rightmost digit of that two numbers. The line can be neither longer nor shorter than specified.

Print one blank line after each test case, including the last one. 样例输入 4

12345+67890 324-111 325*4405 1234*4 样例输出 12345 +67890 ------ 80235 324 -111 ---- 213

325 *4405 ----- 1625 0 1300 1300 ------- 1431625 1234 *4 ---- 4936

（45）Factorial

时间限制(普通/Java):1500MS/15000MS 运行内存限制:65536KByte

总提交: 50 测试通过: 34 描述

The most important part of a GSM network is so called Base Transceiver Station (BTS). These transceivers form the areas called cells (this term gave the name to the cellular phone) and every phone connects to the BTS with the strongest signal (in a little simplified view). Of course, BTSes need some attention and technicians need to check their function periodically.

ACM technicians faced a very interesting problem recently. Given a set of BTSes to visit, they needed to find the shortest path to visit all of the given points and return back to the central company building. Programmers have spent several months

studying this problem but with no results. They were unable to find the solution fast enough. After a long time, one of the programmers found this problem in a conference article. Unfortunately, he found that the problem is so called \Problem\them in any order, giving us N! possibilities to examine. The function expressing that number is called factorial and can be computed as a product 1.2.3.4....N. The number is very high even for a relatively small N.

The programmers understood they had no chance to solve the problem. But because they have already received the research grant from the government, they needed to continue with their studies and produce at least some results. So they started to study behaviour of the factorial function.

For example, they defined the function Z. For any positive integer N, Z(N) is the number of zeros at the end of the decimal form of number N!. They noticed that this function never decreases. If we have two numbers N1

There is a single positive integer T on the first line of input. It stands for the number of numbers to follow. Then there is T lines, each containing exactly one positive integer number N, 1 <= N <= 1000000000. 输出

For every number N, output a single line containing the single non-negative integer Z(N). 样例输入 6 3 60 100 1024 23456 8735373 样例输出 0 14 24 253 5861 2183837

（46）Chinese Chess

时间限制(普通/Java):1000MS/10000MS 运行内存限制:65536KByte

总提交: 7 测试通过: 2 描述

Both Xnby and Hekui like playing Chinese Chess. There are two sides: black and red (in the figures below, red is the pieces with white characters) in Chinese Chess. Each side take moves in turns. One day, they made a composition(Now, it’s red's turn):

By the way, each side can only move the ”Cannon”and

the ”Pawn”. The cannon can move in straight lines at any distance (from one cross to another) if no other chess pieces block its way. And the pawn can only move forward, one unit per turn. (For the red, top-bottom is forward, and for the black, bottom-top).

After the discussion，they all agree that only when one side, for example, the black cannon is forced to take a horizonal move which makes the red cannon can get to the hemline of the black, then the red wins (See the following figure).

So, they make a few rules:

1. The cannon can only move forward. If one side has to move the

“cannon” to left or right, he loses. Notice that it doesn't change situation if a cannon moves backward, because the opposite side can move its cannon forward for the same distance. 2. Only the pawns which haven't crossed the river can move. And the

distance between each pair of pawns (one red, one black) must exceed 1. 3. The winner only depends on the distance m and n(between the pair

of cannons in the same vertical line counting from the left side), S1,S2,S3 (between the pair of pawns”which not cross the river in the same vertical line counting from the left side). Xnby and Hekui want to know: which side is the winner when each of them moves in the best strategy. To make it more interesting, m,n,

S1,S2,S3 are not limited by Chinese Chessboard, in other words, Chessboard of this game is large enough. 输入

There are several test cases, each case in a single line which contains 5 integers separated by a blank: m, n, S1, S2, S3,

0≤m,n≤1000000,1≤S1,S2,S3≤1000。The input terminates when one line contains a single negative integer, which needn't to be processed. 输出

For each test case, output the winner(Red or Black) 样例输入 4 1 2 2 1 0 0 1 1 1 -1

样例输出 Red Black

（47）Border

时间限制(普通/Java):1000MS/10000MS 运行内存限制:65536KByte

总提交: 61 测试通过: 30 描述

You are to write a program that draws a border around a closed path into a bitmap, as displayed in the following figure:

The path is closed and runs along the grid lines, i.e. between the squares of the grid. The path runs counter-clockwise, so if following the path is considered as going ``forward'', the border pixels are always to the \covers 32 by 32 squares and has its lower left corner at (0, 0). You can safely assume that the path never touches the bounding rectangle of the bitmap and never touches or crosses itself. Note that a bit gets set if it is on the outside of the area surrounded by the path and if at least one of its edges belongs to the path, but not if only one of its corners is in the path. (A look at the convex corners in the figure should clarify that statement.) 输入

The first line of the input file contains the number of test cases in the file. Each test case that follows consists of two lines. The first line of each case contains two integer numbers x and y specifying the starting point of the path. The second line contains a string of variable length. Every letter in the string symbolizes a move of length one along the grid. Only the letters 'W' (\and '.' (\immediately followed by the end of the line. 输出

For each test case, output a line with the number of the case ('Bitmap #1', 'Bitmap #2', etc.). For each row of the bitmap from top to bottom, print a line where you print a character for every bit in that row from left to right. Print an uppercase 'X' for set bits and a period '.' for unset bits. Output a blank line after each bitmap. 样例输入

1 2 1

EENNWNENWWWSSSES. 样例输出

Bitmap #1

................................ ................................ ................................ ................................ ................................ ................................ ................................ ................................ ................................ ................................ ................................ ................................ ................................ ................................ ................................ ................................ ................................ ................................ ................................ ................................ ................................ ................................ ................................ ................................ ................................ ................................ .XXX............................ X...X........................... X..X............................ X...X........................... .X..X........................... ..XX............................

（48）URLs

TimeLimit: 1 Second MemoryLimit: 32 Megabyte Totalsubmit: 1068 Accepted: 458 Description

In the early nineties, the World Wide Web (WWW) was invented. Nowadays, most people think that the WWW simply consists of all the pretty (or not

so pretty) HTML-pages that you can read with your WWW browser. But back then, one of the main intentions behind the design of the WWW was to unify several existing communication protocols.

Then (and even now), information on the Internet was available via a multitude of channels: FTP, HTTP, E-Mail, News, Gopher, and many more. Thanks to the WWW, all these services can now be uniformly addressed via URLs (Uniform Resource Locators). The syntax of URLs is defined in the Internet standard RFC 1738. For our problem, we consider a simplified version of the syntax, which is as follows:

\

The square brackets [] mean that the enclosed string is optional and may or may not appear. Examples of URLs are the following: http://www.informatik.uni-ulm.de/acm ftp://acm.baylor.edu:1234/pub/staff/mr-p gopher://veryold.edu More specifically,

is always one of http, ftp or gopher.

is a string consisting of alphabetic (a-z, A-Z) or numeric (0-9) characters and points (.).

is a positive integer, smaller than 65536. is a string that contains no spaces.

You are to write a program that parses an URL into its components. Input

The input starts with a line containing a single integer n, the number of URLs in the input. The following n lines contain one URL each, in the format described above. The URLs will consist of at most 60 characters each. Output

For each URL in the input first print the number of the URL, as shown in the sample output. Then print four lines, stating the protocol, host, port

and path specified by the URL. If the port and/or path are not given in the URL, print the string instead. Adhere to the format shown in the sample output.Print a blank line after each test case. Sample Input

3

ftp://acm.hrbeu.edu.cn:1234/pub/mail/~moxichain http://www.hrbeu.edu.cn/acm gopher://sunwise.net Sample Output

URL #1

Protocol = ftp

Host = acm.hrbeu.edu.cn Port = 1234

Path = pub/mail/~moxichain

URL #2

Protocol = http

Host = www.hrbeu.edu.cn Port = Path = acm

URL #3

Protocol = gopher

Host = sunwise.net Port = Path =

（49）Rock, Scissors, Paper

TimeLimit: 1 Second MemoryLimit: 32 Megabyte Totalsubmit: 386 Accepted: 159 Description

Bart's sister Lisa has created a new civilization on a two-dimensional grid. At the outset each grid location may be occupied by one of three life forms: Rocks, Scissors, or Papers. Each day, differing life forms occupying horizontally or vertically adjacent grid locations wage war. In each war, Rocks always defeat Scissors, Scissors always defeat Papers,

and Papers always defeat Rocks. At the end of the day, the victor expands its territory to include the loser's grid position. The loser vacates the position.

Your job is to determine the territory occupied by each life form after n days. Input

The first line of input contains t, the number of test cases. Each test case begins with three integers not greater than 100: r and c, the number of rows and columns in the grid, and n. The grid is represented by the r lines that follow, each with c characters. Each character in the grid is R, S, or P, indicating that it is occupied by Rocks, Scissors, or Papers respectively. Output

For each test case, print the grid as it appears at the end of the nth day. Leave an empty line between the output for successive test cases. Sample Input 2 3 3 1 RRR RSR RRR 3 4 2 RSPR SPRS PRSP

Sample Output RRR RRR RRR RRRS RRSP RSPR

（50）Dumb Bones

TimeLimit: 5 Second MemoryLimit: 32 Megabyte Totalsubmit: 14 Accepted: 9 Description

You are trying to set up a straight line of dominos, standing on end, to be pushed over later for your entertainment. (Sure, it seems pointless to set something up only to knock it down again, but you have some strange hobbies) The tricky thing about setting dominos, however, is that if you make a mistake and knock one over as you place it, it will knock down any adjacent line of consecutive dominos on one side of it, partially ruining your work.

For instance, if you've already placed dominos in the pattern DD__DxDDD_D, and you try placing a domino at position x, there is a chance it will fall and knock over the domino to the left or the three dominos to its right, forcing you to place them again.

This human error is somewhat unavoidable, but you can make the odds somewhat more favourable by using a domino-placing technique that leads to dominos falling in one direction more often than in the other. Given the number of dominos you are trying to set up, and the probability that you'll knock over any individual domino either to the left or to the right while placing it, determine the average number of dominos you'll need to place before you finish. Assume that you're using an optimal placement strategy. Input

Input will consist of up to 100 cases. Each case consists of one line of input. It will contain the number of dominos to place, n, 1 <= n <= 1000, followed by nonnegative values Pl and Pr, indicating the probability of any domino falling to the left or to the right when placed. You may assume 0 < Pl + Pr <= 0.5.

The last test case is followed by a line containing a single 0. Output

For each case, output the expected number of dominos that will need to be placed before you finish, accurate to two digits after the decimal. Sample Input

10 0.25 0.25 10 0.1 0.4 10 0.0 0.5 0

Sample Output 46.25 37.28 20.00

本文来源：https://www.bwwdw.com/article/cf5o.html