A Colorful Problem

Interview

Time limit1sMemory limit512 MB

Summary

For each RGB color after the first 16, print it, the words "maps to", and the target color with the smallest Euclidean distance.

Level: Easy2 of 10
Topics: Implementation, Brute force, Geometry, Array
Solved: No attempts yet

Problem

In computer graphics it is often necessary to map one discrete set of colors to a second, smaller discrete set of colors. The goal of this program is to perform just such a mapping in RGB color space. The input to the program consists of a target set of 16 RGB color values, and a collection of RGB color values to be mapped to the "closest" color in the target set.

The input is a list of RGB color values, one color per line, with each color having a red, green, and blue component, in that order, specified as integers from 0 to 255 (0 indicates complete absence of that component, 255 indicates full intensity of that component). The first 16 colors form the target set of colors to which all the rest of the colors in the input should be mapped.

For a given color, the "closest" color in the target set is the color with the smallest euclidean distance from the original color. That is if $rgb$ is the color to be mapped, and $\{R_1G_1B_1, \dots, R_{16}G_{16}B_{16}\}$ is the set of target colors, the closest color is the one which minimizes the distance equation $d = \sqrt{(R_i - r)^2 + (G_i - g)^2 + (B_i - b)^2}$ , where $i$ is an integer from 1 to 16.

The program should output one line for each color to be mapped to the target set. As illustrated in the sample out below, that line should contain the color to be mapped followed by the words "maps to", and then the color from the target set which the original color was mapped to. All colors should be specified as described above, in the order red, green, blue.

Examples1

Example 1

Input

0 0 0
255 255 255
0 0 1
1 1 1
128 0 0
0 128 0
128 128 0
0 0 128
126 168 9
35 86 34
133 41 193
128 0 128
0 128 128
128 128 128
255 0 0
0 1 0
0 0 0
255 255 255
253 254 255
77 79 134
81 218 0

Expected output

  0   0   0 maps to   0   0   0
255 255 255 maps to 255 255 255
253 254 255 maps to 255 255 255
 77  79 134 maps to 128 128 128
 81 218   0 maps to 126 168   9