中南大学第三届ACM校赛题目

Problem A. Palindrome

Description

A palindrome is a symmetrical string, that is, a string read the same from left to right as from right to left. You are asked to write a program which, given a string, determines whether it is a palindrome or not.

Input

The first line contain a single integer T, indicates the number of test cases.

T lines follow, each line contain a string which you should judge. The length of the string is at most 1000.

Output

Print one line for each string, if it is a palindrome, output “YES”, else “NO”.

Sample Input

2

aba

ab

Sample Output

YES

NO

Problem B. 素数槽

Description

处于相邻的两个素数p和p + n之间的n - 1个连续的合数所组成的序列我们将其称为长度为n的素数槽。例如，?24, 25, 26, 27, 28?是处于素数23和素数29之间的一个长度为6的素数槽。

你的任务就是写一个程序来计算包含整数k的素数槽的长度。如果k本身就是素数，那么认为包含k的素数槽的长度为0。

Input

第一行是一个数字n，表示需要测试的数据的个数。后面有n行，每行是一个正整数k，k大于1并且小于或等于的第十万个素数（也就是1299709）。

Output

对于输入部分输入的每一个k，都对应输出一个非负整数，表示包含k的素数槽的长度，每个非负整数占一行。

Sample Input

5

10

11

27

2

492170

Sample Output

4

6

114

Problem C. Parsing Real Numbers Description

In scientific notation, real numbers are written like this:

a×10b

Here we call a the coefficient and b the exponent. But the representation of real numbers in programming language has a little different; we use the character e or E to indicate the start of the exponent. For example, 2×103 in the programming language is written as 2e3. And the exponent part of the real number is not all necessary so that the numbers as "6", "6.5" without an exponent are also valid real number.

Real numbers may have a decimal point in the coefficient (and must have numbers on at least one side of the decimal point, e.g. "0.1", ".1", "1.0", "1. ", are all valid real numbers, but "." is not.).

The exponent of the real number is an integer and starts with the character e or E. Before the character e or E, there must have a valid coefficient.

There may be a plus or minus sign in front of the coefficient or exponent, or both (without any blank characters after the sign). e.g. "-0.1", "1.1e-1" are valid but "-.", "1.1e-", "1.e 3" are not.

Note that there is no bound on the range of the numbers in the input, but for the sake of simplicity, you may assume the input strings are not longer than 1000 characters. There are no blanks in the input data.

Input

The first line of the input contains a single integer T which is the number of test cases, followed by T lines each containing the input line for a test case.

Output

The output contains T lines, each having a string which is “YES” or “NO”.

Sample Input

4

1.5e+2

3.

2.e

-.35

Sample Output

YES

YES

NO

YES

Problem D. OSU! Scoring System Description

OSU! is a rhythm game based on the gameplay of a variety of popular commercial rhythm games. The gameplay consists of only three elements: hit circles on the screen, dragging a ball across a fixed path and rotating a spinner very fast. To simplify the calculation, we assume that there are only hit circles in this game.

Here?s the scoring system of this game:

Hit circle judgment

You get a 300, 100 or 50 from a normal hit circle depending on how accurately you click on it. If you do not click on the hit circle at all or click on it way too early you will receive a miss.

Combo

The initial of your combo is 0, and each successful hitting (300,100 or 50) add 1 point to your combo. A miss will reset your combo to 0.

Score

The score given by each hit circle is calculated with the following formula:

Score = HitValue + HitValue * (Combo multiplier * Difficulty multiplier * Mod multiplier) / 25

Hit value = The hit circle judgment (50, 100 or 300).

Combo multiplier = The max value between (Combo before this hit - 1) and 0. Difficulty multiplier = The difficulty setting for the beatmap.

Mod multiplier = The multiplier of the selected mods.

The total score is the sum of score given by each hit circle.

Accuracy

Accuracy = Total points of hits / (Total number of hits * 300) *100%

