【免费】2018年ACM国际大学生程序设计竞赛真题_acm程序设计大赛题库

需积分: 0 63 浏览量更新于2023-05-22 评论 6 收藏 1.49MB PDF 举报

身份认证购VIP最低享 7 折!

领优惠券(最高得80元）

资源详情

资源评论

资源推荐

Problem A

Catch the Plane

Time limit: 10 seconds

Your plane to the ICPC Finals departs in a short time, and the only way to get to the airport is by bus.

Unfortunately, some of the bus drivers are considering going on strike, so you do not know whether

you can get to the airport on time. Your goal is to plan your journey in such a way as to maximize the

probability of catching your plane.

You have a detailed map of the city, which includes all the bus stations. You are at station 0 and the

airport is at station 1. You also have a complete schedule of when each bus leaves its start station and

arrives at its destination station. Additionally, for each bus you know the probability that it is actually

going to run as scheduled, as opposed to its driver going on strike and taking the bus out of service.

Assume all these events are independent. That is, the probability of a given bus running as planned does

not change if you know whether any of the other buses run as planned.

If you arrive before the departure time of a bus, you can transfer to that bus. But if you arrive exactly

at the departure time, you will not have enough time to get on the bus. You cannot verify ahead of time

whether a given bus will run as planned – you will ﬁnd out only when you try to get on the bus. So if

two or more buses leave a station at the same time, you can try to get on only one of them.

20%

Bus Schedule

Start

Station

Destination

Station

Departure

Time

Arrival

Time

100

500

501

200

500

550

700

900

500

700

701

400

800

650

900

10%

50%

10%

90%

10%

Figure A.1: Bus schedule corresponding to Sample Input 1.

Consider the bus schedule shown in Figure A.1. It lists the start and destination stations of several bus

routes along with the departure and arrival times. You have written next to some of these the probability

that that route will run. Bus routes with no probability written next to them have a 100% chance of

running. You can try catching the ﬁrst listed bus. If it runs, it will take you straight to the airport, and

you can stop worrying. If it does not, things get more tricky. You could get on the second listed bus to

station 2. It is certain to leave, but you would be too late to catch the third listed bus which otherwise

would have delivered you to the airport on time. The fourth listed bus – which you can catch – has only

a 0.1 probability of actually running. That is a bad bet, so it is better to stay at station 0 and wait for

the ﬁfth listed bus. If you catch it, you can try to get onto the sixth listed bus to the airport; if that does

not run, you still have the chance of returning to station 0 and catching the last listed bus straight to the

airport.

ACM-ICPC World Finals 2018 Problem A: Catch the Plane 1

Problem B

Comma Spr inkler

Time limit: 8 seconds

Photo by Tanya Hart. Yarn

pattern by Morgen Dämmerung.

As practice will tell you, the English rules for comma placement are complex, frus-

trating, and often ambiguous. Many people, even the English, will, in practice,

ignore them, and, apply custom rules, or, no rules, at all.

Doctor Comma Sprinkler solved this issue by developing a set of rules that sprinkles

commas in a sentence with no ambiguity and little simplicity. In this problem you

will help Dr. Sprinkler by producing an algorithm to automatically apply her rules.

Dr. Sprinkler’s rules for adding commas to an existing piece of text are as follows:

1. If a word anywhere in the text is preceded by a comma, ﬁnd all occurrences of that word in the text,

and put a comma before each of those occurrences, except in the case where such an occurrence

is the ﬁrst word of a sentence or already preceded by a comma.

2. If a word anywhere in the text is succeeded by a comma, ﬁnd all occurrences of that word in the

text, and put a comma after each of those occurrences, except in the case where such an occurrence

is the last word of a sentence or already succeeded by a comma.

3. Apply rules 1 and 2 repeatedly until no new commas can be added using either of them.

As an example, consider the text

please sit spot. sit spot, sit. spot here now here.

Because there is a comma after spot in the second sentence, a comma should be added after spot in

the third sentence as well (but not the ﬁrst sentence, since it is the last word of that sentence). Also,

because there is a comma before the word sit in the second sentence, one should be added before that

word in the ﬁrst sentence (but no comma is added before the word sit beginning the second sentence

because it is the ﬁrst word of that sentence). Finally, notice that once a comma is added after spot

in the third sentence, there exists a comma before the ﬁrst occurrence of the word here. Therefore, a

comma is also added before the other occurrence of the word here. There are no more commas to be

added so the ﬁnal result is

please, sit spot. sit spot, sit. spot, here now, here.

Input

The input contains one line of text, containing at least 2 characters and at most 1 000 000 characters.

Each character is either a lowercase letter, a comma, a period, or a space. We deﬁne a word to be a

maximal sequence of letters within the text. The text adheres to the following constraints:

• The text begins with a word.

• Between every two words in the text, there is either a single space, a comma followed by a space,

or a period followed by a space (denoting the end of a sentence and the beginning of a new one).

• The last word of the text is followed by a period with no trailing space.

ACM-ICPC World Finals 2018 Problem B: Comma Sprinkler 3

Problem C

Conquer The World

Time limit: 8 seconds

Bwahahahahaha!!! Your nemesis, the dashingly handsome spy Waco Powers, has at last fallen to your

secret volcano base’s deathtraps (or so you assume, being a little too busy to witness it ﬁrsthand). At

long last, you are all set to CONQUER THE WORLD!

Nothing will stand in your way! Well, nothing except a minor problem of logistics. Your evil armies

have announced that they will not continue carving their relentless path of destruction across the puny

nations of the world without being paid. And unfortunately you are running low on cash – a volcano

lair has many wonderful qualities, but “reasonably affordable” is not one of them. You have had to pull

funds from the travel budget to pay your ungrateful underlings. Now you are not sure how you will

actually get your armies into position to CONQUER THE WORLD.

You have a map of the nations of the world and all your available transport routes between them. Each

route connects two nations and has a ﬁxed cost per army that uses it. The routes are laid out such that

there is exactly one way to travel between any two nations. You know the current position of each of

your armies and how many you will need to place permanently in each nation in order to subjugate it.

How can you move the armies into place as cheaply as possible so you can CONQUER THE WORLD?

Input

The ﬁrst line of input contains an integer n (1 ≤ n ≤ 250 000), the number of nations. This is followed

by n − 1 lines, each containing three integers u, v, and c (1 ≤ u, v ≤ n, 1 ≤ c ≤ 10

), indicating that

there is a bidirectional route connecting nations u and v, which costs c per army to use.

Finally, another n lines follow, the i

of which contains two non-negative integers x

and y

, indicating

that there are currently x

armies in nation i, and you need at least y

armies to end up in that nation in

the ﬁnal conﬁguration. The total number of armies (the sum of the x

values) is at least the sum of the

values, and no more than 10

Output

Display the minimum cost to move your armies such that there are at least y

armies in nation i for all i.

Sample Input 1 Sample Output 1

1 2 5

3 1 5

2 1

5 0

1 3

ACM-ICPC World Finals 2018 Problem C: Conquer The World 5

剩余21页未读，继续阅读

nibolyoung

粉丝: 12
资源: 24

会员权益专享

2018年ACM国际大学生程序设计竞赛真题

评论0

会员权益专享

最新资源

2018年ACM国际大学生程序设计竞赛真题

评论0

ACM试题集和答案

ACM练习题及答案整理

ACM大学生程序设计竞赛在线题库精选题解

ACM Transactions on Internet Technology, 2018年11月出版

"2021年3月ACM经济计算交易中基于信号传递成本的机制设计揭示原理

基于模型检查的Web应用程序设计

科学直接获取船舶运动仿真计算设计与工程杂志，2018年285卷

闪存技术中基于WOM代码的页面重用分析-ACM存储交易,Vol.141,2018年2月

acm国际大学生程序设计竞赛试题与解析

acm国际大学生程序设计竞赛真题

acm国际大学生程序设计竞赛知识与入门 俞勇 pdf

acm国际大学生程序设计竞赛 pdf

ACM国际大学生程序设计竞赛官网

acm-icpc国际大学生程序设计竞赛 知识与入门

有什么程序设计竞赛是针对研究生的呢？

讲讲蒋凌宇的算法竞赛经历

山东省2018acm试题

acm程序设计 pdf

acm程序设计竞赛基础教程(第2版 ) pdf

研究生还能参加哪些程序设计竞赛

会员权益专享

最新资源

acm国际大学生程序设计竞赛知识与入门俞勇 pdf

acm-icpc国际大学生程序设计竞赛知识与入门