← 返回题目列表

Codeforces · 1267/C

C. 仙人掌复仇

中文机器翻译题面 查看原题

以下页面来自赛事官方发布的原题PDF,已完整保存并渲染到本地。

Cactus Revenge - 原题 PDF 第 1 页
原题PDF第3页
可复制的 PDF 提取文本
ICPC 2019–2020, NERC – Northern Eurasia Finals
                         St. Petersburg, Barnaul, Tbilisi, and Almaty, December 1, 2019
Problem C. Cactus Revenge

    Time limit:     3 seconds

NE(E)RC featured a number of problems in previous years about cactuses — connected undirected graphs
in which every edge belongs to at most one simple cycle. Intuitively, a cactus is a generalization of a tree
where some cycles are allowed. The traditional cactus that was initially used in NEERC 2005 problem is
given on the second picture in the Examples section.

You are given n integers d1, d2, . . . , dn. Construct any cactus with n vertices such that vertex i has degree di
(i. e. exactly di incident edges), or determine that no such cactus exists. Parallel edges and loops are not
allowed.

Input

The first line contains a single integer n (2 ≤n ≤2 000) — the number of vertices in the cactus.

The second line contains n integers d1, d2, . . . , dn (1 ≤di ≤n −1) — the desired vertex degrees.

Output

If it’s impossible to construct a cactus satisfying the conditions, output a single integer −1.

Otherwise, by tradition, output the constructed cactus as a set of edge-distinct paths.

In the first line output an integer m — the number of such paths. Each of the following m lines should
contain a path in the graph. A path should start with an integer ki (ki ≥2) followed by ki integers from
1 to n. These ki integers should represent consecutive vertices of this path. Adjacent vertices in the path
should be distinct. The path can visit the same vertex multiple times, but every edge of the cactus should
be traversed exactly once in the whole output.

Examples

         standard input              standard output               Illustration
 5                                4                                        2
 2 2 3 2 1                        2 1 2
                                  2 2 3
                                                                                                   3        4        5
                                  2 3 1
                                  3 3 4 5                               1

 4                                -1
 3 3 2 2

 6                                -1
 1 2 1 1 2 1

 15                               3                                        6
 1 4 3 2 2 2 2 2 4 4 2 2 2 2 2    9 1 2 3 4 5 6 7 8 3
                                  7 2 9 10 11 12 13 10                         13     12                                                                            7          5
                                  5 2 14 9 15 10
                                                                            8          4
                                                                                            10   11

                                                                                 3     9    15

                                                                                  2   14

                                                                              1

Note

Both in the second and the third example, there exist graphs that satisfy the given conditions but none
of them are cactuses.


                                         Page 3 of 15