没有合适的资源?快使用搜索试试~ 我知道了~
2021年ACM-ICPC程序设计竞赛济南站正式赛题目
需积分: 6 0 下载量 34 浏览量
2023-04-06
11:00:58
上传
评论 1
收藏 1.09MB PDF 举报
温馨提示
试读
21页
本资源为2021年ACM-ICPC程序设计竞赛济南站的正式赛题目,比赛时长一共五小时,题目为全英文题目,并且在比赛的时候可以使用一切纸质书籍,但禁止使用电子产品,一组三个队员,只允许使用一台电脑,不过可以配备打印机去打印题目。
资源推荐
资源详情
资源评论
The 2021
Asia Jinan Regional Contest
Contest Session
November 14, 2021
Problems
A. Space Station
B. Monitored Area
C. Optimal Strategy
D. Arithmetic Sequence
E. Insidemen
F. Neural Network Counting
G. Happy Alice
H. Game Coin
I. Permutation Pair
J. Determinant
K. Search for Mafuyu
L. Strange Series
M. Coloring Rectangles
Do not open before the contest starts.
Prepared by Peking University
The 2021 ICPC Asia Jinan Regional Contest
China, Jinan, November 14, 2021
Problem A. Space Station
Input file: standard input
Output file: standard output
Time limit: 5 seconds
Memory limit: 512 megabytes
“TianTing” is a huge space station. It consists of several thin cylindrical capsules. There is a joint on each
end of a capsule. One joint may connect to several capsules.
If we take joints as nodes and take capsules as edges the structure of the space station can be seen as a
tree.
The structure of space station corresponding to the sample input.
The shape of the space station can be shifted by rotating capsules around joints. At the beginning
directions, (from one end to the other) of all the capsules are parallel to the 3D coordinate axes. A
capsule can rotate around a joint of its either end as pivot arbitrarily as long as its final direction is
still parallel to one of the axes. Note all the capsules which are connected to the other end (directly or
indirectly) will also rotate at the same time. You do not need to worry about any collisions or overlapping
of capsules. Assume they can “pass through” each other safely.
Given the shape of the space station at the beginning and a sequence of rotations afterwards can you tell
the Euclidean distance between two given joints?
Input
The first line contains two integers N and Q (2 ≤ N ≤ 10
5
, 1 ≤ Q ≤ 10
5
) – the number of joints and the
Page 1 of 20
The 2021 ICPC Asia Jinan Regional Contest
China, Jinan, November 14, 2021
number of operations.
Each of the following N − 1 lines contains three integers u, v, w (1 ≤ u, v ≤ N, u 6= v, 1 ≤ w ≤ 10
6
) and
two characters which means there is a capsule of length w between joint u and joint v. The two characters
are one of “x+”, “x-”, “y+”, “y-”, “z+”, “z-” which represents the direction of the capsule from joint u to
joint v. It is guaranteed that the given structure is a tree.
Each of the following Q lines contains an operation. There are two types of operation: rotation of capsule
and query on Euclidean distance of two given joints.
The first type is described as follows:
1 u v axis degree
Where u and v (1 ≤ u, v ≤ N, u 6= v) are two joints, axis is one of “x”, “y” or “z” and degree is an
integer either 90, 180 or 270. It means we rotate the capsule connecting joint u and joint v degree degrees
following right-hand rule, using the line which points to the positive direction of axis through joint u
as pivot. It is guaranteed that joint u and joint v are connected by a capsule. See the following pictures
for more information about rotation.
Rotation operation: 1 1 3 z 270
Page 2 of 20
The 2021 ICPC Asia Jinan Regional Contest
China, Jinan, November 14, 2021
Rotation operation: 1 3 1 x 90
The second type is described as follows:
2 u v
This means you should tell the Euclidean distance between joint u and joint v (1 ≤ u, v ≤ N ).
Again, you do not need to worry about any collisions or overlapping of capsules. Assume they can “pass
through” each other safely.
Output
For each second type operations output one line contains the distance. Your answer should have an
absolute or relative error less than 10
−9
. Namely, if your answer is a and the jury’s answer is b, then your
answer is accepted if
|a − b|
max(1, |b|)
≤ 10
−9
.
Page 3 of 20
剩余20页未读,继续阅读
资源评论
凉云生烟
- 粉丝: 2w+
- 资源: 9
上传资源 快速赚钱
- 我的内容管理 展开
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功