IOI 2011 day1 3- 쌀 창고(Rice Hub) > 문제은행 : 정보올림피아드&알고리즘




2676 : 쌀 창고(Rice Hub)

제한시간
1000 ms   
메모리제한
256 MB   
해결횟수
9 회   
시도횟수
30 회   

문제

어느 시골에, 쌀의 길이라고 불리는 긴 직선 도로가 있다.

이 길을 따라 R 개의 논들이 있다.

각 논들은 1이상 L 이하의 정수좌표를 갖는다.

논들은 좌표 값이 감소하지 않는 순서로 주어진다.

즉, 0 ≤ i < R에 대해서, 논 i 는 좌표 X[i] 에 있다. 1 ≤ X[0] ≤ ... ≤ X[R-1] ≤ L라고 가정할 수 있다.

 

여러 개의 논이 하나의 같은 좌표에 있을 수 있음을 주의하라.

 

논에서 수확한 가능한 가장 많은 쌀들을 저장할 수 있는 하나의 쌀 창고를 세우려고 계획하고 있다.

논의 위치와 같이, 쌀 창고의 위치는 1이상 L 이하의 정수좌표에만 있을 수 있다.

쌀 창고는 논들이 위치하고 있는 장소를 포함하여 어떤 곳에든지 세울 수 있다.

 

수확의 계절에 각 논들은 정확히 트럭 한대 분량의 쌀만 생산할 수 있다.

쌀들을 창고로 옮기기 위해서 트럭 운전사들을 고용하여야 한다.

트럭 운전사는 한 트럭분량의 쌀을 창고로 옮기는데 단위 거리당 1 바트의 요금을 청구한다.

다르게 말하자면, 논으로부터 쌀을 창고로 옮기는 비용은, 논의 좌표 값과 창고의 좌표 값의 차이와 같다.

 

불행히도, 올해의 예산이 충분하지 못하여 쌀의 수송에는 최대 B 바트 까지만 사용할 수 있다.

여러분이 해야 할 일은 가능한 가장 많은 쌀을 창고로 모으기 위한 창고의 위치를 결정하는 것이다.

 

해야 할 일(Your task)
반드시 최적의 쌀 창고의 위치를 찾아야 하고,

예산 범위 이내에서 쌀 창고까지 옮길 수 있는 최대 쌀의 양이 트럭 몇 대 분량 인지를 구하여야 한다.

 

쌀을 옮기는데 허용된 예산은 매우 클 수가 있음을 주의하라.

예산은 64-비트의 정수로 주어지고, 계산 과정에서는 64-비트의 정수를 사용하도록 권장한다.

 

 

예제 설명 

 

다음의 경우를 고려해보자. R=5, L=20, B=6, X= 1 2 10 12 14 

 


 

 

이 경우에는 창고의 위치에 대한 여러 개의 최적 위치가 있다: 

10 이상 14 이하의 어느 정수 위치에든지 쌀 창고를 둘 수 있다. 

위의 그림은 최적 위치들 중의 하나를 보여준다. 

이 경우 10 과 12, 14 의 위치에 있는 논으로부터 쌀들을 옮길 수 있다. 

어떤 최적의 창고 위치에 대해서든지, 쌀의 총 수송비용은 6 바트 이하이다. 

세 개보다 많은 논으로부터 쌀을 모을 수 있는 창고의 위치는 존재하지 않으므로, 3 최적이다.​ 


입력형식

입력의 첫 줄에 R, L, B가 들어오고 그 다음 줄부터 R개의 X가 들어온다. ● R - 논의 수. 논들은0 이상 R-1 이하의 번호로 나타낸다. ● L - 최대 좌표 값. ● X - 가장 작은 수부터 가장 큰 수까지 정렬된 정수의 1차원 배열. 0 ≤ i < R에 대하여, 논 i 는X[i]에 위치한다. ● B - 예산. <서브테스크> 서브태스크 1 1 ≤ R ≤ 100 1 ≤ L ≤ 100 0 ≤ B ≤ 10,000 모든 논들의 좌표는 서로 다르다 (이 서브태스크 에서만). 서브태스크 2 1 ≤ R ≤ 500 1 ≤ L ≤ 10,000 0 ≤ B ≤ 1,000,000 서브태스크 3 1 ≤ R ≤ 5,000 1 ≤ L ≤ 1,000,000 0 ≤ B ≤ 2,000,000,000 서브태스크 4 1 ≤ R ≤ 100,000 1 ≤ L ≤ 1,000,000,000 0 ≤ B ≤ 2,000,000,000,000,000

출력형식

출력의 첫 줄에 쌀 창고의 위치를 찾아야 하고, 예산 범위 이내에서 쌀 창고까지 옮길 수 있는 최대 쌀의 양이 트럭 몇 대 분량 인지를 출력한다.

입력 예

5 20 6
1
2
10
12
14

출력 예

3


경기도 안양시 동안구 평촌대로 109 협성골드프라자 601호

TEL : 031-360-4144 FAX : 031-388-0996 E-mail : hancomc@hotmail.com, comkiwer@naver.com

Copyrightⓒ 2010 jungol. All right reserved.

TOP