19592번 - 장난감 경주 다국어
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 (추가 시간 없음) | 256 MB | 570 | 271 | 208 | 51.106% |
문제
당신을 포함한 N명의 참가자가 각자 자신의 장난감 자동차를 이용해 경주를 하는데, 트랙의 길이는 X 미터이다.
참가자는 1번부터 N번까지 번호가 매겨져 있고, 당신의 참가 번호는 N번이다.
i번 참가자의 자동차의 일반적인 속도는 V[i] meters per sec (m/s) 이며, 당신을 제외한 모든 참가자의 자동차는 출발점 부터 도착점까지 항상 일정한 속도로 움직인다.
단, 당신의 장난감 자동차는 특수 부스터가 있기 때문에, 처음 1초간 Z m/s 로 움직이도록 설정할 수 있다 (이 때 트랙의 나머지 거리는 V[N] m/s 로 일정한 속도로 움직인다).
경주 시작 전 정수 Z값을 고를 수 있으며, 이 값은 반드시 부스터 속도 한계치인 Y m/s 이하이어야 한다 (Z ≤ Y).
당신은 꼭 이 경주에서 단독 1등을 하고 싶은데, 부스터를 지나치게 사용하면 의심 받을 수 있으니 단독 우승이 가능토록 하는 최소의 Z값을 구하고 싶다.
예를 들어 N = 3, X = 12, Y = 11 이라하고, V = [3, 2, 1] 이라 하자.
- 1번 참가자의 자동차는 3 m/s의 일정한 속도로 움직여서 4초만에 경주를 마친다.
- 2번 참가자의 자동차는 2 m/s의 일정한 속도로 움직여서 6초만에 경주를 마친다.
- 3번 참가자인 당신의 경우 여러 가지 가능성이 있다.
- 부스터를 사용하지 않으면 1 m/s의 일정한 속도로 움직여서 12초만에 경주를 마친다.
- 부스터를 최대치로 사용하면 (Z = Y) 첫 1초간 11m를 이동하고, 나머지 1m를 1초간 주행해서 2초만에 경주를 마치며 단독 우승 할 수 있다.
- 부스터를 조금 덜 사용하여 Z = 10미터를 1초만에 이동하면, 나머지 2m는 원래 속도로 이동하여 총 3초가 걸리고, 단독 우승할 수 있다.
- 그보다 조금 덜 사용하여 Z = 9미터를 1초만에 이동하면, 나머지 3m는 원래 속도로 이동하여 총 4초가 걸리고, 1번 자동차와 같은 시간만큼 걸린다 (공동 우승).
위의 예제의 경우 단독 우승을 하기 위해 최소 10미터를 부스터를 사용하여 이동하여야 하므로, 원하는 답이 10이다.
입력으로 N, X, Y, 그리고 각 장난감 자동차의 속도 V가 주어졌을 때 단독 우승을 하기 위해 부스터를 사용해서 이동해야하는 최소한의 거리를 구하는 프로그램을 작성하시오.
입력
첫 줄에 테스트 케이스의 수 T가 주어진다.
각 테스트 케이스의 첫 줄에 N, X, Y가 공백으로 구분되어 주어진다.
둘째 줄에 N개의 정수가 공백으로 구분되어 주어지는데 이는 각 장난감 자동차의 속도 V[i]를 나타낸다.
출력
각 테스트 케이스에 대해 단독 우승을 위해 부스터를 사용해서 이동해야하는 최소한의 거리를 출력한다.
만약 부스터를 쓰지 않고도 단독 우승이 가능하다면 0을 출력한다.
부스터를 최대치로 사용하고도 단독 우승이 불가능하다면 -1을 출력한다.
제한
- 1 ≤ T ≤ 10
- 2 ≤ N ≤ 1,000
- 1 ≤ Y ≤ X ≤ 1,000,000
- 1 ≤ V[i] ≤ 1,000,000
예제 입력 1
5 3 12 11 3 2 1 3 12 9 3 2 1 3 12 10 3 4 5 3 80 80 80 60 70 3 80 80 70 50 60
예제 출력 1
10 -1 0 -1 72
© 2023 All Rights Reserved. 주식회사 스타트링크 | 서비스 약관 | 개인정보 보호 | 결제 이용 약관 | 도움말 | 광고 문의 | 업데이트 노트 | 이슈 | TODO
- 사업자 등록 번호: 541-88-00682
- 대표자명: 최백준
- 주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
- 전화번호: 02-521-0487 (이메일로 연락 주세요)
- 이메일: contacts@startlink.io
- 통신판매신고번호: 제 2017-서울서초-2193 호