tceic.com
简单学习网 让学习变简单
相关标签
当前位置:首页 >> 学科竞赛 >>

大一ACM寒假20题


ACM 寒假 20 题
^_^o~ 加油,努力!

目录
前言 ..........................................................................................................................................

........ 1 示例说明........................................................................................................................................... 2 (1)例题................................................................................................................................. 2 (2)题目讲解......................................................................................................................... 2 (3)代码................................................................................................................................. 3 01、1020: C 语言程序设计教程(第三版)课后习题 1.6 ............................................................ 3 02、1021: C 语言程序设计教程(第三版)课后习题 3.7 ............................................................ 3 03、1023: C 语言程序设计教程(第三版)课后习题 4.9............................................................ 4 04、1028: C 语言程序设计教程(第三版)课后习题 5.8............................................................ 5 05、1038: C 语言程序设计教程(第三版)课后习题 6.10.......................................................... 6 06、1043: C 语言程序设计教程(第三版)课后习题 7.4............................................................ 6 07、1052: C 语言程序设计教程(第三版)课后习题 8.8 ............................................................ 7 08、1058: C 语言程序设计教程(第三版)课后习题 9.6............................................................ 8 09、1065: C 语言程序设计教程(第三版)课后习题 10.5.......................................................... 8 10、1067: C 语言程序设计教程(第三版)课后习题 11.1 .......................................................... 9 11、1006: 1-Norm Distance ........................................................................................................... 10 12、1007: Sum of 1 to n ................................................................................................................. 10 13、1008: Closest Points ................................................................................................................ 11 14、1009: Median Value ................................................................................................................ 12 15、1010: Grade Record Management .......................................................................................... 13 16、1012: Joseph Problem ............................................................................................................. 14 17、1013: Username Validation ..................................................................................................... 15 18、1075: Problem E – Steps ......................................................................................................... 15 19、1076: Problem A: Freckles ....................................................................................................... 16 20、1074: Problem D – Snap .......................................................................................................... 17 附录 ................................................................................................................................................ 18

