1.5　相关题库

【1.5.1　Sum】

请你求出在1～n之间的所有整数的总和。

输入

输入是一个绝对值不大于10 000的整数n。

输出

输出一个整数，是所有在1～n之间的整数的总和。

试题来源：ACM 2000 Northeastern European Regional Programming Contest(test tour)

在线测试：Ural 1068

提示

根据等差数列s=1+2+…n的求和公式，如果n是大于0的正整数，则，否则。

【1.5.2　Specialized Four-Digit Numbers】

找到并列出所有具有如下特性的十进制的4位数字：4位数字的和等于这个数字以十六进制表示时的4位数字的和，也等于这个数字以十二进制表示时的4位数字的和。

例如，整数2991（十进制）的4位数字之和是2+9+9+1=21，因为2991=1×1728+8×144+9×12+3，所以其十二进制表示为1893₁₂，4位数字之和也是21。但是2991的十六进制表示为BAF₁₆，并且11+10+15=36，因此2991被程序排除了。

下一个数是2992，3种表示的各位数字之和都是22(包括BB0₁₆)，因此2992被列在输出中。（本题不考虑少于4位数字的十进制数——排除了前导零——因此2992是第一个正确答案。）

输入

本题没有输入。

输出

输出为2992和所有比2922大的满足需求的4位数字（以严格的递增序列），每个数字一行，数字前后不加空格，以行结束符结束。输出没有空行。输出的前几行如样例所示。

试题来源：ACM Pacific Northwest 2004

在线测试：POJ 2196，ZOJ 2405，UVA 3199

提示

首先设计一个函数calc(k,b)，计算并返回k转换成b进制后的各位数字之和。然后枚举[2992..9999]内的每个数i，若calc(i,10)==calc(i,12)==calc(i,16)，则输出i。

【1.5.3　Quicksum】

校验是一个扫描数据包并返回一个数字的算法。校验的思想是，如果数据包发生了变化，校验值也随之发生变化，所以校验经常被用于检测传输错误、验证文件的内容，而且在许多情况下可用于检测数据的不良变化。

本题请你实现一个名为Quicksum的校验算法。Quicksum的数据包只包含大写字母和空格，以大写字母开始和结束，空格和字母可以以任何组合出现，可以有连续的空格。

Quicksum计算在数据包中每个字符的位置与字符的对应值的乘积的总和。空格的对应值为0，字母的对应值是它们在字母表中的位置。A=1，B=2，依次类推，则Z=26。例如Quicksum计算数据包ACM和MID CENTRAL如下：

·ACM：1*1+2*3+3*13=46。

·MID CENTRAL：1*13+2*9+3*4+4*0+5*3+6*5+7*14+8*20+9*18+10*1+11*12=650。

输入

输入由一个或多个测试用例（数据包）组成，输入最后给出仅包含“#”的一行，表示输入结束。每个测试用例一行，开始和结束没有空格，包含1～255个字符。

输出

对每个测试用例（数据包），在一行中输出其Quicksum的值。

试题来源：ACM Mid-Central USA 2006

在线测试：POJ 3094，ZOJ 2812，UVA 3594

提示

设计一个函数value(c)，若字符c=='_'，则返回0，否则返回字母c的对应值c-'A'+1。

整个计算过程为一个循环，每次循环输入当前测试用例，计算和输出其Quicksum值。

字符位置和Quicksum值初始化为0，当前测试用例所对应的字符串s设为空，然后反复读入字符c，并将c送入s，直至c为文件结束标志（EOF）或行结束符（'\n'）为止。字符串s的Quicksum值可边输入边计算，即。

若s为输入结束符“#”，则退出程序。

【1.5.4　A Contesting Decision】

程序设计竞赛的裁判是一项艰苦的工作，要面对要求严格的参赛选手，要做出相关的决定，并要重复单调的工作。不过，这其中也可以有很多的乐趣。

对于程序设计竞赛的裁判来说，用软件使评测过程自动化有很大的帮助作用，而一些比赛软件存在的不可靠因素使人们希望比赛软件能够更好、更可用。如果你是竞赛管理软件开发团队的一员，基于模块化设计原则，你所开发的模块功能是为参加程序设计竞赛的队伍计算分数并确定冠军。给出参赛队伍在比赛中的情况，确定比赛的冠军。

