QOJ.ac

QOJ

Time Limit: 3 s Memory Limit: 1024 MB Total points: 100

#16217. Constructing a circuit

Statistics

在对高中物理学进行了整个学习之后,辛迪打算运用他的知识。他挖出了一块印制电路板,上面有2排触点,每排有n+1个。他计划用细铜线连接这些触点,如下图所示(蓝色是触点,红色是电线,电源没有连接),然后计算电阻和电流。连接下图中的两个相邻节点需要1单位长度的铜线。为了实现这一目标,辛迪从鲍勃借用了一些总长度为3n的铜线。辛迪可以将每根铜线弯曲数次,但不能将任何铜线掰开。请为辛迪找到任何有效的解决方案,或者报告不可能!

problem_16217_1.png

Implementation Details

你应该包含 circuit.h,并实现如下过程:

int[][] wiring(int n, int[] w)

  • $n$: 每行的长度,见题面。
  • $w$: 第 $i$ 个($0\le i\le 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]],对应下图。

problem_16217_2.png

Constraints

$1\le n,|w|\le 10^5$

$\sum_{t\in w} t=3n$

Subtasks

  1. (10分)$n\le 3$,$m\le 9$
  2. (20分)所有铜线长度至多为2
  3. (30分)所有铜线长度至少为2
  4. (20分)$n,m\le 5000$
  5. (20分)无特殊限制。

Sample Grader

样例交互器以下列格式读取输入。

  • 第一行:$n~|w|$
  • 第二行:依次给出 $w$ 的各个元素

样例交互器以下列格式打印你的输出。

  • 第一行:如果有解输出 Yes,否则输出 No
  • 如果有解,接下来三行依次输出返回的方案

Discussions

About Discussions

The discussion section is only for posting: General Discussions (problem-solving strategies, alternative approaches), and Off-topic conversations.

This is NOT for reporting issues! If you want to report bugs or errors, please use the Issues section below.

Open Discussions 0
No discussions in this category.

Issues

About Issues

If you find any issues with the problem (statement, scoring, time/memory limits, test cases, etc.), you may submit an issue here. A problem moderator will review your issue.

Guidelines:

  1. This is not a place to publish discussions, editorials, or requests to debug your code. Issues are only visible to you and problem moderators.
  2. Do not submit duplicated issues.
  3. Issues must be filed in English or Chinese only.
Active Issues 0
No issues in this category.
Closed/Resolved Issues 0
No issues in this category.