前言
题目是针对所有大一同学选的, 没有考虑到大一中一些已经 K 了很多题的人, 而且这些 题目均是选自地大人自己的 OJ(http://202.114.196.48/JudgeOnline/,欢迎访问,Y(^_^)Y ) , 有条件上网的同学推荐直接在 OJ 上做(每个题前面都有 OJ 中的题目编号) 。另外,有些大 一 ACM 能力较强的同学可能已经做过其中部分题目,建议寒假中继续进阶,推荐杭电 OJ、 北大 OJ 和浙大 OJ,^_^o~ 努力! 前面 10 道题均是选自 OJ 上的中文题目, 大家也可以看到这些题目均是谭浩强老师的 《C 程序设计》上的课后习题,主要是帮助大家进一步熟练程序中的基本控制语句,以及提高对 代码的敏感度。 后面 10 题都是 OJ 上的英文题目,帮助大家感受一下 ACM 的氛围。其中也有一些基本 的题目,只是将题目改成英文描述而已。当然,也有一些比较难的,比如 16 题的约瑟夫环 问题,最后一题还涉及取随机数的问题(题目中有提示,具体怎么弄可以自己去查 baidu、 google 或者 MSDN) 。但是,这些基本算法和操作方法又是很常见的,当然也是很有用的。 所以说是迟早要掌握的啦,^_^ 另外,小编给大家透露一下,这些题目的答案基本上都是可以在网上找到的~ 不过,可 不要直接去搜哦~ 要尽量自己动脑想, 实在写不出是可以小小地看一下的, 前提是你得搞懂, 而搞懂的意思是下次在 OJ 或者在现场赛中遇到相同或者类似的题你能马上把它 A 掉啊~同 时,讨论、共享,是 IT 人的精神,欢迎大家互相讨论,互相学习,而且,在网上分享自己 的感悟与问题, 你还会收获更多意想不到的东西, 这里就不提前透露了, 试过你就知道了?? 时间和能力有限,ACM 学长只能帮你到这儿了。另外,选题不当还望谅解勿喷。OJ 上 有更多好题,欢迎大家去探索,^_^o~ 加油,亲! 胡浩 2013 年 1 月 15 日 深夜

1

示例说明
(1)例题
1001: A + B Problem (2) Description
Calculate a + b. a and b are integers.

Input
The input may contain several test cases. In each test case, there are two integers, a and b, separated by a space. Input is terminated by EOF.

Output
For each test case, print out the sum of a and b.

Sample Input
1 2 10 20 324 111

Sample Output
3 30 435

(2)题目讲解
在给大一的同学答疑的时候发现很多人对 EOF 的意思不理解,有的“理解”了也不会 用。 EOF 的值通常为-1,代表 End Of File。 (详见百度,或者自己去查 MSDN) 在这个题目里在实现连续输入时就要用到这个知识点。 同时, 大家得知道 scanf()的返回 值的意思,scanf()的返回值是成功输入数据的个数。于是实现连续输入的代码就可以写为 while(scanf(“%d %d”,&a,&b)!=EOF)。

2

(3)代码

01、1020: C 语言程序设计教程(第三版)课 后习题 1.6
Description
编写一个程序,输入 a、b、c 三个值,输出其中最大值。

Input
一行数组,分别为 a b c

Output
a b c 其中最大的数

Sample Input
10 20 30

Sample Output
30

02、1021: C 语言程序设计教程(第三版)课 后习题 3.7
Description
要将"China"译成密码,译码规律是:用原来字母后面的第 4 个字母代替原来的字母.例如, 字母"A"后面第 4 个字母是"E"."E"代替"A"。因此,"China"应译为"Glmre"。请编一程序,
3

用赋初值的方法使 cl、c2、c3、c4、c5 五个变量的值分别为,’C’、’h’、’i’、’n’、’a’,经过 运算,使 c1、c2、c3、c4、c5 分别变为’G’、’l’、’m’、’r’、’e’,并输出。

Input
China

Output
加密后的 China

Sample Input
China

Sample Output
Glmre

03、1023: C 语言程序设计教程(第三版)课 后习题 4.9
Description
输入一个华氏温度,要求输出摄氏温度。公式为 c=5(F-32)/9 输出要求有文字说明, 取位 2 小数。

Input
一个华氏温度,浮点数

Output
摄氏温度,浮点两位小数

Sample Input
-40

Sample Output
c=-40.00

HINT

4

零下 40 度,可以不问是?氏

04、1028: C 语言程序设计教程(第三版)课 后习题 5.8
Description
企业发放的奖金根据利润提成。利润低于或等于 100000 元的,奖金可提 10%; 利润高于 100000 元,低于 200000 元(100000<I≤200000)时,低于 100000 元的部 分按 10%提成,高于 100000 元的部分,可提成 7.5%; 200000<I≤400000 时, 低于 200000 元部分仍按上述办法提成, (下同) 高于 200000 , 元的部分按 5%提成; 400000<I≤600000 元时,高于 400000 元的部分按 3%提成;600000<I≤1000000 时, 高于 600000 元的部分按 1.5%提成; I>1000000 时,超过 1000000 元的部分按 1%提成。从键盘输入当月利润 I,求应发奖 金总数。

Input
一个整数,当月利润。

Output
一个整数,奖金。

Sample Input
900

Sample Output
90

HINT
用 Switch 要比用 if 的看起来更清晰。

5

05、1038: C 语言程序设计教程(第三版) 课后习题 6.10
Description
猴子吃桃问题。猴子第一天摘下若干个桃子,当即吃了一半,还不过瘾,又多吃了 一个。第二天早上又将剩下的桃子吃掉一半,又多吃一个。以后每天早上都吃了前 一天剩下的一半零一个。到第 N 天早上想再吃时,见只剩下一个桃子了。求第一天 共摘多少桃子。

Input
N

Output
桃子总数

Sample Input
10

Sample Output
1534

06、1043: C 语言程序设计教程(第三版) 课后习题 7.4
Description
已有一个已排好的 9 个元素的数组,今输入一个数要求按原来排序的规律将它插入 数组中。

Input
第一行,原始数列。第二行,需要插入的数字。

Output
排序后的数列

Sample Input
1 7 8 17 23 24 59 62 101
6

50

Sample Output
1 7 8 17 23 24 50 59 62 101

07、1052: C 语言程序设计教程(第三版)课 后习题 8.8
Description
写一函数,输入一个四位数字,要求输出这四个数字字符,但每两个数字间空格。 如输入 1990,应输出"1 9 9 0"。

Input
一个四位数

Output
增加空格输出

Sample Input
1990

Sample Output
1 9 9 0

7

08、1058: C 语言程序设计教程(第三版) 课后习题 9.6
Description
请设计输出实数的格式,包括:⑴一行输出一个实数;⑵一行内输出两个实数;⑶ 一行内输出三个实数。实数用"6.2f"格式输出。

Input
一个实数,float 范围

Output
输出 3 行,第一行打印一遍输入的数,第二行打印两遍,第三行打印三遍。第二行 和第三行,用空格分隔同一行的数字。实数用"6.2f"格式输出。

Sample Input
0.618

Sample Output
0.62 0.62 0.62 0.62 0.62

0.62

09、1065: C 语言程序设计教程(第三版) 课后习题 10.5
Description
有 n 人围成一圈,顺序排号。从第 1 个人开始报数(从 1 到 3 报数) ,凡报到 3 的人 退出圈子,问最后留下的是原来的第几号的那位。

Input
初始人数 n

Output
最后一人的初始编号

Sample Input
8

3

Sample Description
定义一个结构体变量(包括年、月、日) 。计算该日在本年中是第几天,注意闰年问 题。

Input
年月日

Output
当年第几天

Sample Input
2000 12 31

Sample Output
366

Output
2

10、1067: C 语言程序设计教程(第三版)课 后习题 11.1
Description
定义一个结构体变量(包括年、月、日) 。计算该日在本年中是第几天,注意闰年问 题。

Input
年月日

Output
当年第几天

Sample Input
2000 12 31

Sample Output
366

9

11、1006: 1-Norm Distance
Description
For two points with coordinates of (x1, y1) and (x2, y2), their 1-norm distance D1 is defined as: D1 = |x1 – x2| + |y1 – y2|. Calculate the 1-norm distance of any two given points (You should not use any mathematical function).

Input
Two lines, each line has two integers. The first line is x1 and y1; the second line is x2 and y2.

Output
The 1-norm distance between the two points.

Sample Input
1 1 2 2

Sample Output
2

12、1007: Sum of 1 to n
Description
Calculate 1 + 2 + 3 + ... + n (n is an integer, and 1 <= n <= 10000). If n<=0, print out “Error Input”, else print out the sum.

Input
There are multiple test cases. For each case, there is a line contains n which has been described above. Input is terminated by EOF.
10

Output
The result of 1 + 2 + 3 + ... + n.

Sample Input
8 100 -1 200

Sample Output
36 5050 Error Input 20100

13、1008: Closest Points
Description
Given a point p and a set of points S in 3-D coordinate system, the distance from p to S is defined as the Euclidean Distance from p to the closest point a in S. Write a program to find out the point in S from which is closest to p.

Input
The first line is three floating numbers, denoting the coordinates of p (x, y, z). The second line is an integer N (1<=N<=20), indicating that there are N pointers in S. Then the following N lines will show the 3-D coordinates of each point in S, one point on each line.

Output
The coordinates of the nearest point in S to p, denoting the coordinate in format of (x, y, z), and the distance, separating the coordinate and the distance by a space. Each output number must be formatted as a floating point number with exactly two digit after the decimal point.
11

Sample Input
1.1 3 4.2 1.0 5.0 2.0 3.0 5.0 6.0 3.1 4.0 6.0 1.0

Sample Output
(1.00 3.10 4.00) 1.49

14、1009: Median Value
Description
Figure out the median of a floating point number array. If the size of an array is an odd number, the median is the middle element after arranging all the array elements from lowest value to highest value; If there is an even number of elements, then there is no single middle value, so the median is the mean of the two middle values.

Input
The input may contain several test cases. The first line of each test case is an integer n (n >= 1), representing the size of the array. The second line of each test case contains all the elements in the array. Input is terminated by EOF.

Output
For each test case, output the median , which must be formatted as a floating point number with exactly two digit after the decimal point.

Sample Input
6 5.0 4.0 3.0 2.0 11.0 3.0 11 5.0 6.0 222.0 23.0 23.0 4.0 2.0 5.0 99.0 1.0 8.0
12

Sample Output
3.50 6.00

15、1010: Grade Record Management
Description
There are some students’ grade records, in format of “name grade”. In order to make the teacher to view and manage all the records easily, you are asked to develop a program to sort the records first by grade (in descending order), and second by name (in alphabetic order). That means the sorted records will be from the highest grade to lowest grade; and if two students have the same grade, whose name appeared earlier in a dictionary will be shown earlier.

Input
8 grade records, one record on per line. Only letters and digits appear in the name of a student (i.e. there will be no space in a name). All grades are integers.

Output
The 8 sorted records, one record per line.

Sample Input
WangYi 90 LiMing 90 HuRui 50 ZhangLi 65 LiLei 80 ZhangFei 65 ZhaoSan 70 ChenZi 100

Sample Output
ChenZi 100 LiMing 90 WangYi 90
13

LiLei 80 ZhaoSan 70 ZhangFei 65 ZhangLi 65 HuRui 50

16、1012: Joseph Problem
Description
The Joseph's problem is notoriously known. From among n people, numbered 1, 2, . . ., n, standing in circle. Starting from sth and every mth is going to be executed and only the life of the last remaining person will be saved. Joseph was smart enough to choose the position of the last remaining person, thus saving his life to give us the message about the incident. For example when n = 6, s = 1 and m = 5, then the people will be executed in the order 5, 4, 6, 2, 3 and 1 will be saved. (1<= n <=20000, s>=1, m >=1)

Input
There are multiple test cases. For each case, there is a line contains three positive integers, n, s and m.. Input is terminated by EOF.

Output
For every test case, output a single line containing the number of the person who may be saved.

Sample Input
13 1 5 15 2 5

Sample Output
6 2

14

17、1013: Username Validation
Description
A website requests its new user to register a user name before using it. A valid username should: (1) contain only letters (a~z, A~Z) and digits (0~9); (2) have neither less than 6 characters nor more than 10 characters (6 <= name length <= 10); and (3) start with a letter (a~z, A~Z). Please write a program to check whether a given string is a valid username or not.

Input
The input may contain several test cases. Each test case is one user name (i.e. a string). Input is terminated by EOF.

Output
For each test case, output “Valid” or “Invalid”.

Sample Input
Mary8912 Tom_cat

Sample Output
Valid Invalid

18、1075: Problem E – Steps
Description
One steps through integer points of the straight line. The length of a step must be nonnegative and can be by one bigger than, equal to, or by one smaller than the length of the previous step. What is the minimum number of steps in order to get from x to y? The length of the first and the last step must be 1.

15

Input consists of a line containing n, the number of test cases. For each test case, a line follows with two integers: 0 <= x <= y < 2^31. For each test case, print a line giving the minimum number of steps to get from x to y.

Sample Input
3 45 48 45 49 45 50

Sample Output
3 3 4

19、1076: Problem A: Freckles
Description
In an episode of the Dick Van Dyke show, little Richie connects the freckles on his Dad's back to form a picture of the Liberty Bell. Alas, one of the freckles turns out to be a scar, so his Ripley's engagement falls through. Consider Dick's back to be a plane with freckles at various (x,y) locations. Your job is to tell Richie how to connect the dots so as to minimize the amount of ink used. Richie connects the dots by drawing straight lines between pairs, possibly lifting the pen between lines. When Richie is done there must be a sequence of connected lines from any freckle to any other freckle.

Input
The first line contains 0 < n <= 100, the number of freckles on Dick's back. For each freckle, a line follows; each following line contains two real numbers indicating the (x,y) coordinates of the freckle.

Output
Your program prints a single real number to two decimal places: the minimum total length of ink lines that can connect all the freckles.

16

Sample Input
3 1.0 1.0 2.0 2.0 2.0 4.0

Sample Output
3.41

20、1074: Problem D – Snap
Description
Snap is a 2-player card game. The deck of cards contains several of each type of card. Initially each player has one half of the deck, in some random sequence, face down in a pile, and plays them in sequence from top to bottom, placing each card face-up in another pile. When the face-down pile is exhausted, the face-up pile is turned over to become the face-down pile and play continues. The two players play their cards concurrently and synchronously. That is, each places a card face up at exactly the same time. If two cards turned up at the same time are the same type, each player calls "Snap!" and the player who calls first takes the other's face-up pile and places it on top of his or her own. Play proceeds until one player has all the cards. This player is the winner. Your job is to simulate a game of snap to determine whether it will end within 1000 turns and, if so, to determine the winner.

Input
Each type of card is denoted by a single letter or digit. The first line of input Jane's initial pile of cards, from top to bottom. The second line of input is John's initial pile. Jane and John start with the same number of cards; not more than 50 each.

Output
During play, whenever it comes time to call "Snap!" the builtin function "random" is used to determine who calls first: if the expression

17

random()/141%2 random div 141 mod 2

{in C or C++} {in Pascal; see note below}

yields 0, Jane calls first; otherwise John calls first. Whenever Jane calls first, print "Snap! for Jane: " followed by Jane's face-up pile, from top to bottom. Whenever John calls first, print "Snap! for John: " followed by John's face-up pile. If the game ends, print "John wins." or "Jane wins.", whichever is appropriate. If the game does not end when each player has turned over 1000 cards, print "Keeps going and going ..."

Sample Input
ABCDA CBADC

Sample Output
Snap! for Jane: Snap! for Jane: Snap! for John: Snap! for John: John wins. BCBA DADCBCBA CBAC ADADCBAC

Source
waterloo

附录
其它 OJ
杭电 OJ,http://acm.hdu.edu.cn/,据说是 ACMer 聚集最多的地方 北大 OJ,http://acm.whu.edu.cn/blog/ 浙大 OJ,http://acm.zju.edu.cn/onlinejudge/,这个上面的题可有点难,欢迎挑战,反正 我是感觉很难的喽。另外,这上面每个月都有月赛,你可以去感受,然后你就可以找到自己 的差距了,(^_^)∠※ 武大 OJ,http://acm.whu.edu.cn/blog/,看一下兄弟院校是怎么弄的。 南阳理工 OJ,http://acm.nyist.net/JudgeOnline/step.php,呃,仅是逛了下,^_^ 哈工大 OJ,http://acm.hit.edu.cn/,好强的样子。 codeforces,http://codeforces.com/,也可以做题,全英文网站??

一些值得浏览的网站
http://blog.csdn.net/New_C_YUER/article/category/816398,组合数学的题好多,可以跟 着他的顺序做。当然,等你学到一定程度也可以自己写 BLOG,交流、共享,IT 人的精神嘛~
18

给 IT 新人的建议,写得有点意思,http://blog.csdn.net/pozen/article/details/7583820。 而且,语言很有 IT 人的特色,感受一下吧。 这个 BLOG 可以让你学到很多,http://972169909-qq-com.iteye.com/ 全球最大的中文 IT 社区,http://www.csdn.net/, 在这上面可以看到最新的 IT 新闻,还 可以和很多同道中人交流,当然,还可以找到你各种课设的代码,└(^o^)┘ 差点儿忘了介绍 ACM 的全球首页了,http://icpc.baylor.edu/welcome.icpc,是不是感觉 很强大?不过平时很少上去逛的,仅仅是介绍一下而已啊。

19


推荐相关:
网站首页 | 网站地图
All rights reserved Powered by 简单学习网 www.tceic.com
copyright ©right 2010-2021。
文档资料库内容来自网络,如有侵犯请联系客服。zhit325@126.com