haihongyuan.com
海量文库 文档专家
全站搜索:
您现在的位置:首页 > 初中教育 > 学科竞赛学科竞赛

奥林匹克信息学选题及解答

发布时间:2013-12-04 09:28:17  

Addtion of numbers

Time Limit: 2 seconds

Eric is currently studying in Primary two. He was asked to do n ( 1 n

20 ) addition problems,

31which is to sum up two integers, a and b ( 1 a, b < 2 ). He has to hand this in tomorrow.

However, he is a very lazy student. He wants to play lego instead of doing this homework. You are Eric's elder brother and he ask you to help him. As both of you are lazy guys, you decide to write a program to complete this task rather than calculating those by hand. Input

The input contains n + 1 lines of input. The first line of the input is the number n. The second line to the n + 1th line contains two numbers a and b at each line.

Output

The output file contains n lines, which are the sum of a and b. The i-th line of output is the sum of the two integers in the i+1-th line of input.

Sample Input

5

1 1

2 9

3 6

4 19

5 200

Sample Output

2

11

9

23

205

计算a^b mod c

1<=b,c<=10^9

输入:a b c

输出:求出的值

The `if' statement

Time Limit: 1 second

Memory Limit: 1 MB

Write a program to read in an integer n ( 0 < n < 2 ) . If n is an odd number which lies between 50 and 100 (excluding 50 and 100), the program should output n. Otherwise if n is a multiple of 6 or 7, the program should output 2n. If n does not statisfy the above conditions, the program should output 3n. 60

Input

The input file contains an integer n.

Output

The output contains 1 line, which is the result of the above description.

Sample Input

24

Sample Output

48

Alphabet Sorting

Time Limit: 1 second

Memory Limit: 1 MB

Allen is currently studying the 26 letters. Please write a program to help him to identify the 10th letter, after sorting in ascending order, in the input.

Input

The inpue file contains n+1 lines. The first line contains an integer n ( 11 n

26 ). Each of the following n lines contain a lower case letter.

Output

The output contains the 10th letter after sorting in ascending order.

Sample Input

11

a

c

b

e

f

d

g

z

h

i

x

Sample Output

x

Taking Square Roots

Time Limit: 1 second

Given a list of integers, output the result after taking the square roots rounded up to 3 decimal places. The first line of input consists of one non-negative integer N, which is smaller than 21, which indicates the number of test cases. The following N lines contain an integer in each line, which lies between -40000 and 40000. Output its square root up to 3 decimal places. If the square root is not real, you should display `i' after the number. Sample Input

2

4

-4

Sample Output

2.000

2.000i

Output Your Message

Time Limit: 1 second

Memory Limit: 1 MB

Given a name in the input, please output the name with an additional string `, you are fired.' If the input is either `Marcus', `Patrick' or `Sherman' (these theee names are sorted in lexicographical order), please output his name and ` is extremely clever.'. It is guranteed that the string in the input contains at most 255 characters and the characters are all printable ASCII characters.

Sample Input 1

Simon

Sample Output 1

Simon, you are fired.

Sample Input 2

Patrick

Sample Output 2

Patrick is extremely clever.

Sample Input 3

Sherman

Sample Output 3 Sherman is extremely clever.

Sherman's Website

Time Limit: 3 seconds

Sherman is an experienced website designer. He built a famous website, comfield, which attracts millions of visitors to browse his website per day. This website provides a wide variety of services, games, articles and even online judge for the users. It is extremely popular and nearly every Hong Kong people know his webiste. Marcus and Patrick are his fans and they post a lot of threads in his forum. He currently has 2147483647 threads in his forum! Sherman wants to post some statistics of his website to prove that his website is really popular. He wants to do some statistical analysis. From his server software, he knows that the number of visitors of his website per hour. However, he does not know much about statistics as he is too young to learn it. As a friend of Sherman, you have the responsibility to help him.

Given a specified time period, and the number of visitors per hour, write a program which tells him the mean and median of these statistics.

Input

The input file consists of N + 1 lines. The first line contains an integer N ( 1 N

100000 ), which is the number of hours provided in the statistics. The 2nd to the N + 1th line are the number of visitors per hour, which are non-negative integers less than 21475.

Output

The output file should contain 3 lines. The first line contains the time period, in days, in this statistical report. One day is added if the exceeding hours cannot form a new day. The second line of output is the mean (correct to three decimal places) and the third line is the median (correct to the nearest integer). You should follow the output format as shown in the sample output.

