#2206. Constructing a circuit
Constructing a circuit
Constructing a circuit
题目描述
标题: Constructing a circuit - Problem - QOJ.ac
#16217. Constructing a circuit
The problem was used in the following contests:
在对高中物理学进行了整个学习之后,辛迪打算运用他的知识。他挖出了一块印制电路板,上面有2排触点,每排有n+1个。他计划用细铜线连接这些触点,如下图所示(蓝色是触点,红色是电线,电源没有连接),然后计算电阻和电流。连接下图中的两个相邻节点需要1单位长度的铜线。为了实现这一目标,辛迪从鲍勃借用了一些总长度为3n的铜线。辛迪可以将每根铜线弯曲数次,但不能将任何铜线掰开。请为辛迪找到任何有效的解决方案,或者报告不可能!
Implementation Details
你应该包含 circuit.h,并实现如下过程:
int[][] wiring(int n, int[] w)
- n: 每行的长度,见题面。
- w: 第 i 个(0≤i≤n−1)表示一条长度为 w[i]>0 的铜线。保证 w 内元素之和为 3n。
- 你实现的过程会被调用恰好一次。
- 如果无解,你应该返回一个空数组。
- 否则,你应该返回一个由三个 n 长度的数组组成的数组,依次表示第一排横着的、竖着的、第二排横着的每个单位线段从左到右由哪条铜线组成(0 到 n−1 的编号)。
Example
考虑如下调用:wiring(3, [3, 2, 2, 2])
一种合法的输出为 [[0, 0, 2], [0, 1, 2], [1, 3, 3]],对应下图。
Constraints
1≤n,|w|≤105
∑t∈wt=3n
Subtasks
- (10分)n≤3,m≤9
- (20分)所有铜线长度至多为2
- (30分)所有铜线长度至少为2
- (20分)n,m≤5000
- (20分)无特殊限制。
Sample Grader
样例交互器以下列格式读取输入。
- 第一行:n |w|
- 第二行:依次给出 w 的各个元素
样例交互器以下列格式打印你的输出。
- 第一行:如果有解输出
Yes,否则输出No - 如果有解,接下来三行依次输出返回的方案
输入格式
(见题面原文)
输出格式
(见题面原文)
数据范围
(见题面原文)
样例
样例 1
3 4
3 2 2 2
Yes
0 0 2
0 1 2
1 3 3
样例 2
4 5
3 3 2 2 2
Yes
0 0 0 1
2 3 4 1
2 3 4 1