ACM 2007 - Distinct colors

Problem D. Distinct colors ≡

problems
details
visible spaces
basic formulae
wide text
editor

Author:	A. Klenin	Time limit:	2 sec
Input file:	input.txt	Memory limit:	64 Mb
Output file:	output.txt

Statement

Colors on computer screen are represented by (r, g, b) triplets, where r, g, b are integer intensities of red, green and blue components.

Two colors (r₁, g₁, b₁) and (r₂, g₂, b₂) are distinct if min(|r₁ − r₂|, |g₁ − g₂|, |b₁ − b₂|) ≥ D.

Your program will be given N (not necessarily distinct) colors. It must either calculate K new colors that are distinct from each other and from all initial colors, or determine that it is impossible.

Input file format

Input file contains numbers N K D followed by N triplets r_i g_i b_i, representing initial colors.

Output file format

Output file must contain K triplets r_j g_j b_j, representing resulting distinct colors. If there is no solution, output must contain a single number −1. If there is more than one solution, output any of them.

Constraints

0 ≤ r_i, g_i, b_i ≤ 255 for both input and output colors,

0 ≤ N ≤ 256, 1 ≤ D, K ≤ 256

Sample tests

No.	Input file (`input.txt`)	Output file (`output.txt`)
1	`2 1 10 255 100 100 100 100 255`	`110 110 110`
2	`2 1 200 255 100 100 100 100 255`	`-1`