26425번 - Students and Mentors 서브태스크다국어
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 서브태스크 참고 (추가 시간 없음) | 1024 MB | 20 | 19 | 17 | 94.444% |
문제
A group of $\mathbf{N}$ 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 $i$ we know their rating $\mathbf{R_i}$ 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 $j$ can be a mentor of student $i$ only if $\mathbf{R_j} \le 2 \times \mathbf{R_i}$. 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?
입력
The first line of the input gives the number of test cases, $\mathbf{T}$. $\mathbf{T}$ test cases follow. Each test case consists of two lines.
The first line of each test case contains an integer $\mathbf{N}$, representing the number of students in a group.
The second line of each test case contains $\mathbf{N}$ integers $\mathbf{R_1} \ \mathbf{R_2} \ \mathbf{R_3} \ \dots \ \mathbf{R_N}$ where $\mathbf{R_i}$ is a rating of the $i$-th student.
출력
For each test case, output one line containing Case #x: M1 M2 M3 ... MN$ where $x$ is the test case number (starting from 1), and $M_i$ is the maximum possible rating of the $i$-th student's mentor or $-1$ if there are no suitable mentors for that student.
제한
- $1 \le \mathbf{T} \le 100$.
- $1 \le \mathbf{R_i} \le 10^6$, for all $i$.
Test Set 1 (6점)
시간 제한: 20 초
- $2 \le \mathbf{N} \le 1000$.
Test Set 2 (12점)
시간 제한: 40 초
- $2 \le \mathbf{N} \le 10^5$.
예제 입력 1
3 3 2000 1500 1900 5 1000 600 1000 2300 1800 2 2500 1200
예제 출력 1
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 $2000$, $1500$, and $1900$. 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 $1900$, $2000$, and $2000$, respectively. Note that in this case a student with the rating $2000$ will be a mentor of two other students.
In the Sample Case #2, there are five students with ratings $1000$, $600$, $1000$, $2300$, and $1800$ (note that some students may have equal ratings). For both students with ratings $1000$, the highest rated possible mentor for them has rating $1800$. They cannot pick a mentor with rating $2300$ as $2300 > 2 \times 1000$. Student with rating $600$ cannot pick mentors with ratings $1800$ or $2300$, so they pick a mentor with rating $1000$ (either of two students with rating $1000$ works). Student with rating $2300$ can pick any other student as their mentor, so they pick a mentor with rating $1800$ — the highest possible. Finally, student with rating $1800$ can pick any other student as their mentor too, so they pick a mentor with the highest possible rating of $2300$. So in the end, the students pick the mentors with the ratings $1800$, $1000$, $1800$, $1800$, and $2300$, respectively.
In the Sample Case #3, there are two students with ratings $2500$ and $1200$. For a student with rating $2500$, another student with rating $1200$ can be a mentor, and there are no other options. For a student with rating $1200$, we cannot assign a mentor with rating $2500$, as $2500 > 2 \times 1200$, and therefore this student has no suitable mentor. In the end, we output $1200$ and $-1$ as a result for this test case.
출처
Contest > Google > Kick Start > Google Kick Start 2022 > Round E B번
채점 및 기타 정보
- 예제는 채점하지 않는다.
© 2026 All Rights Reserved. 주식회사 스타트링크 | 서비스 약관 | 개인정보 보호 | 결제 이용 약관 | 도움말 | 광고 문의 | 업데이트 노트 | 이슈 | TODO
- 사업자 등록 번호: 541-88-00682
- 대표자명: 최백준
- 주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
- 전화번호: 02-521-0487 (이메일로 연락 주세요)
- 이메일: contacts@startlink.io
- 통신판매신고번호: 제 2017-서울서초-2193 호