Sample Input

5

1

2

3

4

5

Sample Output

1 day(s)

Mean: 3.000

Median: 3

返回数A在数组中的位置

输入格式:数A ,一维数组B的元素个数N(N<=10^5)

已按升序或降序排列的一维数组B (-32768<B[i],A<32767)

输出格式:数A在B中的下标。B中如果存在多个A,则输出最小的一个。如果B中不存在A,则输出-1

输入样例:3 6

1 3 3 4 5 10

输出样例:2

输入样例:1 3

3 4 5

输出样例:-1

闰年(二)

输入任意两个年份(正整数),判断这两个年份之间共存在多少个闰年?

输入样例:

1981 2000

输出样例:

5

进制转换(二)

输入K进制的正整数N,请把N化为L进制后输出。(N<1000000;L,K<=16) 有多组数据。

输入格式:

K N L

输入样例:

8 10 2

10 10 16

输出样例:

1000

A

题目:剔除多余括号(reduce.pas)

输入一个含有括号的四则运算表达式,可能含有多余的括号。编程整理该表达式,去掉所有多余的括号,原表达式中所有变量和运算符相对位置保持不变,并保持与原表达式等价。

变量用小写的a-z表示,运算符为+,-,*,/

例:

输入表达式 应输出表达式

a+(b+c) a+b+c

(a*b)+c/d a*b+c/d

a+b/(c-d) a+b/(c-d)

注意输入a+b时不能输出b+a

表达式以字符串输入,长度不超过255。输入不用判错。所有变量为单个小写字母。只是要求去掉所有多余括号,不要求对表达式化简。

回文数

【题目描述】

若一个数(首位不为零)从左向右读与从右向左读都一样,我们就将其称之为回文数。

例如:给定一个10进制数56,将56加65(即把56从右向左读),得到121是一个回文数。 又如:对于10进制数87:

STEP1:87+78 = 165 STEP2:165+561 = 726

STEP3:726+627 = 1353 STEP4:1353+3531 = 4884

在这里的一步是指进行了一次N进制的加法,上例最少用了4步得到回文数4884。

写一个程序,给定一个数M,求最少经过几步可以得到回文数。如果在30步以内(包含30步)不可能得到回文数,则输出“Impossible!”

【输入格式】

共一行

第一行为M(0<=M<=maxlongint)

【输出格式】

共一行

第一行为经过的步数或“Impossible!”

【输入样例】

87

【输出样例】

4

1.奖学金

(scholar.pas/c/cpp)

【问题描述】

某小学最近得到了一笔赞助,打算拿出其中一部分为学习成绩优秀的前5名学生发奖学金。期末,每个学生都有3门课的成绩:语文、数学、英语。先按总分从高到低排序,如果两个同学总分相同,再按语文成绩从高到低排序,如果两个同学总分和语文成绩都相同,那么规定学号小的同学排在前面,这样,每个学生的排序是唯一确定的。

任务:先根据输入的3门课的成绩计算总分,然后按上述规则排序,最后按排名顺序输出前5名学生的学号和总分。注意,在前5名同学中,每个人的奖学金都不相同,因此,你必须严格按上述规则排序。例如,在某个正确答案中,如果前两行的输出数据(每行输出两个数:学号、总分)是:

7 279

5 279

这两行数据的含义是:总分最高的两个同学的学号依次是7号、5号。这两名同学的总分都是279(总分等于输入的语文、数学、英语三科成绩之和),但学号为7的学生语文成绩更高一些。如果你的前两名的输出数据是:

5 279

7 279

则按输出错误处理,不能得分。

【输入】

输入文件scholar.in包含n+1行:

第1行为一个正整数n,表示该校参加评选的学生人数。

第2到n+1行,每行有3个用空格隔开的数字,每个数字都在0到100之间。第j行的3个数字依次表示学号为j-1的学生的语文、数学、英语的成绩。每个学生的学号按照输入顺序编号为1~n(恰好是输入数据的行号减1)。

所给的数据都是正确的,不必检验。

【输出】

输出文件scholar.out共有5行,每行是两个用空格隔开的正整数, 依次表示前5名学生的学号和总分。

【输入输出样例1】

【输入输出样例2】

【限制】

50%的数据满足:各学生的总成绩各不相同

100%的数据满足:6<=n<=300

猴子选大王

