시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
1 초 | 512 MB | 119 | 48 | 18 | 45.000% |
당신은 주식을 사고 팔아 이윤을 남기고 싶다. 주식 투자에 대한 법이 최근 바뀌어 아래와 같은 제한이 있다.
즉, 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 ≤ 109 를 만족한다.
둘째 줄에 n개의 정수 V가 공백으로 구분되어 주어진다. 각 V[i] 는 |V[i]| ≤ 106 를 만족한다.
각 테스트 케이스에 대해 한 줄에 답을 출력한다. 문제에서 언급된 조건들을 만족하는 i, j가 존재하지 않을 경우 -1을 출력하고, 아닌 경우 묘사된대로 (j - i + 1)을 최소화 하는 (i, j) 중 i값이 최대가 되는 i, j 를 공백으로 구분하여 출력한다.
5 1 0 0 1 1 2 0 0 4 1 2 3 0 0 3 2 -1 2 3 0 0 2 2 -1 2 3 0 0 1 2 -1 2
1 1 -1 1 3 3 3 3 3