记分规则如下。

一支参赛队的分数由两个部分组成：第一部分是解出的题数；第二部分是罚时，表示解题的总耗时和试题没有被解出前因错误的提交所另加的罚时。对于每个被正确解出的试题，罚时等于该问题被解出的时间加上每次错误提交的20分钟罚时。在问题没有被解出前不加罚时。

因此，如果一支队伍在比赛20分钟的时候第二次提交解出第1题，他们的罚时是40分钟。如果他们提交第2题3次，但没有解决这个问题，则没有罚时。如果他们在120分钟提交第3题，并一次解出的话，该题的罚时是120分钟。这样，该队的成绩是罚时160分钟，解出了两道试题。

冠军队是解出最多试题的队伍。如果两队在解题数上打成平手，那么罚时少的队为冠军队。

输入

程序评判的程序设计竞赛有4题。本题设定，在计算罚时后，不会导致队与队之间不分胜负的情况。

第1行为参赛队数n。

第2～n+1行为每个队的参赛情况。每行的格式如下：

<Name><p1Sub><p1Time><p2Sub><p2Time>…<p4Time>

第一个元素是不含空格的队名。后面是4道试题的解题情况（该队对这一试题的提交次数和正确解出该题的时间（都是整数））。如果没有解出该题，则解题时间为0。如果解出一道试题，提交次数至少是一次。

输出

输出一行。给出冠军队的队名、解出题目的数量，以及罚时。

试题来源：ACM Mid-Atlantic 2003

在线测试：POJ 1581，ZOJ 1764，UVA 2832

提示

设冠军队的队名为wname，解题数为wsol，罚时为wpt；当前队的队名为name，解题数为sol，罚时为pt；当前题的提交次数为sub，解题时间为time。

我们依次读入每个队的队名name和4道题的提交次数sub，解题时间time。

若该题成功解出（time>0），则累计该队的解题数（++sol），统计罚时pt（pt+=(sub-1)*20+time）。

计算完4道题的解题情况后，若当前队解题数最多，或虽同为目前最高解题数但罚时最少（sol>wsol||(sol==wsol & & wpt>pt)），则将当前队暂设为冠军队，记下队名、解题数和罚时（wname=name;wsol=sol;wpt=pt）。

显然，处理完n个参赛队的信息后，wname、wsol和wpt就是问题的解。

【1.5.5　Dirichlet’s Theorem on Arithmetic Progressions】

如果a和d是互素的正整数，从a开始增加d的算术序列，即a,a+d,a+2d,a+3d,a+4d,…包含无穷多的素数，这被称为Dirichlet算术级数定理。这一猜想由Johann Carl Friedrich Gauss（1777～1855）提出，Johann Peter Gustav Lejeune Dirichlet（1805～1859）在1837年证明它。

例如，由2开始增加3的算术序列，即：

2,5,8,11,14,17,20,23,26,29,32,35,38,41,44,47,50,53,56,59,62,65,68,71,74,77,80,83,86,89,92,95,98,…

包含了无穷多的素数：

2,5,11,17,23,29,41,47,53,59,71,83,89,…

给出正整数a、d和n，请你编写一个程序给出算术序列中的第n个素数。

输入

输入是一个测试用例的序列，每一个测试用例一行，包含3个用空格分开的正整数a、d和n。a和d互素。设定a≤9307、d≤346、n≤210。

输入用3个由空格分开的0结束，这不是测试用例。

输出

输出的行数与输入的测试用例的行数相同。每行给出一个整数，并且不包含多余的字符。

输出的整数对应于测试用例中的a、d、n，是从a开始每次增加d的算术序列中第n个素数。

在输入的条件下可知结果总是小于10⁶（一百万）。

试题来源：ACM Japan 2006 Domestic

在线测试：POJ 3006

提示

由于测试用例由算术序列的起始值a、增量d和素数顺序数n构成，输入以“0 0 0”结束，因此程序在输入第1个算术序列的起始值a、增量d和素数顺序数n后，进入了结构为while(a||d||n)的循环。循环体内的计算过程如下：

