406972: GYM102640 A Points coloring

Memory Limit:256 MB Time Limit:15 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

A. Points coloringtime limit per test15 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard output

You are given $$$n$$$ points on a plane. All points are pairwise distinct. You have to paint each point in one of $$$k$$$ colors so that there are exactly $$$\frac{n}{k}$$$ points of each color. It is guaranteed that $$$k$$$ is a divisor of $$$n$$$.

For each color $$$c$$$ the value $$$s_c$$$ — the square distance between the two closest points of this color — is calculated. The total score is a sum of $$$s_c$$$. You have to maximize your total score.

Input

The first line contains an integer $$$t$$$ — the number of tests.

Each test starts with two integers $$$n$$$ and $$$k$$$ ($$$1 \le n \le 1000$$$, $$$1 \le k \le 25$$$) — the numbers of points and colors. Then $$$n$$$ lines follow, each of them contains two integers $$$x_i$$$ and $$$y_i$$$ ($$$0 \le x_i, y_i \le 1000$$$) — the coordinates of points.

Output

For each test output "Case #j:", where $$$j$$$ is the test number from $$$1$$$ to $$$t$$$, and then a string of $$$n$$$ uppercase Latin letters, whose $$$i$$$-th letter is a color to paint the $$$i$$$-th point. Each letter should be among $$$k$$$ first letters of the alphabet.

ExampleInput
2
4 2
0 0
1 0
1 1
0 1
4 2
0 0
1 0
1 1
0 1
Output
Case #1: AABB
Case #2: ABAB
Note

The sample has two identical test cases but with different answers. The painting "AABB" gives score 2, and the painting "ABAB" gives score 4.

The test file has 60 test cases. Tests 1-10 have some unique feature, tests 11-20 — another feature, tests 21-30 — the third feature, tests 31-40 — the fourth feature, and tests 41-60 are randomly generated.

The total score is the average score for all test cases, rounded down. If the test file contained only two sample test cases, the total score would be 3.

加入题单

上一题 下一题 算法标签: