문제
당신을 포함한 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
나의 풀이:
다른 사람 풀이:
TAKEAWAY:
느낀점:
