单点时限: 1.0 sec
内存限制: 256 MB
有 $n$ 个小朋友,标号为 $1$ 到 $n$,每个小朋友有一些糖果,第 $i$ 个小朋友拥有糖果数量为 $a_i$。
为了使得每个小朋友拥有相同的糖果,现提供如下操作:选择两个小朋友组成一个有序对 $(u,v)$ $(1 \le u,v \le n, u \ne v)$,然后记两个小朋友拥有的糖果总和为 $S$,然后令 $a_u=\lfloor \frac{S}{2} \rfloor$, $a_v=\lceil \frac{S}{2} \rceil$。
即:
function do_something(u, v):
S := (a[u] + a[v])
a[u] := floor(S / 2)
a[v] := ceil(S / 2)
请构造一系列操作,使得所有小朋友最终拥有相同的糖果。或者判断出这是不可能的。
第一行一个整数 $n$。
第二行 $n$ 个整数用空格隔开:$a_1,a_2,\ldots,a_n$。
部分分约定:
如果不可能,输出一行 Impossible
。
否则:
所以你的程序应该在 $10~000$ 步以内完成任务。给定数据保证存在一种方案能够完成目标,除非不可能完成。
4 1 3 1 3
2 1 2 3 4