주식
면접 대비시간 제한1초메모리 제한512 MB
합에서 길이 곱하기 y를 뺀 값이 Z 이상이고 길이 곱하기 y가 X 이하인 가장 짧은 구간을 찾고, 길이가 같으면 시작일이 가장 늦은 구간을 고른다.
문제
당신은 주식을 사고 팔아 이윤을 남기려고 한다. 주식 투자에 관한 법이 최근 바뀌어 다음과 같은 제한이 생겼다.
- 시장은 1일차부터 n일차까지, n일 동안만 개장한다.
- 당신은 그중 연속된 k일 (k ≥ 1) 기간에만 참가할 수 있다. 참가하는 날에는 매일 반드시 주식을 사야 한다.
- 주식을 살 때의 가격은 매일 y원으로 일정하다.
- 주식을 팔 때의 가격은 i일차에 산 경우 V[i]원이며, 산 날짜에 따라 다르다. V[i]는 음수일 수 있다.
- 당신은 초기 자금 X원을 가지고 참가한다.
- 시장 개장 기간인 n일차가 지나기 전에는 산 주식을 팔 수 없다.
- 당신은 최소 Z원 이상의 이윤을 남겨야 한다. (Z ≥ 0)
즉, 1 ≤ i ≤ j ≤ n을 만족하는 i일차부터 j일차까지 주식을 샀다면,
(V[i] + V[i+1] + … + V[j-1] + V[j]) - y × (j - i + 1) ≥ Z 및 y × (j - i + 1) ≤ X 을 만족해야 한다.
이때 목표는 Z원 이상의 이윤을 남길 수 있는 구매 방법 중에서 기간이 가장 짧은 것을 찾는 것이다.
다시 말해, 이윤은 Z원 이상만 남길 수 있다면 얼마든 상관없고, Z원 이상의 이윤을 남기는 기간을 최대한 짧게 하고 싶다. 그러한 기간의 시작일과 종료일 i, j를 출력하는 프로그램을 작성하시오.
같은 최단 기간 구매법이 여러 개 존재한다면, 그중 i가 가장 큰 (즉, 시장에 가장 늦게 진입하는) 기간을 출력하시오.
Z원 이상의 이윤을 남길 수 있는 방법이 존재하지 않는다면 -1을 출력하시오.
입력
첫 줄에 테스트 케이스의 수 T가 주어진다 (1 ≤ T ≤ 10).
각 테스트 케이스는 두 줄에 걸쳐 주어진다.
첫째 줄에 n, X, y, Z가 공백으로 구분되어 주어진다. 0 ≤ X, y, Z ≤ 10⁹를 만족한다.
둘째 줄에 n개의 정수 V가 공백으로 구분되어 주어진다. 각 V[i]는 |V[i]| ≤ 10⁶를 만족한다.
출력
각 테스트 케이스마다 한 줄에 답을 출력한다. 문제에서 언급한 조건을 만족하는 i, j가 존재하지 않으면 -1을 출력하고, 그렇지 않으면 (j - i + 1)을 최소화하는 (i, j) 중 i가 최대인 i, j를 공백으로 구분하여 출력한다.