COCI '21 Contest 3 #1 Lampice

View as PDF

Submit solution

Points: 5 (partial)
Time limit: 1.0s
Memory limit: 512M

Problem types

Little Vera really likes Advent and Christmas time. Most of all, she likes colorful Christmas lights and enjoys decorating her balcony with shining colors. To decorate her balcony, she bought a sequence of n lights connected in a row, each shining in one of a thousand different colors.

Apart from lights, Vera also really likes repeating patterns, so she would like to have her balcony decorated so that a certain pattern of colors repeats k times in a row. However, the lamps she bought might not satisfy her obsession of repetition and patterns, so she decided to cut off zero or more lamps from the beginning and from the end of the sequence to obtain a sequence in which a pattern of colors repeats k times in a row.

Help her determine whether she can obtain such a sequence of lights by making the mentioned cuts, and if so, print the pattern that will be repeated.

Input Specification

The first line contains positive integers n and k (1 \le k \le n \le 50) described above.

The second line contains a sequence of positive integers a_1, a_2, \dots, a_n (1 \le a_i \le 1\,000), which denotes the colors of the lamps that Vera bought in the order they appear in her sequence.

Output Specification

If Vera can't cut out a sequence of lights that she wants, print -1.

If Vera can cut out a sequence of lights that she wants, in the first line, print the length of the repeating pattern, and in the second line, print the sequence of colors that makes up the pattern. If there is more than one solution, you can output any one of them.


110The sequence contains a pattern of a single light repeated k times in a row.
215k = 2
325No additional constraints.

Sample Input 1

8 6
10 1 1 1 1 1 1 5

Sample Output 1


Sample Input 2

3 2
1 2 1

Sample Output 2


Sample Input 3

10 2
1 5 1 5 2 5 6 2 5 6

Sample Output 3

1 5

Explanation for Sample Output 3

If Vera cuts off six lights from the end and zero from the beginning, she obtains the sequence of lights 1, 5, 1, 5, in which the pattern 1, 5 repeats twice in a row. If, on the other hand, she cuts off four lights from the beginning and zero from the end, she obtains the sequence of lights 2, 5, 6, 2, 5, 6, in which the pattern 2, 5, 6 repeats twice, so this is also a valid solution.


There are no comments at the moment.