首页 > 试题广场 >

Kolakoski 序列

[编程题]Kolakoski 序列
  • 热度指数:1259 时间限制:C/C++ 1秒,其他语言2秒 空间限制:C/C++ 64M,其他语言128M
  • 算法知识视频讲解
Kolakoski 序列是个自生成的无限序列。
例如,当给定的整数组为 [1, 2] 时,Kolakoski 序列是这样的:
    [1,2,2,1,1,2,1,2,2,1,2,2,1,1,2,1,1,2,2,1,2,1,1,2,1,2,2,1,1,…]
如果我们将相邻的相同的数字分成一组,那么将会得到:
    [[1],[2,2],[1,1],[2],[1],[2,2],[1],[2,2],[1,1],[2],[1,1],[2,2],[1],[2],[1,1],[2],[1],[2,2],[1,1],…]
可以看出,每组数字交替由 1, 2 组成。
接下来对每个分组求他的长度,得到:
    [1,2,2,1,1,2,1,2,2,1,2,2,1,1,2,1,1,2,2,1,2,1,1,2,1,2,2,1,1,…]
可以看出,经过如上的变换后,数列保持不变。
对于其他给定的整数组,同样可以用类似的方法构造 Kolakoski 序列,例如给定整数组 [2, 3] 时:
    [2,2,3,3,2,2,2,3,3,3,2,2,3,3,2,2,3,3,3,2,2,2,3,3,3,2,2,3,3,…]
给定整数组 [2, 1, 3, 1] 时,构造得到如下:
    [2,2,1,1,3,1,2,2,2,1,3,3,1,1,2,2,1,3,3,3,1,1,1,2,1,3,3,1,1,…]

输入描述:
输入由两行组成:
第一行包括两个正整数 n, m
第二行包括 m 个正整数 a[]
数据规模与限制:
0 < n < 10000
1 < m < 1000
0 < a[i] < 1000
a[i] 不等于 a[i + 1]
a[0] 不等于 a[m-1]


输出描述:
每行一个数字,共 n 行
整数组 a 生成的 Kolakoski 序列的前 n 项
示例1

输入

30 4
2 1 3 1

输出

2
2
1
1
3
1
2
2
2
1
3
3
1
1
2
2
1
3
3
3
1
1
1
2
1
3
3
1
1
2

这道题你会答吗?花几分钟告诉大家答案吧!