没有合适的资源?快使用搜索试试~ 我知道了~
首页ACM-ICPC 2020年上海区域赛正式赛试题
资源详情
资源评论
资源推荐
ICPC 2020, Shanghai Site
China, Shanghai, Dec, 13, 2020
Problem A. Wowoear
Input file: standard input
Output file: standard output
Time limit: 3 seconds
Memory limit: 1024 megabytes
Wowo is a solo adventurer who completed many dangerous journeys on his own foot in forests, deserts and
even glaciers. The Shanghai ICPC (Shanghai Invitational Contest on Programmable Cheating) committee
invited Wowo as a tester of their new running trial.
The trial can be described as a 2D simple polyline (p
1
, . . . , p
n
). In other words, the trial consists of
n − 1 line segments (p
1
, p
2
), . . . , (p
n−1
, p
n
). The line segments do not intersect with each other except that
two consecutive line segments (p
i
, p
i+1
) and (p
i+1
, p
i+2
) intersect at the point p
i+1
. Any two consecutive
segments have different directions. The committee wants Wowo to run from p
1
to p
n
along the line
segments (p
1
, p
2
), . . . , (p
n−1
, p
n
) in order.
However, Wowo has a smart device that can hack the committee’s system for an interval of time. Wowo
is able to choose 2 points a, b on the trial and run directly from a to b along the line segment (a, b).
Each of these a and b can be some p
i
(1 ≤ i ≤ n) and can be some point on some line segment (p
i
, p
i+1
)
(1 ≤ i < n) as well. Before reaching a and after reaching b, Wowo has to run along the original trial.
Wowo does not want to be caught cheating, so he decided that the line segment (a, b) should not intersect
or touch any line segment of the trial at any point other than a and b. Help Wowo to choose a and b
wisely and output the shortest distance Wowo need to run from p
1
to p
n
using his smart cheating device.
Input
The first line includes a single integer n indicating the number of points on the running trial (2 ≤ n ≤ 200).
The i + 1-th line (1 ≤ i ≤ n) contains two integers x and y separated by a single space indicating the
coordinates of p
i
(−1000 ≤ x, y ≤ 1000).
It is guaranteed that the line segments do not intersect with each other except that two
consecutive line segments (p
i
, p
i+1
) and (p
i+1
, p
i+2
) intersect at the point p
i+1
. In other words,
(p
i
, p
i+1
) ∩ (p
j
, p
j+1
) =
∅ i 6= j − 1
{p
j
} i = j − 1
holds for any integers i, j satisfying 1 ≤ i < j < n. Here
(s, t) represents all points on the line segment from s to t including s and t.
It is guaranteed that each line segment has nonzero length. In other words, p
i
6= p
i+1
for any integer
i ∈ [1, n).
It is guaranteed that adjacent line segments are not collinear. In other words, for any integer i ∈ [1, n − 2]
and any real number λ, p
i
− p
i+1
is not equal to λ(p
i+1
− p
i+2
).
Output
Output the shortest distance Wowo needs to run. Your answer will be considered correct if its absolute
or relative error does not exceed 10
−6
.
Example
standard input standard output
5
0 0
1 10
2 0
3 10
4 0
22.099751242242
Page 1 of 18
ICPC 2020, Shanghai Site
China, Shanghai, Dec, 13, 2020
Problem B. Mine Sweeper II
Input file: standard input
Output file: standard output
Time limit: 1 second
Memory limit: 1024 megabytes
A mine-sweeper map X can be expressed as an n × m grid. Each cell of the grid is either a mine cell
or a non-mine cell. A mine cell has no number on it. Each non-mine cell has a number representing the
number of mine cells around it. (A cell is around another cell if they share at least one common point.
Thus, every cell that is not on the boundary has 8 cells around it.) The following is a 16×30 mine-sweeper
map where a flagged cell denotes a mine cell and a blank cell denotes a non-mine cell with number 0.
Given two mine-sweeper maps A, B of size n × m, you should modify at most
nm
2
(i.e. the largest
nonnegative integer that is less than or equal to
nm
2
) cells in B (from a non-mine cell to a mine cell or vice
versa) such that the sum of numbers in the non-mine cells in A and the sum of numbers in the non-mine
cells in B are the same. (If a map has no non-mine cell, the sum is considered as 0.)
If multiple solutions exist, print any of them. If no solution exists, print “-1” in one line.
Input
The first line contains two integers n, m (1 ≤ n, m ≤ 1000), denoting the size of given mine-sweeper maps.
The i-th line of the following n lines contains a length-m string consisting of “.” and “X” denoting the i-th
row of the mine-sweeper map A. A “.” denotes for a non-mine cell and an “X” denotes for a mine cell.
The i-th line of the following n lines contains a length-m string consisting of “.” and “X” denoting the i-th
row of the mine-sweeper map B. A “.” denotes for a non-mine cell and an “X” denotes for a mine cell.
Output
If no solution exists, print “-1” in one line.
Otherwise, print n lines denoting the modified mine-sweeper map B. The i-th line should contain a
length-m string consisting of “.” and “X” denoting the i-th row of the modified map B. A “.” denotes for
a non-mine cell and an “X” denotes for a mine cell.
Please notice that you need not print the numbers on non-mine cells since these numbers can be determined
by the output mine-sweeper map.
Page 2 of 18
剩余19页未读,继续阅读
她与伞皆过客
- 粉丝: 37
- 资源: 2
上传资源 快速赚钱
- 我的内容管理 收起
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
会员权益专享
最新资源
- ExcelVBA中的Range和Cells用法说明.pdf
- 基于单片机的电梯控制模型设计.doc
- 主成分分析和因子分析.pptx
- 共享笔记服务系统论文.doc
- 基于数据治理体系的数据中台实践分享.pptx
- 变压器的铭牌和额定值.pptx
- 计算机网络课程设计报告--用winsock设计Ping应用程序.doc
- 高电压技术课件:第03章 液体和固体介质的电气特性.pdf
- Oracle商务智能精华介绍.pptx
- 基于单片机的输液滴速控制系统设计文档.doc
- dw考试题 5套.pdf
- 学生档案管理系统详细设计说明书.doc
- 操作系统PPT课件.pptx
- 智慧路边停车管理系统方案.pptx
- 【企业内控系列】企业内部控制之人力资源管理控制(17页).doc
- 温度传感器分类与特点.pptx
资源上传下载、课程学习等过程中有任何疑问或建议,欢迎提出宝贵意见哦~我们会及时处理!
点击此处反馈
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功
评论0