【问题】n(3≤n≤1000)只猴子选大王,选举办法如下:从头到尾1,2,3报数,凡报3的退出,余下的从尾到头1,2,3报数,凡报3的退出...如此类推,当剩下两只猴子时,取这时报1的为王,若想当猴王,请问当初应占据什么位置?

【输入样例】

7

【输出样例】

2 应该是6

铺地毯 (carpet.cpp/c/pas)

【问题描述】

为了准备一个独特的颁奖典礼,组织者在会场的一片矩形区域(可看做是平面直角坐标系的第一象限)铺上一些矩形地毯。一共有n 张地毯,编号从1 到n。现在将这些地毯按照编号从小到大的顺序平行于坐标轴先后铺设,后铺的地毯覆盖在前面已经铺好的地毯之上。

地毯铺设完成后,组织者想知道覆盖地面某个点的最上面的那张地毯的编号。注意:在矩形地毯边界和四个顶点上的点也算被地毯覆盖。

【输入】

输入共n+2 行。

第一行,一个整数n,表示总共有n 张地毯。接下来的n 行中,第i+1 行表示编号i 的地毯的信息,包含四个正整数a,b,g,k,每两个整数之间用一个空格隔开,分别表示铺设地毯的左下角的坐标(a,b)以及地毯在x轴和y 轴方向的长度。

第n+2 行包含两个正整数x 和y,表示所求的地面的点的坐标(x,y)。

【输出】

输出共1 行,一个整数,表示所求的地毯的编号;若此处没有被地毯覆盖则输出-1。

【输入输出样例1】

输入:

3

1 0 2 3

0 2 3 3

2 1 3 3

2 2

输出:

3

【输入输出样例说明】

如下图,1 号地毯用实线表示,2 号地毯用虚线表示,3 号用双实线表示,覆盖点(2,2)的最上面一张地毯是3 号地毯。

【输入输出样例2】

输入:

3

1 0 2 3

0 2 3 3

2 1 3 3

4 5

输出:

-1

【输入输出样例说明】

如上图,1 号地毯用实线表示,2 号地毯用虚线表示,3 号用双实线表示,点(4,5)没有被地毯覆盖,所以输出-1。

【数据范围】

对于30%的数据,有n≤2;

对于50%的数据,0≤a, b, g, k≤100;

对于100%的数据,有0≤n≤10,000,0≤a, b, g, k≤100,000。

记数问题

(count.cpp/c/pas)

【问题描述】

试计算在区间1到n的所有整数中,数字x(0≤x≤9)共出现了多少次?例如,在1到11中,即在1、2、3、4、5、6、7、8、9、10、11中,数字1出现了4次。

【输入】

输入文件名为count.in。

输入共1行,包含2个整数n、x,之间用一个空格隔开。

【输出】

输出文件名为count.out。

输出共1行,包含一个整数,表示x出现的次数。

【输入输出样例】

count.in count.out

11 1 4

【数据说明】

对于100%的数据,1≤n≤1,000,000,0≤x≤9。

校门外的树 (tree.pas/c/cpp)

【问题描述】 某校大门外长度为L的马路上有一排树,每两棵相邻的树之间的间隔都是 1米 。我们可以把马路看成一个数轴,马路的一端在数轴0的位置,另一端在L的位置;数轴上的每个整数点,即0,1,2,??,L,都种有一棵树。由于马路上有一些区域要用来建地铁。这些区域用它们在数轴上的起始点和终止点表示。已知任一区域的起始点和终止点的坐标都是整数,区域之间可能有重合的部分。现在要把这些区域中的树(包括区域端点处的两棵树)移走。你的任务是计算将这些树都移走后,马路上还有多少棵树。

【输入文件】 输入文件tree.in的第一行有两个整数L(1 <= L <= 10000)和 M(1 <= M <= 100),L代表马路的长度,M代表区域的数目,L和M之间用一个空格隔开。接下来的M行每行包含两个不同的整数,用一个空格隔开,表示一个区域的起始点和终止点的坐标。

【输出文件】 输出文件tree.out包括一行,这一行只包含一个整数,表示马路上剩余的树的数目。

【样例输入】

500 3

150 300

100 200

470 471

【样例输出】 298

【数据规模】 对于20%的数据,区域之间没有重合的部分;对于其它的数据,区域之间有重合的情况。

网站首页网站地图 站长统计
All rights reserved Powered by 海文库
copyright ©right 2010-2011。
文档资料库内容来自网络,如有侵犯请联系客服。zhit326@126.com