#P15796. [2026作业]排列赌场的期望下注

[2026作业]排列赌场的期望下注

题目描述

特工 James Bond 终于在名为 Permutasino 的赌场里找到了宿敌 Dr. Zlo。两人坐到了一张奇怪的轮盘赌桌前。

这张轮盘上共有 n!n! 个格子,每个格子对应一个 11 到 nn 的排列。

玩家最多可以在 nn 个格子上下注。若在排列 π\pi 上下注,其赌注为一个非负实数 bπb_\pi。所有下注金额之和必须为 11。

下注结束后,轮盘会按照这些下注金额给出的分布随机选择一个排列:如果排列 π\pi 上的下注为 bπb_\pi,则它被选中的概率为 bπb_\pi;没有下注的排列被选中的概率为 00。

Bond 想让最终随机排列的期望值等于给定向量

(x1,x2,…,xn).(x_1,x_2,\ldots,x_n).

这里,一个长度为 nn 的随机排列的期望值也是一个长度为 nn 的向量;其第 ii 个分量等于随机排列第 ii 个位置上的数的期望。

请你帮助 Bond 给出一种下注方案,或者判断不存在这样的方案。

输入格式

第一行包含一个整数 nn,表示轮盘上排列的长度。

第二行包含 nn 个整数

x1,x2,…,xn,x_1,x_2,\ldots,x_n,

表示目标期望向量。

输出格式

如果无法构造,输出一行:

-1

否则,第一行输出一个整数 kk,表示下注的格子数,需满足

1≤k≤n.1\le k\le n.

接下来 kk 行,每行先输出一个实数 bib_i,表示第 ii 个下注金额;随后输出 nn 个整数

πi,1,πi,2,…,πi,n,\pi_{i,1},\pi_{i,2},\ldots,\pi_{i,n},

表示下注对应的排列。

需要满足:

  • 每个 bi≥0b_i\ge 0;
  • 每行给出的 πi\pi_i 是 11 到 nn 的排列;
  • ∑ibi=1\sum_i b_i=1,允许绝对误差不超过 10−610^{-6};
  • 对所有 1≤j≤n1\le j\le n,
∣∑ibiπi,j−xj∣≤10−6.\left|\sum_i b_i\pi_{i,j}-x_j\right|\le 10^{-6}.

验证时使用双精度浮点数。若有多种方案,输出任意一种即可。

数据范围

  • 1≤n≤1001\le n\le 100;
  • 1≤xi≤n1\le x_i\le n。

样例 1

输入

4
2 2 3 3

输出

3
0.5000000000 1 2 3 4
0.1666666667 1 4 3 2
0.3333333333 4 1 3 2

样例 2

输入

2
1 1

输出

-1

样例 1 解释

样例 1 中,输出方案的期望为

$$\frac12(1,2,3,4)+\frac16(1,4,3,2)+\frac13(4,1,3,2)=(2,2,3,3).$$