首页 > ACM题库 > HDU-杭电 > hdu 4399 Colorful Points 待解决[解题报告]C++
2015
05-24

hdu 4399 Colorful Points 待解决[解题报告]C++

Colorful Points

问题描述 :

In this problem, all points are integer points located on the number axis.

There is a set of colorful points P, where point Pk has color k and is located at k,1<=k<=n. Colors of points in set P are pairwise different.

Now, we want to color another set of points Q, where point Qk is located at �Cn+k, 1<=k<=n. Every point in set Q must be colored with one of colors 1, 2, …, n, and all colors must be used at least once. After we finish coloring all points in set Q, we will shift them right by the speed of one unit per second, which means that point Q1 changes its location to �Cn+2, point Q2 changes its location to �Cn+3, …, point Qn changes its location to 1 in the 1st second; and point Q1 changes its location to �Cn+3, point Q2 changes its location to �Cn+4, …, point Qn changes its location to 2 in the 2nd second and so on. We will end the process after 2*n seconds (Q1 -> n+1, Q2 -> n+2, Qn -> 2*n).

We define two parameters here. Let Ak represent the number of different pairs of points coincide in the k-th second. A pair of points coincides in the k-th second means that a point from set Q has the same location with that of a point from set P in the k-th second, such as point Qn changes its location to 1 which is the same as that of point P1 in the 1st second, so the pair (Qn, P1) is a pair of points coincides in the 1st second, and pairs (Qn-1, P1) and (Qn, P2) are two different pairs of points coincide in the 2nd second and so on. Let Bk represent the number of pairs of points which have the same color among all the pairs of points coincide in the k-th second. To help you understand Ak and Bk better, we give an example below:

e.g. Let n = 3, and we color point Q3 with color 2, pointQ2 with color 3, point Q1 with color 1. In the 1st second, (Q3, P1) is the only pair of points coincide, but the color of point Q3 is different from that of point P1, so A1 = 1 and B1 = 0; In the 2nd second, (Q3, P2) and (Q2, P1) are the only two pairs of points coincide, and point Q3 and point P2 have a same color while point Q2 and point P1 have a different color, so A2 = 2 and B2 = 1; In the 3rd second, there are three pairs of points coincide, which are (Q1, P1) with a same color and (Q2, P2), (Q3, P3) with a different color, so A3 = 3 and B3 = 1; In the 4th second, A4 = 2 and B4 = 1; In the 5th second, A5 = 1 and B5 = 0; In the 6th second, A6 = 0 and B6 = 0.

We define another parameter C, where C=max{Ak – Bk}, 1<=k<=2*n. If you have finished coloring all the points in set Q, parameter C is easy to be calculated, and different ways of coloring may lead to different Cs. Among all the Cs, there is a minimum one. In this problem, your job is to calculate the minimum C and give a way of coloring which leads to the minimum C.

输入:

At the beginning, there is an integer T indicating the total number of test cases.
Every test case occupies a single line with only one integer n.
  T <= 100;
  1 <= n <= 100000;
Most ns are less than 1000.

输出:

At the beginning, there is an integer T indicating the total number of test cases.
Every test case occupies a single line with only one integer n.
  T <= 100;
  1 <= n <= 100000;
Most ns are less than 1000.

样例输入:

4
1
2
3
4

样例输出:

Case #1: 0
1
Case #2: 1
1 2
Case #3: 2
1 2 3
Case #4: 2
1 2 4 3