#2206. Constructing a circuit

    ID: 2206 传统题 1000ms 256MiB 尝试: 0 已通过: 0 难度: 省选/NOI- 上传者: 标签>TEAM赛事:contest1655来源:qoj.ac数据:公开样例贪心枚举

Constructing a circuit

Constructing a circuit

题目描述

标题: Constructing a circuit - Problem - QOJ.ac

#16217. Constructing a circuit

Statistics

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

  1. (10分)n≤3,m≤9
  2. (20分)所有铜线长度至多为2
  3. (30分)所有铜线长度至少为2
  4. (20分)n,m≤5000
  5. (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