길이 \(N\)인 양의 정수열 \(A_1, . . . , A_N\)이 주어진다. 이 수열을 오름차순으로 만들려 한다. 수열 \(A_1, . . . , A_N\)이 오름차순이라는 것은, 각 \(i (1 ≤ i ≤ N − 1)\)에 대해 \(A_i ≤ A_{i+1}\)이라는 것이다.
수열 \(A\)를 오름차순으로 만들기 위해, 수열 \(A\)에 다음 연산을 몇 번이든 반복해서 적용할 수 있다

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

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

제약 조건
• 주어지는 모든 수는 정수이다.
• \(1 \le N \le 250 000\)
• \(1 \le A_i \le 1 000 000 (1 \le i \le 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점) 추가 제약 조건 없음

첫 번째 줄에 \(N\)이 주어진다.
두 번째 줄에 \(A_1, . . . , A_N\)이 주어진다.

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

	작성자	제목(댓글)
글이 없습니다.

문제 게시판

새 글 작성

2024KOI1차