Total number of hits = (Number of misses + Number of 50's + Number of 100's + Number of 300's)

Total points of hits = (Number of 50s * 50 + Number of 100s * 100 + Number of 300s * 300)

In other words, each miss counts as 0 points, each 50 counts as 50 points, each 100 as 100 points and each 300 as 300 points. Add them all together and divide the sum with the number of hits multiplied by 300. If you score only 300s you will get a result of 1.00 which means 100% accuracy. If you score only 100s you will get a result of

0.3333 which means 33.33% accuracy.

Grades

After each play, you will get your grade according to your performance.

SS = 100% accuracy

S = Over 90% 300s, less than 1% 50s and no misses.

A = Over 80% 300s and no misses OR over 90% 300s.

B = Over 70% 300s and no misses OR over 80% 300s.

C = Over 60% 300s.

D = Anything else.

Input

The first line contains a non-negative integer N, the number of test cases, at most 100. The first line of each test case contains three numbers, D, M and L (1 ≤ D ≤ 5, 1 ≤ M ≤ 1.5, 1 ≤ L ≤ 1000). D means Difficulty multiplier, M means Mod multiplier and L means the number of hit circles.

The second line of each test case contains L integers (0, 50, 100 or 300), which denote your performance of each hit circle. 0 means a miss.

Output

For each case, out put the total score, accuracy and grade on a line. (Accurate to two digits after decimal point.).

Sample Input

2

1 1.1 5

300 300 300 300 300

2 1.0 6

300 0 100 300 300 300

Sample Output

1579.20 100.00% SS

1372.00 72.22% C

Problem E. 五一步行街购物Description

五一劳动节到了，焦同学要陪女朋友去步行街购物，但是五一去步行街购物的人相当多，大街上、商店里到处都是人，相当拥挤。焦同学想节省购物时间，不愿陪女朋友在街上来回走动，所以他计划一直从街头走向街尾，沿途所经过的商店里如果有他女朋友所需的商品，他就可以考虑购买。现在焦同学手上有份购物清单，并且也有份关于步行街旁各商店所出售的商品的名称及价格的详单。因为要买的东西太多，为避免买漏了东西，现在他计划按照购物清单上的顺序，依次购买各个物品，并且还要使总的费用最小。请问如何设计才能帮助焦同学实现他的计划。

为方便起见，用数字来代替商品的名称。关于详单上的记录，是按照各商店在步行街上的位置的先后关系依次给出各商店所出售的某种商品的名称及价格（对于每个商店仅给出一种所出售的物品的名称及价格，可以认为该商店只有这一种商品可以出售）。举个例子，下面的图一表示购物清单的内容，图二表示详单的内容（S1表示街头处的商店，S n表示街尾处的商店）。

图一

图二

Input

有多组测试数据。对于每一组测试数据，第一行有两个数字M和N，M (1 ≤M ≤ 100)表示购物清单上需要购买的商品的数量，N(1 ≤ N ≤ 100000)表示详单上商店的数量，接下来一行为M个整数，依次表示购物清单上的物品名称，再接下来有N行，每行有两个整数，其中第i行第一个数字表示商店S i所出售物品的名称，第二个数字表示商店S i所出售物品的价格。当M=N=0时表示输入结束。

Output

对于每组测试数据，如果能帮完成购物计划，则输出完成购物计划最少需要的费用，若不能完成购物计划，则输出“Impossible”。

Sample Input

4 8

2 2 5 1

2 50

3 80

2 40

5 60

2 42

5 65

4 100

1 30

2 3

3 2

1 200

2 300

3 100

0 0

Sample Output

177

Impossible

Problem F. The Composition of Letters Description

Given a list of n letters (A1, A2, A3… A n) and a word W. The letters and the word are in capitals. Each letter has a value which is its sequence in the alphabet. For example, …A? has a value that equal s to 1, …B? has a value that equal to 2. The word W has a value which is the su m of its letters? value, For example, …ATM? has a value that equal to 34(34=1+20+13). Find all different compositions have the same sum using the value of the letters from the list that add up to the value of the word W. For example, n = 6, the list is [A, A, B, C, D, E], and the word is ADD, then there are five different compositions of letters: AABE, AACD, ACE, BCD, DE. (A letter can be used within a composition as many times as it appears in the list.) Your job is to solve this problem in general.

Input

The first line is a integer T, which is the number of test case. Each test case contains n, the number of letters in the list, followed by n letters A1, A2, A3,…, A n. And the last of the line is a word W (the length of the word W will be less than 30). n will be a positive integer less than 40. All letters will be separated by exactly one space. The letters in each list appear in alphabet order, and there may be repetitions.

Output

For each test case, the first part contains one line, you should output `Case k', k is the sequence of the test case. In the second part you should output each composition, one per line; if there are no composition, output the line `NONE'. The letters within each composition must appear in alphabet order. A letter may be repeated in the composition as many times as it was repeated in the original list. The compositions themselves must be sorted in alphabet order based on the letters appearing in the compositions. In other words, the compositions must be sorted by their first letter; compositions with the same first letter must be sorted by their second letter; compositions with the same first two letters must be sorted by their third letter; and so on. Within each test case, all compositions must be distinct; the same compositions cannot appear twice.

Sample Input

3

5 A B L M N AN

6 A A B C D E ADD

7 B C F G I J K OK Sample Output

Case 1

ABL

AN

BM

Case 2

AABE

AACD

ACE

BCD

DE

Case 3

BCJK

BFGK

CFGJ

FIK

GIJ

Problem G. Max DPS

Description

Liam 喜欢玩电脑游戏，他的最爱是“World of Bugcraft”。Liam在游戏中扮演了一个法师。法师通过吟唱法术攻击敌人。由于一开始Liam非常弱小，他只会一种法术—“火球术”，每次施展火球术都要消耗他3.5秒的施法时间。每个火球术对敌人造成1000点的基础伤害。有时候，火球术会造成致命一击，这时，火球术便会造成双倍伤害（初始情况下，Liam施放的“火球术”有10%的几率造成致命一击）。

World of Bugcraft 给玩家提供了一定的“能力点”，玩家可以自由分配能力点来强化三项属性：法术能量、致命几率和施法速度。

法术能量：每一点“能力点”可以转化为一点法术能量，每一点法术能量都能提高Liam施放的法术所造成的伤害。例如Liam有20点法术能量，那么他的火球术就能造成1000+20=1020点伤害，如果这次火球术产生了致命一击，那么就造成1020*2=2040点伤害。

致命几率：每20点“能力点”可以转化为1%的致命几率，假设Liam使用了30点“能力点”用于强化致命几率，那么他就有（10+30/20）%=11.5%的致命几率。当然,致命几率的上限为100%。

施法速度：每15点“能力点”可以转化为1%的施法速度。假设Liam使用了150点“能力点”用于强化施法速度，那么他施放火球术的时间就变成了3.5/(1+(150/15)%)=35/11s。

在游戏中，玩家们经常以每秒伤害量DPS（Damage Per Second）来衡量角色的强弱。计算DPS的公式如下：

f = B*(1+C)/T

其中B表示单个法术在未产生致命一击时的伤害。C表示致命一击的几率，T表示单个法术的施法时间。

现在我们可以计算初始情况下Liam的DPS期望值：

f1 = 1000*(1+10%)/3.5 =314.286

假如Liam有200点“能力点”，并且他将20点转化为法术能量，30点转化为致命几率，150点转化为施法速度，那么他的DPS期望值就变成了

f2=1020*（1+11.5%）/(35/11)=357.437

可见分配了“能力点”后LIAM的DPS有了很大提高，可是这样的分配方案显然不能最大化Liam的DPS，如果Liam将200点“能力点”全部转化为法

术能量，那么他的DPS期望值就变成了

f3=1200*(1+10%)/3.5=377.143

f3是能力点S=200时所能达到的最大DPS值，可是当S不等于200时呢？你能帮助他找到最优的分配方案，计算出最大化的DPS吗？（假设能力点可以拆分成非整数来分配）

Input

第一行，一个正整数N，表示测试用例的数目

第2到N+1行，每行一个正整数S（0 < S ≤ 10000）,S表示Liam拥有的能力点数。

Output

每个测试用例占一行，输出最大可能的DPS，保留小数点后3位有效数字。

Sample Input

2

200

3000

Sample Output

377.143

1610.346

Problem H. Minimum Circle Description

zfy lives in a city where has n crossings (0 < n≤ 100, the crossings are labeled as 0, 1, 2 ... n-1. And we can regard each crossing as a vertex of a graph.), m roads (0 ≤ m ≤n(n-1), every road connects two crossings, and for some reason all the roads are one-way-roads, thus they can be regarded as directed edges of a graph).

Now comes the problem: zfy wants to locate his new home to one of the crossings which is included in the circle that has the minimum total length so that it could be convenient to go somewhere outside and back to home. But the problem seems a little complex to him, so he turns to you for helping him calculate the length of the minimum circle by programming.

Input

The first line of the input file contains a single integer T: the number of test cases. The first line for each test case contains two integers: n and m, followed by m lines. Each of the m lines has three integers u, v, w (0 ≤u, v < n; 0 < w < 10^7), described a road of length w which connect the u th crossing and the v th crossing of the city.

Output

For each test case, output one line contains exactly one integer, which is the length of the minimum circle of the city. If there is no circle in the city, just output -1.

Sample Input

1

4 6

0 1 3

2 0 5

1 2 3

2 1 2

1 3 1

3 2 1

Sample Output 4

Problem I. Kevin的书架

Description

Kevin是个爱读书，爱藏书的孩子。Kevin的寝室有一个书架，能够整整齐齐地容纳k本书。但是这个书架太小了，放不下他的所有书，而另一方面他的衣柜很大可他却没多少衣服，于是他把书都胡乱地塞在衣柜里面。

每个学期伊始，Kevin都会给自己定一个长度为n读书计划列表，上面依次显示了Kevin在接下来的n天中，每天要读的书籍（假设Kevin每天只读一本书）。

每天读书之前，Kevin必须检查，他所要的书是否在他的书架上，如果在，就直接从书架上取下来。但是如果不在，就需要从乱起八糟的衣柜中把书找出，但是Kevin读书有个怪癖，比如说在衣柜中找到了要读的书x，他不是直接阅读x，而是先要将这本书放到书架上（如果书架满了，就先把书架上的另一本书y 扔回衣柜中去，以空出位置来放书x），然后再将x从书架上取下来，安安心心地阅读。Kevin每读完一本书，就会把书放回到书架。假设一开始所有的书都在衣柜里，书架上没有放一本书。

现在的问题是：每次在乱哄哄（也许同样臭烘烘）的衣柜中找书并不是一件快乐的经历，所以每次选择放回衣柜的书y时，必须慎重地选择，现在需要你为他制定一个计划，让他在n天中，从衣柜中找书的次数最少。

Input

第一行有一个整数T，表示测试数据的组数。

接下来有T组数据，对于每组数据：

第一行是两个整数k, n ( 0 < k < 100, 0 < n < 10000)，分别表示Kevin的书架能容纳的书的数量和他读书的天数。接下来是n行，每行有一个整数x (0 ≤x < n)，表示Kevin当天要读的书的编号。

Output

一个整数，表示Kevin最少需要从衣柜中找多少次书。

Sample Input

2

2 7

1

2

3

1

3

1

3

3 9

1

2

3

4

1

2

1

2

4

Sample Output

3

4

Problem J. Prevent the Enemy Description

Recently, the ACM (A rmy of C razy M an) obtains a pressing message that its enemy is trying to cross the defense area they guard. Now we know the defense area is as the following rectangle:

The size of height AB is a, and the width AC is b (So that the coordinate of B: (0, 0), C: (b, a)). There are N towers in the defense area, and the guard area of every tower is a circular region of R as its radius. Now the spy is on AB, and wants to cross the defense area to CD without discovered by the towers. So the ACM decides to build some new towers. They want to know how many new towers should be built at least to prevent the spy crossing the area.

Input

The first line of the input is an integer T (T < 100), corresponding to the number of test case.

For each test case:

The first line has four integers: a, b, N, R (0 < a < 1000, 0 < b < 1000, 0 ≤ N ≤ 100, 1 ≤ R ≤ 1000). Each of the following N lines contains two integers corresponding to the coordinate of the tower.

Output

Output one line for each test case: the minimum number of the new towers they should build. If there is no need to build any tower, just output “0”.

Sample Input

2

5 10 1 1

1 1

5 10 1 2

1 1

Sample Output

2

1

ACM竞赛试题集锦

取石子游戏 Time Limit:1S Memory Limit:1000K Total Submit:505 Accepted:90 Description 有两堆石子，数量任意，可以不同。游戏开始由两个人轮流取石子。游戏规定，每次有两种不同的取法，一是可以在任意的一堆中取走任意多的石子；二是可以在两堆中同时取走相同数量的石子。最后把石子全部取完者为胜者。现在给出初始的两堆石子的数目，如果轮到你先取，假设双方都采取最好的策略，问最后你是胜者还是败者。 Input 输入包含若干行，表示若干种石子的初始情况，其中每一行包含两个非负整数a和b，表示两堆石子的数目，a和b都不大于1,000,000,000。 Output 输出对应也有若干行，每行包含一个数字1或0，如果最后你是胜者，则为1，反之，则为0。 Sample Input

2 1 8 4 4 7 Sample Output 1 跳蚤 Time Limit:1S Memory Limit:1000K Total Submit:198 Accepted:44 Description Z城市居住着很多只跳蚤。在Z城市周六生活频道有一个娱乐节目。一只跳蚤将被请上一个高空钢丝的正中央。钢丝很长，可以看作是无限长。节目主持人会给该跳蚤发一张卡片。卡片上写有N+1个自然数。其中最后一个是M，而前N个数都不超过M，卡片上允许

有相同的数字。跳蚤每次可以从卡片上任意选择一个自然数S，然后向左，或向右跳S个单位长度。而他最终的任务是跳到距离他左边一个单位长度的地方，并捡起位于那里的礼物。 比如当N=2，M=18时，持有卡片(10, 15, 18)的跳蚤，就可以完成任务：他可以先向左跳10个单位长度，然后再连向左跳3次，每次15个单位长度，最后再向右连跳3次，每次18个单位长度。而持有卡片(12, 15, 18)的跳蚤，则怎么也不可能跳到距他左边一个单位长度的地方。 当确定N和M后，显然一共有M^N张不同的卡片。现在的问题是，在这所有的卡片中，有多少张可以完成任务。 Input 两个整数N和M(N <= 15 , M <= 100000000)。 Output 可以完成任务的卡片数。 Sample Input

安徽ACM省赛试题

2018年安徽省机器人大赛程序设计竞赛

目录A．数7 B．编译错误 C．做操的时候要排好队D．判重 E．最长上升字串 F．雄伟的城堡 G．然后打5 H．运货卡车 I．最大矩形框 J．数列分段 K．数数字

A.数7 时间限制: 3s 描述 求整数序列中位置L到位置R中一共有多少个7。对于每个数7的个数的定义为，十进制各个位置上一共有多少个7，以及能够被7整除的次数。 输入 第一行是一个整数T，代表测试数据的组数。每组数据中两个整数L,R。其中T≤50,L

B.编译错误 时间限制: 3s 描述 在程序员编写程序的时候，通常会引用其他文件，而引用的文件也会引用其它的头文件。但是出现循环引用的现象编译时便会报错。例如A引用了B，B引用了C，C引用了A，那么就产生了循环引用（Circular reference）。考虑另外一个情况，A引用了B和C，B引用D，C引用D，虽然D被引用了两次，但是没有出现循环引用。 输入 第一行是一个整数T，代表测试数据的组数。每组数据中第一行是一个整数n，代表有多少个引用关系。接下来n行每行有2个字符串a,b，用空格分隔，代表a引用了b。其中T≤50, n≤105，每个字符串长度不超过100。 输出 共T行。若不会产生编译错误则输出Passed，否则输出Failed。 样例输入 样例输出

C.做操的时候要排好队 时间限制: 3s 描述 同学们在做早操时，应该按照身高从低到高排好队。但是总是有人不好好排队，老师在审查时会对没有排好的队伍扣除一定的分数。扣的分数被定义为，找到三个人Ai,Aj,Ak，其中i

山东科技大学第二届ACM程序设计大赛试题

山东科技大学 第二届ACM程序设计大赛 试题册 试题共14页，题目共计12道

山东科技大学第二届ACM 程序设计大赛试题册 Problem A 简单计算 Description 给出n 个十进制的数，找出这n 个数的二进制表示中1的个数最少的数。 Input 输入的第一行为一个正整数T （1≤T ≤20）,代表测试数据组数。 对于每组测试数据，输入的第一行为一个正整数n （1≤n ≤10000），第二行为n 个正整数A 1、A 2、…、A n （1≤A i ≤109 ），每个数之间以空格分隔。 Output 每组数据输出一行，先输出数据组数，再输出二进制中含1最少的数，如果存在多个数符合条件，输出最小的那个。具体输出格式见样例输出。 Sample Input Sample Output

山东科技大学第二届ACM 程序设计大赛试题册 Problem B 关键字搜索 Description 我们的新网站具有了全新的搜索功能，使用了2个通配符“*”和“？”，其中“*”表示0或者多个小写字母，“？”代表1个字母。 当我们输入一个关键字的时候，我们在不确定的地方就使用通配符。我们在数据库里面有多条记录，每条记录都是由小写字母组成，现在给出一个关键字，你能告诉我数据库里面有多少条与关键字相匹配的记录吗？ 例如： 如果关键字是j*y*m*y?，那么jiyanmoyu ，jyanmoyu ，jymyu 都是相匹配的记录。 Input 第一行输入一个T （T ≤20），表示有T 组测试数据。对于每组测试数据，第一行是输入的关键字，接下是数据库里面的所有记录的条数n ，1≤n ≤10000,每条记录的长度不超过50个小写字母。 Output 对于每组测试数据，输出与关键字相匹配的总记录条数，占一行。 Sample Input Sample Output

acm程序设计大赛

acm程序设计大赛 一、参赛队的组成： 每只队伍三名参赛队员组成，设队长一名。 超过两名以上选手为女队员的参赛队可认为具有女队的资格。 在解出同等题目的情况下，女队优先，然后再计算时间（争夺第一名时除外）。 二、竞赛过程 竞赛中命题 6 题，比赛时间为5个小时。比赛编程语言为C或C++。 队员在接到题目后，编程进行解答，解答完每道题目，即可将程序通过网络提交，评委当场对提交的程序进行评判，并对提交的时间进行记录，经运行测试后由裁判判为正确或者错误，判决结果由系统自动反馈给参赛队伍。如果正确，就为该队挂上一个气球，不同颜色的气球代表不同的题目。为了增加比赛的紧张气氛，比赛结束前一个小时，停止公布所有的成绩。 参赛队员有权提交解释请求，针对题目描述中的不明确或错误的部分提问。如果裁判确认题目中确实存在不明确或错误的部分，将会通告所有参赛队伍进行声明或更正。 在竞赛中，参赛队员不得和同组成员以及竞赛组委会指定工作人员以外的人交谈；系统支持人员可以回答和系统相关的问题，例如解释系统错误信息。 参赛队员不能携带任何电子设备。允许携带纸质材料，包括源代码，参考书，字典等。 当参赛队伍出现妨碍比赛正常进行的行为时，诸如擅自移动赛场中的设备，未经授权修改比赛软硬件，干扰他人比赛等，都将会被竞赛组委会剥夺参赛资格。 三、竞赛评分 竞赛裁判主要负责当比赛选手对裁判系统的结果提出异议或题目需要人工判别时作出相应解释或判定。竞赛组委会主任在与竞赛裁判组协商后确定获胜队伍，有权根据由于不可预见的事件引起的问题，对结果进行调整，这个决定是最终的。 比赛最终结果由每支队伍解决的题目以及解决时间来决定。解题多者获胜，如果有队伍解题数量相同，则根据总用时加上惩罚时间进行排名。总用时和惩罚时间由每道解答正确的试题的用时加上惩罚时间组成。每道试题用时将从竞赛开始到试题解答被判定为正确为止，期间每一次错误的运行将被加罚20分钟时间，未正确解答的试题不计时。

Acm试题及答案

Acm试题及答案 1001 Sum Problem ............................................. 错误!未定义书签。1089 A+B for Input-Output Practice (I) ...................... 错误!未定义书签。1090 A+B for Input-Output Practice (II) ..................... 错误!未定义书签。1091 A+B for Input-Output Practice (III) .................... 错误!未定义书签。1092 A+B for Input-Output Practice (IV) ...................... 错误!未定义书签。1093 A+B for Input-Output Practice (V) ...................... 错误!未定义书签。1094 A+B for Input-Output Practice (VI) ..................... 错误!未定义书签。1095 A+B for Input-Output Practice (VII) ..................... 错误!未定义书签。1096 A+B for Input-Output Practice (VIII) ................... 错误!未定义书签。2000 ASCII码排序............................................ 错误!未定义书签。2001计算两点间的距离........................................ 错误!未定义书签。2002计算球体积.............................................. 错误!未定义书签。2003求绝对值................................................ 错误!未定义书签。2004成绩转换................................................ 错误!未定义书签。2005第几天.................................................. 错误!未定义书签。2006求奇数的乘积............................................ 错误!未定义书签。2007平方和与立方和.......................................... 错误!未定义书签。2008数值统计................................................ 错误!未定义书签。2009求数列的和.............................................. 错误!未定义书签。2010水仙花数................................................ 错误!未定义书签。2011多项式求和.............................................. 错误!未定义书签。2012素数判定................................................ 错误!未定义书签。2014青年歌手大奖赛_评委会打分............................... 错误!未定义书签。

acm程序设计大赛题目

The Mailboxes Manufacturers Problem Time Limit:1000MS Memory Limit:65536K Total Submit:299 Accepted:227 Description In the good old days when Swedish children were still allowed to blowup their fingers with fire-crackers, gangs of excited kids would plague certain smaller cities during Easter time, with only one thing in mind: To blow things up. Small boxes were easy to blow up, and thus mailboxes became a popular target. Now, a small mailbox manufacturer is interested in how many fire-crackers his new mailbox prototype can withstand without exploding and has hired you to help him. He will provide you with k(1 ≤ k≤ 10) identical mailbox prototypes each fitting up to m(1 ≤ m≤ 100) crackers. However, he is not sure of how many firecrackers he needs to provide you with in order for you to be able to solve his problem, so he asks you. You think for a while and then say, “Well,if I blow up a mailbox I can’t use it again, so if you would provide me with only k = 1 mailboxes, I would have to start testing with 1 cracker, then 2 crackers, and so on until it finally exploded. In the worst case, that is if it does not blow up ev en when filled with m crackers, I would need 1 + 2 + 3 + … + m = m ×(m+ 1) ? 2 crackers. If m = 100 that would mean more than 5000 fire-crackers!” “That’s too many,” he replies. “What if I give you more than k = 1 mailboxes? Can you find a strategy that requires less crackers?” Can you? And what is the minimum number of crackers that you should ask him to provide you with? You may assume the following: 1.If a mailbox can withstand x fire-crackers, it can also withstand x? 1 fire-crackers. 2.Upon an explosion, a mailbox is either totally destroyed (blown up) or unharmed, which means that it can be reused in another test explosion.

2017ACM比赛试题

2017年计算机ACM编程竞赛 主办：计算机科学与技术学院 时间：2017-11-22 18:00---20:00 地点：计算机学院奋进楼4楼5机房

竞赛规则 1、比赛时间为120分钟，从18:00开始，20:00结束。 2、比赛形式为上机编程，每个小组使用三台电脑，可任选语言，同一小组不同题目可使用不同语言； 3、比赛期间可以使用自己电脑，不可查阅书籍、但禁止查阅个人U盘，禁止使用手机、电脑进行上网查询，禁止使用现有代码，违者取消比赛资格；（正式ACM中是可以携带纸质材料的，但由于本次比赛，有大量题目参考书上例题，所以就不让携带了） 4、比赛期间，如遇到设备问题，可举手示意工作人员； 5、由于机房电脑系统有重启还原功能，比赛期间请勿轻易重启电脑； 6、【重要】比赛结束后，请确认将所要提交文件拷至工作人员U盘，否则成绩无效概不负责。 提交方式 1、创建文件夹，文件夹命名格式为小组号-小组队长-组员1-组员2 2、将每一题的源程序文件夹以题目编号命名，拷贝至上述创建的文件夹中 3、在本文档中每题相应位置附上源码及截图（windows截图键:Alt+Prt sc sysrq）,拷贝至上述创建的文件夹中 4、比赛结束后将上述文件夹拷贝至工作人员U盘中，提交方算完成，提交 完成前请勿重启电脑。 注：本次比赛共14题，满分120分。没有完成题目，但有部分解题步骤者按完成度给分。每道题要有注释。

竞赛题目 1. 青年歌手大奖赛中，评委会给参赛选手打分。选手得分规则为去掉一个最高分和一个最低分，然后计算平均得分，请编程输出某选手的得分。输入数据有多组，每组占一行，每行的第一个数是n(2

河南省第四届ACM程序设计大赛原题

所有题目时间限制：1秒 【T1】 序号互换 Dr.Kong 设计了一个聪明的机器人卡多，卡多会对电子表格中的单元格坐标快速计算出来。单元格的行坐标是由数字编号的数字序号，而列坐标使用字符序号。观察字母序号，发现第1列到第26列的字母序号分别为A,B,……,Z,接着，第27列序号为AA，第28列为AB，以此类推。 若给Dr.Kong的机器人卡多一个数字序号（比如32），它能很快算出等价的字母序号（即AF），若给机器人一个字母序号（比如AA），它也能很快算出等价的数字序号（27），你能不能与卡多比试比试，看谁能算得更快更准。 【标准输入】 第一行：N 表示有多少组测试数据。 接下来N行，每行或者是一个正整数，或者是一个仅由大写字母组成的字符串。 【标准输出】 对于每一行测试数据，输出一行。如果输入为一个正整数序号，则输出等价的字母序号；如果输入为字符串，则输出等价的数字序号。 【约束条件】 输入保证，所有数字序号和字母序号对应的数字序号均<=2*10^9 【样例】 【T2】 节能 Dr.kong 设计的机器人卡多越来越聪明。最近市政府公司交给卡多一项任务，每天早晨5：00开始，它负责关掉ZK大道右侧上的所有路灯。 卡多每到早晨5:00准会在ZK大道上某盏灯的旁边，然后他开始关灯。每盏灯都有一定的功率，机器人卡多有自觉的节能意识，它希望在关灯期间，ZK大道右侧上所有的路灯的耗电总量数是最少的。 机器人卡多以1m/s的速度行走。假设关灯动作不需要花费额外的时间，因为当它通过某盏路灯时就

顺手将灯关掉。 请编写程序，计算在给定路灯设置，灯泡功率以及机器人卡多的起始位置的情况下，卡多关灯期间，Zk大道上所有灯耗费的最小能量。 【标准输入】 第一行N 表示ZK大道右侧路灯的数量（2<=N<=1000） 第二行V 表示机器人卡多开始关灯的路灯号。（1<=V<=N） 接下来的N行中，每行包含两个空格隔开的整数D和W，用来描述每盏灯的参数 D表示该路灯与ZK大道起点的距离（用米为单位来表示） W表示灯泡的功率，即每秒该灯泡所消耗的能量数。路灯是按顺序给定的。 （0<=D<=1000,0<=W<=1000） 【标准输出】 输出一个整数，即消耗总能量之和的最小值。注意结果小于200，000,000 【样例】 【T3】 表达式求值 Dr.Kong 设计的机器人卡多掌握了加减运算以后，最近又学会了一些简单的函数求值，比如，它知道函数min(20,23)的值是20，add（10,98）的值是108等等。经过训练，Dr.Kong 设计的机器人卡多甚至会计算一种嵌套的更复杂的表达式。 假设表达式可以简单定义为： 1.一个正的十进制数x是一个表达式。 2.如果x和y是表达式，则函数min（x.y）也是表达式，其值为x，y中最小的数。 3.如果x和y是表达式，则函数max（x，y）也是表达式，其值为x，y中最大数。 4.如果x和y是表达式，则函数add（x，y）也是表达式，其值为x，y之和。 例如，表达式max（add（1,2），7）的值为7. 请编写程序，对给定的一组表达式，帮助DrKong算出正确答案，以便校队卡多计算的正误。

整理出ACM所有题目及答案

1111111杭电： 1000 A + B Problem (4) 1001 Sum Problem (5) 1002 A + B Problem II (6) 1005 Number Sequence (8) 1008 Elevator (9) 1009 FatMouse' Trade (11) 1021 Fibonacci Again (13) 1089 A+B for Input-Output Practice (I) (14) 1090 A+B for Input-Output Practice (II) (15) 1091 A+B for Input-Output Practice (III) (16) 1092 A+B for Input-Output Practice (IV) (17) 1093 A+B for Input-Output Practice (V) (18) 1094 A+B for Input-Output Practice (VI) (20) 1095 A+B for Input-Output Practice (VII) (21) 1096 A+B for Input-Output Practice (VIII) (22) 1176 免费馅饼 (23) 1204 糖果大战 (25) 1213 How Many Tables (26) 2000 ASCII码排序 (32) 2001 计算两点间的距离 (34) 2002 计算球体积 (35) 2003 求绝对值 (36) 2004 成绩转换 (37) 2005 第几天？ (38) 2006 求奇数的乘积 (40) 2007 平方和与立方和 (41) 2008 数值统计 (42) 2009 求数列的和 (43) 2010 水仙花数 (44) 2011 多项式求和 (46) 2012 素数判定 (47) 2014 青年歌手大奖赛_评委会打分 (49) 2015 偶数求和 (50) 2016 数据的交换输出 (52) 2017 字符串统计 (54) 2019 数列有序! (55) 2020 绝对值排序 (56) 2021 发工资咯：） (58) 2033 人见人爱A+B (59) 2037 今年暑假不AC (61) 2039 三角形 (63) 2040 亲和数 (64)

ACM程序设计竞赛例题

备战ACM资料 一：知识点 数据结构： 1，单，双链表及循环链表 2，树的表示与存储，二叉树（概念，遍历）二叉树的应用（二叉排序树，判定树，博弈树，解答树等） 3，文件操作（从文本文件中读入数据并输出到文本文件中） 4，图（基本概念，存储结构，图的运算） 数学知识 1，离散数学知识的应用（如排列组合、简单的图论，数理逻辑） 2，数论知识 3，线性代数 4，组合代数 5，计算几何 二算法 1，排序算法（冒抛法，插入排序，合并排序，快速排序，堆排序） 2，查找（顺序查找，二分发） 3，回溯算法 4，递归算法 5，分治算法 6，模拟法 7，贪心法 8，简单搜索算法（深度优先，广度优先），搜索中的剪枝，A*算法 9，动态规划的思想及基本算法 10，高精度运算 三、ACM竞赛的题型分析 竞赛的程序设计一般只有16种类型，它们分别是： Dynamic Programming （动态规划） Greedy （贪心算法） Complete Search （穷举搜索） Flood Fill （不知该如何翻译） Shortest Path （最短路径） Recursive Search Techniques （回溯搜索技术） Minimum Spanning Tree （最小生成树） Knapsack （背包问题） Computational Geometry (计算几何学) Network Flow （网络流） Eulerian Path （欧拉回路） Two-Dimensional Convex Hull （不知如何翻译） BigNums （大数问题）

Heuristic Search （启发式搜索） Approximate Search （近似搜索） Ad Hoc Problems （杂题） 四ACM竞赛参考书 《实用算法的分析与程序设计》（吴文虎，王建德著，电子工业出版社，竞赛类的黑宝书）《青少年国际和全国信息学（计算机）奥林匹克竞赛指导）――组合数学的算法 和程序设计》（吴文虎，王建德著，清华大学出版社，参加竞赛组合数学必学） 《计算机算法设计与分析》（王晓东编著，最好的数据结构教材） 《数据结构与算法》（傅清祥，王晓东编著，我所见过的最好的算法教材） 《信息学奥林匹克竞赛指导――1997-1998竞赛试题解析》（吴文虎，王建德著，清华大学出版社） 《计算机程序设计技巧》 D.E.Kruth著，算法书中最著名的《葵花宝典》，大师的作品，难度大） 《计算几何》周陪德著 《ACM国际大学生程序设计竞赛试题与解析（一）》（吴文虎著，清华大学出版社） 《数学建模竞赛培训教材》共三本叶其孝主编 《数学模型》第二版姜启源 《随机规划》 《模糊数学》 《数学建模入门》徐全智 《计算机算法设计与分析》国防科大 五常见的几个网上题库 常用网站： 1）信息学初学者之家：https://www.doczj.com/doc/118814234.html,/ （2）大榕树编程世界：https://www.doczj.com/doc/118814234.html,/~drs/program/default.asp （3）中国教育曙光网：https://www.doczj.com/doc/118814234.html,/aosai/ （4）福建信息学奥林匹克：https://www.doczj.com/doc/118814234.html,/fjas/index.htm （5）第20届全国青少年信息学奥林匹克竞赛：https://www.doczj.com/doc/118814234.html,/ （6）第15届国际青少年信息学奥林匹克竞赛：https://www.doczj.com/doc/118814234.html,/ （7）全美计算机奥林匹克竞赛：https://www.doczj.com/doc/118814234.html,/usacogate （8）美国信息学奥林匹克竞赛官方网站：https://www.doczj.com/doc/118814234.html,/ （9）俄罗斯Ural州立大学：http://acm.timus.ru/ （10）西班牙Valladolid大学：http://acm.uva.es/problemset （11）ACM-ICPC：https://www.doczj.com/doc/118814234.html,/icpc/ （12）北京大学：https://www.doczj.com/doc/118814234.html,/JudgeOnline/index.acm （13）浙江大学：https://www.doczj.com/doc/118814234.html,/ （14）IOI：http://olympiads.win.tue.nl/ioi/ （15）2003年江苏省信息学奥林匹克竞赛夏令营：https://www.doczj.com/doc/118814234.html, （16）https://www.doczj.com/doc/118814234.html, （17）https://www.doczj.com/doc/118814234.html, （18）https://www.doczj.com/doc/118814234.html, （19）https://www.doczj.com/doc/118814234.html,/downldmanag/index.asp （20）https://www.doczj.com/doc/118814234.html, colin_fox/colin_fox 五如何备战ACM/ICPC

历届程序设计acm试题

搜集的南开大学的ACM试题与你共享 [A]南开大学Onlinejudge 在线判题系统https://www.doczj.com/doc/118814234.html, A.Lucy的新难题 时间限制：2秒内存限制：32000KB 不知不觉，南开大学第三届“我为程序狂”又要拉开帷幕了。这天，Lucy也来到南开大学ACM协会，与大家共同欢庆NKPC的三周岁的日子。 谈笑间，ACM协会的主席拿了圆形的生日蛋糕。大伙开心地唱完了生日歌，一起吹灭了蜡烛。 要分蛋糕了，大家都很兴奋。本着公平的原则，每位到场的人员都要在蛋糕上切一刀。ACM协会的主席事先知道有n位朋友会参与这个欢庆宴会。为了方便大家切蛋糕，主席在订蛋糕的时候就嘱咐在蛋糕的边缘布置上2n朵小花。 每个人切蛋糕都会从蛋糕的边缘的一朵小花笔直地切到蛋糕的另一端的小花，来表达自己对NKPC的祝福。为了尊重其他同学，每个人在切蛋糕一定不会和蛋糕上已有的切痕相交，也不会从别人已切过的小花作为切蛋糕的起点或终点。同时，每位同学在切蛋糕的时候，都要保证后面所有的同学都能够按照上述的规则切蛋糕。这样，蛋糕上就留下n条切痕。 Lucy眨巴眨巴眼睛，问，要是不考虑切蛋糕的先后顺序和谁切的哪一刀，这蛋糕切完了共有多少种切法呢？ 大家听了呵呵一笑，说，那就把这个问题留给NKPC3，作为《Lucy的新难题》吧。 相信聪明的你，一定能够帮Lucy解答她的难题的，对吗？ 输入包括多组测试数据，你应当处理到输入结束为止。 每组输入数据中，都只有一行，仅包含一个正整数n，且0

桂林电子科技大学ACM程序设计校内竞赛试题

桂林电子科技大学ACM程序设计校内竞赛试题 ▲此套试题共8道，请根据自己实际情况尽最大努力去完成。 ▲每位参赛的同学需在考试用机的工作盘上创建一个名为Exam2004的临时文件夹用以保存所有的工作文件。上机编程调试出正确结果。按照试题顺序把每题的运行结果、源程序和算法说明（即解题思路说明）合并到一个Word 文档。该Word文档的文件名按如下格式命名：学号+姓名最后将该文件拷至制定的服务器上。 1、请看如下图4*4的一个网格。你能告诉我网格中隐含了多少正方形？也许你能手工数出 来，但是你能数100*100或者1000*1000的网格吗？请编写一个程序： 输入：输入一个整数N(0<=N<=100),代表网格的边长 输出：输出2维网格N*N中不同大小的正方形的数目S. 如以上4*4网格共有正方形30 2、对于一个8位二进制码，它的镜像就是将它的第n位于倒数第n位交换，使它的每一位 都这样交换。例如，代表十进制数46的二进制数是00101110。它的镜像是二进制码01110100，即十进制数116。编写一个程序，输入一个整数N(如46)，输出其镜像M(如116)。 3、给你9个整数，这9个整数分别是x的8次方至0次方的系数，请你按照多项式的一般 形式合理地构造（去除不必要的）。例如9个系数分别为0，0，0，1，22，-333，0，1，-1，你要构造并输出一行多项式: x^5+22x^4-333x^3+x-1。要求：可以输入多行系数，再显示结果。 如输入： 0 0 0 1 22 -333 0 1 -1 0 0 0 0 0 0 6 88 0 E(输入结束标志) 输出： x^5+22x^4-333x^3+x-1 6x^2+88x 4、美国人的家族 农夫John对他的奶牛继承关系非常认真。但是他不是一个很好的记录员，他以一种二叉树的方法来记录他奶牛的继承关系。他用字符串来记录一棵树的前序、中序遍历，而不是用图形方式来表示这棵树。你的任务是对于给出的奶牛继承关系的前序树和中序树表示，找出它的后序树表示。每个奶牛的名字用一个字母来代表。 输入规范 第一行输入中序序列 第二行输入前序序列 输出规范 显示后序序列 实例输入 In order: AEDFCHG // 中序序列输入

acm编程比赛题

比赛试题 主办方：迅翔计算机协会

【问题描述】 这是一个古老而又经典的问题。用给定的几种钱币凑成某个钱数，一般而言有多种方式。例如：给定了6种钱币面值为2、5、10、20、50、100，用来凑15元，可以用5个2元、1个5元，或者3个5元，或者1个5元、1个10元，等等。显然，最少需要2个钱币才能凑成15元。 你的任务就是，给定若干个互不相同的钱币面值，编程计算，最少需要多少个钱币才能凑成某个给出的钱数。 【要求】 【数据输入】输入可以有多个测试用例。每个测试用例的第一行是待凑的钱数值M（1 <= M <= 2000，整数），接着的一行中，第一个整数K（1 <= K <= 10）表示币种个数，随后是K 个互不相同的钱币面值Ki(1 <= Ki <= 1000)。输入M=0时结束。 【数据输出】每个测试用例输出一行，即凑成钱数值M最少需要的钱币个数。如果凑钱失败，输出“Impossible”。你可以假设，每种待凑钱币的数量是无限多的。 【样例输入】 15 6 2 5 10 20 50 100 1 1 2 【样例输出】 2 Impossible

【问题描述】 Felicia 的生日是11月1日（和Kitty是同一天生的哦）。于是Feli请来Kitty一起过生日。Kitty带来了最新款的“Kitty猫”玩具准备送给Feli，不过她说，这份礼物可不是白送的。Feli要帮她一个忙，才能够得到心仪已久的玩具。Kitty说，“Kitty猫”玩具已经卖出了n!个，n<=10^100 *_*，Kitty想知道确切的数字，而不是无聊的“一个数加个感叹号”。Feli 听了大吃一惊。要知道，算出n!是一个无比艰巨的任务。Feli告诉Kitty，就算Feli算出n!，Kitty也看不下去，因为当n=20 时，计算机的长整型已经存不下了（Kitty只能接受1-9之间的数字）。于是Kitty说，你只要告诉我n!最后一位非0的数就可以了。Feli想了想，立刻动手写了个程序算出了正确的答案。现在，请你也试试看！注意哦，AC的男生将会得到一个“Hello Kitty”计算器（可编程，CPU 1THz，Mem 1TMB），AC的女生将会得到一个仿真“Hello Kitty”宠物（善解人意，无须喂养，智商1101，附带写情书功能）。 【要求】 【数据输入】每行一个n，直到输入数据结束 【数据输出】对应输入的n，每行输出一个答案 【样例输入】 1101 【样例输出】 8

辽宁省acm竞赛赛题

Dinner Description Little A is one member of ACM team. He had just won the gold in World Final. To celebrate, he decided to invite all to have one meal. As bowl, knife and other tableware is not enough in the kitchen, Little A goes to take backup tableware in warehouse. There are many boxes in warehouse, one box contains only one thing, and each box is marked by the name of things inside it. For example, if "basketball" is written on the box, which means the box contains only basketball. With these marks, Little A wants to find out the tableware easily. So, the problem for you is to help him, find out all the tableware from all boxes in the warehouse. Input There are many test cases. Each case contains one line, and one integer N at the first, N indicates that there are N boxes in the warehouse. Then N strings follow, each string is one name written on the box. Output For each test of the input, output all the name of tableware. Sample Input 3 basketball fork chopsticks 2 bowl letter Sample Output fork chopsticks bowl HINT： The tableware only contains: bowl, knife, fork and chopsticks.

2008年ACM大学生程序设计竞赛题

计算机科学系第二届大学生程序设计竞赛试题题目一 大数乘法 问题描述（Problem Description）： 编程实现位数不超过300位的任意大的两个整数相乘。 输入（Input）： 提示用户输入第一个大数乘数和第二个大数乘数。 输出（Output）： 输出两个大数的乘积。 输入示例（Sample Input）： 请输入第一个乘数：123456789123456 请输入第二个乘数：123456789123456 输出示例（Sample Output）： 两数的乘积是：15230578580673373689799383936

四三二五六一题目二 排球队员站位问题 问题描述（Problem Description）： 左图为排球场的平面图，其中一、二、三、 四、五、六为位置编号，二、三、四号位置为前排，一、六、五号位为后排。某队比赛时，一、四号位放主攻手，二、五号位放二 传手，三、六号位放副攻手。队员所穿球衣分别为１，２，３，４，５，６号，但每个队员的球衣都与他们的站位号不同。已知１号、６号队员不在后排，２号、３号队员不是二传手，３号、４号队员不在同一排，５号、６号队员不是副攻手。 编程求每个队员的站位情况。 输入（Input）： 输出（Output）： 输出每个队员球衣号码和所站的位置编号。 输入示例（Sample Input）： 输出示例（Sample Output）： 球衣号码：1 2 3 4 5 6 位置编号：一 二 三 四 五 六

题目三文件读写 问题描述（Problem Description）： INI文件为一种广泛应用的储存程序配置的文件格式。要求不使用操作系统自带INI文件处理功能，用c++编写一个INI文件读取程序，并把结果输出到显示器及文件result.txt中。 说明： INI文件的结构： [区名字] # 区名注释 键名=键值 # 键值注释 一个区里可以有几个不同键名的键值，例如： 测试用INI文件test.ini： [section] #this is a section comment key=value #this is a key comment [section2] key2=value2 要求程序能读取section2区中键名为key2的值，以及section区中的键名为key的注释。 输入（Input）： 在Windows命令窗口里输入程序名称来运行程序，注意程序所带参数。 输出（Output）： 第一行输出section2区中键名为key2的值。 第二行输出section区中的键名为key的注释。 同时要把此结果输出到显示器和文件result.txt中。 输入示例（Sample Input）： CppFileRW Test.ini 输出示例（Sample Output）： section2区中键名为key2的值是：value2 section区中的键名为key的注释是：this is a key comment

ACM程序设计竞赛例题[1]

备战ACM资料 习题 1． 0-1背包问题 在0 / 1背包问题中，需对容量为c 的背包进行装载。从n 个物品中选取装入背包的物品，每件物品i 的重量为wi ，价值为pi 。对于可行的背包装载，背包中物品的总重量不能超过背包的容量，最佳装载是指所装入的物品价值最高。 程序如下： #include <> void readdata(); void search(int); void checkmax(); void printresult(); int c=35, n=10; "); printf("\n"); } printf("\n"); } 6．素数环问题 把从1到20这20个数摆成一个环，要求相邻的两个数的和是一个素数。 分析：用回溯算法，考察所有可能的排列。 程序如下： #include <> #include <> void search(int); void init(); 表示空格；’X’表示墙。 程序如下：

#include <> #include <> void search(int,int); int canplace(int,int); void readdata(); Floodfill 给一个20×20的迷宫和一个起点坐标，用广度优先搜索填充所有的可到达的格子。 提示：参考第2题。 2. 电子老鼠闯迷宫 如下图12×12方格图，找出一条自入口（2，9）到出口（11，8）的最短路 本题给出完整的程序和一组测试数据。状态：老鼠所在的行、列。程序如下： #include<> void readdata(); a[i][j]=0; .... 注：测试数据可在运行时粘贴上去（点击窗口最左上角按钮，在菜单中选则“编辑”/“粘贴”即可）。 想一想：此程序都存在哪些问题，如果openlen太小程序会不会出错，加入代码使程序能自动报出此类错误。 3.跳马 给一个200×200的棋盘，问国际象棋的马从给定的起点到给定的终点最少需要几步。 Sample Input 0 0 1 1 Sample output 4 状态：马所在的行、列。 程序如下： #include<> void readdata(); 独轮车