시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 1024 MB230826935.385%

문제

KSA의 모 선생님은 수학 공부를 많이 하는 학생을 좋아하기 때문에 앞으로 학생들에게 $N$일 동안 수학공부를 굉장히 많이 시키기로 결심했다. 선생님은 학생들이 $i$일차에 $A_i$개의 수학문제를 풀기를 원하고, 각 학생에 대한 호감도는 해당 학생이 수학공부를 얼마나 많이 풀었는지에 따라 달라진다. 어떤 학생이 $i$일차에 $x$개의 수학 문제를 풀었다면, 해당 학생에 대한 호감도는 $$f_i(x) = \begin{cases} x & \text{if } x \ge A_i, \\ 2(x - A_i) & \text{if }x < A_i \end{cases}$$만큼 증가한다.

상현이는 규칙적인 공부를 원하기 때문에 $N$일 동안 매일 동일한 양의 수학문제를 풀기로 마음먹었다. 처음에 상현이에 대한 선생님의 호감도가 $0$이며, 상현이는 $N$일 이후 $L$ 이상의 호감도를 얻고 싶다. 이때 하루에 풀어야 하는 수학 문제 수의 최솟값을 구하는 프로그램을 작성하시오.

입력

첫 번째 줄에 정수 $N$$(1 \le N \le 10^5)$이 주어진다.

두 번째 줄에 $N$개의 정수 $A_1, A_2, \cdots, A_N$이 공백으로 구분되어 주어진다. $(1 \le A_i \le 10^4)$

세 번째 줄에 정수 $L$$(1 \le L \le 10^9)$이 주어진다.

출력

상현이가 하루에 풀어야 하는 수학 문제 수의 최솟값을 출력한다.

예제 입력 1

2
5 4
6

예제 출력 1

5

하루에 $4$문제씩 풀면 이틀 후 호감도는 $(-2) + 4 = 2$로, $6$보다 작다. 대신 하루에 $5$문제씩 풀면 이틀 후 호감도는 $5 + 5 = 10$으로, $6$보다 크거나 같다.

출처

School > 한국과학영재학교 > 2024 Fall Automata 상현컵 B번