2993. 替换

单点时限: 2.0 sec

内存限制: 256 MB

给定一个有限长度的非负整数序列。一次操作是指从第一个元素开始,依次把数列中的每个数替换为它右边比它小的数的个数。对该数列不断进行这个操作。总有一个时刻该数列将不再发生改变(即此时每个数都恰好等于它右边比它小的数的个数)。例如给定数列:

$5, 44, 19, 6, 49, 1, 27, 19, 50, 20$

连续进行五次操作后,依次得到新数列如下:

$1, 6, 2, 1, 4, 0, 2, 0, 1, 0$

$3, 8, 5, 3, 5, 0, 3, 0, 1, 0$

$4, 8, 6, 4, 5, 0, 3, 0, 1, 0$

$5, 8, 7, 5, 5, 0, 3, 0, 1, 0$

$5, 8, 7, 5, 5, 0, 3, 0, 1, 0$

其中,第四次操作后,数列不再发生改变。

对给定数列,循环执行上述操作,直到其不再改变为止,输出最后得到的数列。

输入格式

第 1 行:一个整数 $T$ ($1 \le T \le 10$) 为问题数。

对于每组测试数据:

第 1 行是一个正整数:数列长度 $N$ ( 2 \lt N \leqslant 30 );

第 2 行有 N 个正整数:分别为该数列第 $1$ 至第 $N$ 个元素的值 $a_1,a_2,\cdots , a_n$( $a_1,a_2,\cdots , a_n$均为 $1$ - $1000$ 的数),每两个整数之间用一个空格分开。

输出格式

对于每个问题,输出一行问题的编号($0$ 开始编号,格式:case #0: 等)。

然后在一行中依次输出最后数列的所有元素,每两个元素之间用一个空格分开,最后一个元素后面没有空格。

样例

Input
3
10
5 44 19 6 49 1 27 19 50 20
10
3 2 7 10 9 8 8 5 1 5
10
12 12 19 19 7 10 9 6 18 9
Output
case #0:
5 8 7 5 5 0 3 0 1 0
case #1:
9 2 3 6 5 3 3 2 0 0
case #2:
6 6 6 6 3 4 3 0 1 0

1626 人解决,1702 人已尝试。

2134 份提交通过,共有 3558 份提交。

0.1 EMB 奖励。

创建: 11 年,7 月前.

修改: 6 年,1 月前.

最后提交: 2 月前.

来源: 2013年编程实践课程非师范班第2次上机考试

题目标签