搜狐集团2018秋季校招笔试题（技术类）-编程题一

发表于 | 分类于 ，

题目

描述

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 项

Example

Input

30 4
2 1 3 1

Output

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

题解

思路

  • i 表示当前正在生成的分组
  • j 表示已生成的 Kolakoski 序列的个数
  • k 表示生成当前分组所用的整数在 a[] 中的位置
  • 若 i=j,说明没有生成第 i 组的长度,则需要生成的 i 组的长度为 a[k]
  • 若 i<j,说明已经生成第 i 组长度,则需要生成的 i 组的长度 b[j]
  • 循环生成第 i 组
  • 若 j>=n 说明已生成完毕
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
#include <bits/stdc++.h>

#define ll long long
#define ull unsigned long long

using namespace std;

int a[1000],n,m,Kolakoski[10000];

int main()
{
    int i,j,k,t;
    cin>>n>>m;
    for(i=0;i<m;++i)
    {
        scanf("%d",&a[i]);
    }
    if(n)
    {
        for(i=j=k=0;j<n;++i)
        {
            if(i<j)
                t=Kolakoski[i];
            else
                t=a[k];
            while(t>0&&j<n)
            {
                Kolakoski[j]=a[k];
                cout<<Kolakoski[j]<<endl;
                --t,++j;
            }
            k=(k+1)%m;
        }
    }
}