Students and Mentors solution kickstart

Students and Mentors solution kickstart

A group of NN students prepares together for upcoming programming competitions such as Kick Start and Code Jam by Google. To help each other prepare, it was decided that each student will pick a mentor among other students. A mentor will help their mentee to solve problems, learn algorithms, track their progress, and will generally support them throughout preparation.

Each student will have exactly one mentor among all other students, and a person can be a mentor to multiple people. For every student ii we know their rating RiRi which approximates how good that student is at programming competitions. Because it is believed that a mentor should not be much stronger than their mentee, a student jj can be a mentor of student ii only if Rj2×RiRj≤2×Ri. Note that a mentor can even have a rating that is lower or equal to their mentee’s rating.

Unsurprisingly, each student wants to have the strongest possible mentor. For each student, can you help to figure out what is the highest possible rating of a mentor they can pick?

Input

The first line of the input gives the number of test cases, TTTT test cases follow. Each test case consists of two lines.

The first line of each test case contains an integer NN, representing the number of students in a group.

The second line of each test case contains NN integers R1 R2 R3  RNR1 R2 R3 … RN where RiRi is a rating of the ii-th student.

Students and Mentors solution kickstart

Output

For each test case, output one line containing Case #xxM1 M2 M3  MNM1 M2 M3 … MN where xx is the test case number (starting from 1), and MiMi is the maximum possible rating of the ii-th student’s mentor or 1−1 if there are no suitable mentors for that student.

Limits

Memory limit: 1 GB.
1T1001≤T≤100.
1Ri1061≤Ri≤106, for all ii.

Test Set 1

Time limit: 20 seconds.
2N10002≤N≤1000.

Test Set 2

Students and Mentors solution kickstart

Time limit: 40 seconds.
2N1052≤N≤105.

Sample

Sample Input
content_copy
3
3
2000 1500 1900
5
1000 600 1000 2300 1800
2
2500 1200
Sample Output
content_copy
Case #1: 1900 2000 2000
Case #2: 1800 1000 1800 1800 2300
Case #3: 1200 -1

In the Sample Case #1, there are three students with ratings 2000200015001500, and 19001900. All students can pick any other student as their mentor, so they all pick a mentor with the highest possible rating. As a result, they pick mentors with ratings 1900190020002000, and 20002000, respectively. Note that in this case a student with the rating 20002000 will be a mentor of two other students.

Students and Mentors solution kickstart

In the Sample Case #2, there are five students with ratings 100010006006001000100023002300, and 18001800 (note that some students may have equal ratings). For both students with ratings 10001000, the highest rated possible mentor for them has rating 18001800. They cannot pick a mentor with rating 23002300 as 2300>2×10002300>2×1000. Student with rating 600600 cannot pick mentors with ratings 18001800 or 23002300, so they pick a mentor with rating 10001000 (either of two students with rating 10001000 works). Student with rating 23002300 can pick any other student as their mentor, so they pick a mentor with rating 18001800 — the highest possible. Finally, student with rating 18001800 can pick any other student as their mentor too, so they pick a mentor with the highest possible rating of 23002300. So in the end, the students pick the mentors with the ratings 18001800100010001800180018001800, and 23002300, respectively.

In the Sample Case #3, there are two students with ratings 25002500 and 12001200. For a student with rating 25002500, another student with rating 12001200 can be a mentor, and there are no other options. For a student with rating 12001200, we cannot assign a mentor with rating 25002500, as 2500>2×12002500>2×1200, and therefore this student has no suitable mentor. In the end, we output 12001200 and 1−1 as a result for this test case.

Leave a Comment