#2051. 小 C 的比赛

    ID: 2051 传统题 1000ms 256MiB 尝试: 0 已通过: 0 难度: NOI/NOI+/CTS 上传者: 标签>CTT赛事:contest768来源:qoj.ac数据:公开样例贪心枚举

小 C 的比赛

小 C 的比赛

题目描述

标题: 小 C 的比赛 - Problem - QOJ.ac

#6202. 小 C 的比赛

Statistics

The problem was used in the following contests:

在一个神秘的 OJ 上,小 C 曾经参加过 n 场比赛,其中第 i(i=1,2,…,n) 场比赛获得了 ai 积分;积分可能是正的,可能是负的,但它一定是一个 [−2,2] 中的整数。

由于一些原因,小 C 会挑出一个区间的比赛 [l,r],并和大家说:“要是我只打这个区间的比赛,那么我就有 ∑i=lrai 分了!”当然,小 C 会挑选出至少一场比赛,而且选出区间的比赛积分总和是所有区间里最大的,而这个积分总和则是他对自己发挥的满意程度。

随着时间的流逝,小 C 逐渐忘记了自己每场比赛的分数,也忘了他对这些比赛的满意程度,他只记得每种分数的比赛打了多少场,而小 C 想知道,他满意程度最小可能是多少。于是他来请求于你。

输入格式

本题有多组测试数据。

第一行一个正整数 T,表示数据组数。

下面 T 行,每行 c−2,c−1,c0,c1,c2 五个非负整数,分别表示每种分数的比赛场数。你可以自行算出 n=c−2+c−1+c0+c1+c2。

输出格式

每组测试数据输出两行。第一行一个整数,表示小 C 满意程度的可能最小值。

第二行 n 个整数 a1,a2,…,an,表示达到此最小值的任意一种可能的比赛得分情况。

样例

input

1
1 1 0 2 2

output

3
1 -1 2 -2 1 2

限制与约定

令 ∑n 表示一组数据中 n 的总和。对所有数据,保证 1≤T≤10000,1≤n,∑n≤5×105。

子任务编号n≤特殊性质分值 120T≤518 240T≤518 35×105c−2=018 45×105c2=018 55×105无28

输入格式

(见题面原文)

输出格式

(见题面原文)

数据范围

(见题面原文)

样例

样例 1

1
1 1 0 2 2
3
1 -1 2 -2 1 2