1）当前算术序列中的素数个数cnt初始为0。

2）通过结构为for(m=a;cnt<n;m+=d)的循环构造含n个素数的算术序列（循环变量m的初始值为a；循环条件为cnt<n，每循环一次，若判定m是素数，则cnt++。循环变量m增加一个d）。

3）输出第n个素数m–d（for循环多进行一次，应减去多加的d）。

4）输入下一个算术序列的起始值a、增量d和素数顺序数n。

【1.5.6　The Circumference of the Circle】

计算圆的周长似乎是一件容易的事，只要知道圆的直径就可以计算。但是，如果不知道直径怎么计算呢？给出平面上的3个非共线点的笛卡儿坐标。你的工作是计算与这3个点相交的唯一圆的周长。

输入

输入包含一个或多个测试用例，每个测试用例一行，包含6个实数x₁、y₁、x₂、y₂、x₃和y₃，表示3个点的坐标。由这3个点确定的直径不超过1 000 000。输入以文件结束终止。

输出

对每个测试用例，输出一行，给出一个实数，表示3个点所确定圆的周长。输出的周长精确到两位小数。Pi的值为3.141592653589793。

试题来源：Ulm Local 1996

在线测试：POJ 2242，ZOJ 1090

提示

此题的关键是求出与这3个点相交的唯一圆的圆心。设3个点分别为(x₀,y₀)、(x₁,y₁)和(x₂,y₂)，圆心为(x_m,y_m)。有以下两种解法。

（1）使用行列式

计算与这3个点相交的唯一圆的圆心：

由此得出唯一圆的半径，2πr即为相交于(x₀,y₀)、(x₁,y₁)和(x₂,y₂)的唯一圆的周长。

那么，如何证明与(x₀,y₀)、(x₁,y₁)和(x₂,y₂)相交的唯一圆的圆心为(x_m,y_m)呢？

证明：设圆心为P=(x_m,y_m)，P分别向引中垂线和，交于N点，交于M点。显然，M点的坐标为，(y₂-y₁,x₂-x₁)经过，如图1.5-1所示。

图　1.5-1

，设。现在只需证明。

（2）使用初等几何知识

设，根据海伦公式、三角形面积公式和正弦定理外接圆直径d，得出外接圆直径和外接圆周长l=d×π。

【1.5.7　Vertical Histogram】

请编写一个程序，从输入文件读取由4行大写字母组成的文本输入（每行不超过72个字符），并输出一个垂直柱状图以显示在输入中的所有大写字母（不包括空格、数字或标点符号）出现了多少次。输出格式如输出样例所示。

输入

第1行到第4行为4行大写字母的文本，每行不超过72个字符。

输出

第1行到第n行为由星号和空格组成的若干行，后面跟着一行，由被空格分开的大写字母组成。在任意一行结束时不要输出不需要的空格，也不要输出前导空格。

试题来源：USACO 2003 February Orange

在线测试：POJ 2136

提示

画统计图的顺序是自上而下、自左至右的，“自上而下”指的是按频率递减顺序处理每一行，“自左至右”指的是按序数递增的顺序处理当前行的每个字母。

设cnt为各字母的频率数组，其中cnt[0]为字母“A”的个数，……，cnt[25]为字母“Z”的个数。Maxc为字母的最高频率，即统计图上最高的“柱子”。

计算过程如下：

1）边输入边计算各字母的频率数组cnt。

2）计算字母的最高频率Maxc。

3）从统计图上最高的“柱子”出发，自上而下计算并画统计图，即进入结构为for(int i=1;i<=Maxc;i++)的循环。在循环体内：

①寻找当前行的右边界，即按照cnt[25..0]的顺序寻找第1个频率大于Maxc-i的字母序号l1-1（即cnt[ll-1]>Maxc-i））。

②搜索序号区间[0..l1-1]的字母。若字母j的频率cnt[j]大于Maxc-i（0≤j≤l1-1），则输出“*_”，否则输出“__”。

4）输出底行“A_B_…_Z”。

【1.5.8　Ugly Numbers】

