COCI '11 Contest 6 #5 Pastele

View as PDF

Submit solution


Points: 12 (partial)
Time limit: 5.0s
Memory limit: 256M

Problem types

Mirko recently got N crayons as a gift. The color of each crayon is a combination of three primary colors: red, green and blue. The color of the ith crayon is represented with three integers: Ri for the red, Gi for the green and Bi for the blue component.

The difference between the ith and the jth crayon is max(|RiRj|,|GiGj|,|BiBj|). The colorfulness of a subsequence of crayons is equal to the largest difference between any two crayons in the subsequence.

Mirko needs a subsequence with K crayons with the smallest colorfulness for his drawing. The subsequence does not have to be consecutive. Find it!

Input Specification

The first line of input contains integers N and K (2KN100000).

The ith of the following N lines contains three integers Ri, Gi and Bi (0Ri,Gi,Bi255).

Output Specification

The first line of output should contain the smallest colorfulness of a subsequence with K crayons.

The following K lines should contain the R, G and B values of the colors of the crayons in the subsequence, in any order. Any subsequence that yields the smallest colorfulness will be accepted.

Scoring

In test cases worth 50% of total points, 0Ri,Gi,Bi20 will hold.

In test cases worth additional 30% of total points, 0Ri,Gi,Bi50 will hold.

Sample Input 1

Copy
2 2
1 3 2
2 6 4

Sample Output 1

Copy
3
1 3 2
2 6 4

Sample Input 2

Copy
3 2
3 3 4
1 6 4
1 1 2

Sample Output 2

Copy
2
3 3 4
1 1 2

Sample Input 3

Copy
5 3
6 6 4
6 2 7
3 1 3
4 1 5
6 2 6

Sample Output 3

Copy
2
6 2 7
4 1 5
6 2 6

Comments

There are no comments at the moment.