07/04/2025 07:22:52

Рабочее место участника

Выбрать соревнование

Задачи

Послать решение

Результаты проверки

Статистика по задачам

Вопросы и ответы

Результаты соревнования

Задачи

1804. Crayons

Ограничения: время – 8s/16s, память – 256MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод copy
Послать решение Blockly Посылки Темы Где Обсудить (0)

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

$i$ th crayon is represented with three integers:

$R_i$ for the red,

$G_i$ for the green and

$B_i$ for the blue component.

The difference between the

$i$ th and the

$j$ th crayon is

$max(|R_i\ -\ R_j|,\ |G_i\ -\ "Gj"|,\ |"Bi"\ -\ "Bj"|)$ . 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!

The first line of input contains integers

$N$ and

$K$ (

$2\ ≤\ K\ ≤\ N\ ≤\ 100\ 000$ ). The

$i$ th of the folowing

$N$ lines contains three integers

$R_i$ ,

$G_i$ , and

$B_i$ (

$0\ ≤\ R_i,\ G_i,\ B_i\ ≤\ 255$ ).

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.

Sample Input #1

2 2
1 3 2 
2 6 4

Sample Output #1

3 
1 3 2 
2 6 4

Sample Input #2

Sample Output #2

2 
3 3 4 
1 1 2

Sample Input #3

Sample Output #3

Source: COCI 2011/2012

25/06/2012	Лето 2012 - дорешивание (10C)
10/07/2012	Лето 2012 - 10 (командный) (C)