丑陋数（Ugly Number）是仅有素因子2、3或5的整数。序列1,2,3,4,5,6,8,9,10,12…给出了前10个丑陋数。按照惯例，1被包含在丑陋数中。

给出整数n，编写一个程序输出第n个丑陋数。

输入

输入的每行给出一个正整数n(n≤1500)。输入以n=0的一行结束。

输出

对于输入的每一行，输出第n个丑陋数，对n=0的那一行不做处理。

试题来源：New Zealand 1990 Division I

在线测试：POJ 1338,UVA 136

提示

由于不知道有多少个测试数据，因此采用离线求解的办法，先通过三重循环计算出前1500的丑陋数a[1..1500]。

设最大丑陋数的上限limit=1 000 000 000。

第一重循环（循环变量为i）：枚举2的倍数，每循环一次，i←i×2，循环的终止条件为i≥limit。

第二重循环（循环变量为j）：枚举3的倍数，每循环一次，j←j×3，循环的终止条件为i×j≥limit。

第三重循环（循环变量为k）：枚举5的倍数，每循环一次，将丑陋数i×j×k记入a[]中，k←k×5，循环的终止条件为i×j×k≥limit。

然后，排序数组a，使a[x]为第x大的丑陋数（1≤x≤1500）。这样对于每测试一个数据x，只要从a表中直接取出a[x]即可，十分高效。

【1.5.9　排列】

大家知道，给出正整数n，则1～n这n个数可以构成n！种排列，把这些排列按照从小到大的顺序（字典顺序）列出，如n=3时，可以列出1 2 3、1 3 2、2 1 3、2 3 1、3 1 2、3 2 1六个排列。

任务描述如下。

给出某个排列，求出这个排列的下k个排列，如果遇到最后一个排列，则下一个排列为第1个排列，即排列1 2 3…n。

比如n=3、k=2，给出排列2 3 1，则它的下1个排列为3 1 2，下2个排列为3 2 1，因此答案为3 2 1。

输入

第一行是一个正整数m，表示测试数据的个数，下面是m组测试数据，每组测试数据第一行是2个正整数n（1≤n<1024）和k（1≤k≤64），第二行有n个正整数，是1，2…n的一个排列。

输出

对于每组输入数据，输出一行，n个数，中间用空格隔开，表示输入排列的下k个排列。

试题来源：2004人民大学ACM选拔赛

在线测试：POJ 1833

提示

设当前排列为num[0]～num[n-1]。如何找它的下一个排列呢？

1）从num[0]出发，从左向右找第1个非递增的数字的位置b。

2）在b位置之后寻找大于num[b]的最小的数num[k]：num[b]}，将num[b]与num[k]交换；

3）重新递增排序num[b+1]～num[n-1]，即为num的下一个排列。

例如排列2 3 1 5 4，从左向右找到第1个非递增的数字1；1之后大于它的最小数为4，交换1和4后得到2 3 4 5 1；递增排序5 1后得到2 3 4 1 5。2 3 4 1 5即2 3 1 5 4的下一个排列。

使用上述方法连续对排列num进行k次运算，即可得到num后的第k个排列。

【1.5.10　Number Sequence】

给出一个正整数i。编写一个程序，在数组序列S₁S₂…S_k中找到第i个位置的数字。每组S_k由从1到k的正整数序列组成，序列中从1到k一个接一个地给出。

例如，这个序列的前80个数字如下：

11212312341234512345612345671234567812345678912345678910123456789101112345678910

输入

输入的第一行给出一个整数t（1≤t≤10），表示测试用例的个数，后面每行给出一个测试用例。每个测试用例给出一个整数i（1≤i≤2 147 483 647）。

输出

输出每行处理一个测试用例，给出在第i个位置的数字。

试题来源：ACM Tehran 2002,First Iran Nationwide Internet Programming Contest

在线测试：POJ 1019，ZOJ 1410

提示

首先，完成两个函数。第一个函数计算前j个组的总长度（也就是说，前j个组有多少位数），并将结果存入数组中。第二个函数返回在组S_m中的第l位的数。

然后，采用二分法找到包含第i个位置数字的组S_n。

最后，返回在组S_n中的第i个位置的数字。