RiseOJ – 두 배

설명

길이 $$N$$ 인 양의 정수열 $A_1, \dots , A_N$ 이 주어진다. 이 수열을 오름차순으로 만들려 한다. 수열 $A_1, \dots , A_N$ 이 오름차순이라는 것은, 각 $$i$$ ( $$1 \leq i \leq N - 1$$ )에 대해 $A_i ≤ A_{i+1}$ 이라는 것이다.

수열 $$A$$ 를 오름차순으로 만들기 위해, 수열 $$A$$ 에 다음 연산을 몇 번이든 반복해서 적용할 수 있다.

어떤 $$i$$ ( $$1 \leq i \leq N$$ )에 대해 $$A_i$$ 에 $$2$$ 를 곱한다.

연산을 최소 횟수로 적용해서 $$A$$ 를 오름차순으로 만들고 싶다. 이때, 최소 횟수를 구하라.

제약

주어지는 모든 수는 정수이다.
$1 \le N \le 250\,000$
$1 \le A_i \le 1\,000\,000$ ( $1 \le i \le N$ )

입력 형식

첫 번째 줄에 $$N$$ 이 주어진다.

두 번째 줄에 $A_1, \dots , A_N$ 이 주어진다.

출력 형식

첫 번째 줄에 답을 출력한다.

서브태스크

서브태스크	점수	설명
1	12점	각 $$i$$ ( $1 \le i \le N$ )에 대해, $$A_i = 1$$ 또는 $$A_i = 2$$ .
2	10점	각 $$i$$ ( $1 \le i \le N$ )에 대해, $A_i = 2^{k_i}$ 를 만족하는 $$0$$ 이상의 정수 $$k_i$$ 가 존재한다.
3	11점	$N \le 10$ .
4	19점	각 $$i$$ ( $1 \le i \le N$ )에 대해, $$A_i = 2$$ 또는 $$A_i = 3$$ .
5	20점	각 $$i$$ ( $1 \le i \le N - 1$ )에 대해, $A_i \ge A_{i+1}$ .
6	28점	추가 제약 조건 없음.

예제 1

입력

5
3 1 4 1 5

출력

예제 2

입력

5
3 1 5 1 5

출력

예제 3

입력

5
1 2 3 4 5

출력

문제 정보

riseoj 작성

출처 올림피아드 > 한국정보올림피아드 > KOI 2024 > 1차 대회 > 초등부 2번 / 중등부 1번

올림피아드 > 한국정보올림피아드 > KOI 2024 > 1차 대회 > 초등부 올림피아드 > 한국정보올림피아드 > KOI 2024 > 1차 대회 > 중등부

태그

#수학 #그리디 JudgeKOI

두 배

평가 및 의견

풀이 제출

서브태스크	점수	설명
1	12점	각 $\(i\)$ ( $1 \le i \le N$ )에 대해, $\(A_i = 1\)$ 또는 $\(A_i = 2\)$ .
2	10점	각 $\(i\)$ ( $1 \le i \le N$ )에 대해, $A_i = 2^{k_i}$ 를 만족하는 $\(0\)$ 이상의 정수 $\(k_i\)$ 가 존재한다.
3	11점	$N \le 10$ .
4	19점	각 $\(i\)$ ( $1 \le i \le N$ )에 대해, $\(A_i = 2\)$ 또는 $\(A_i = 3\)$ .
5	20점	각 $\(i\)$ ( $1 \le i \le N - 1$ )에 대해, $A_i \ge A_{i+1}$ .
6	28점	추가 제약 조건 없음.