두 배
골드 III의견: 0
길이 \(N\)인 양의 정수열 \(A_1, \dots , A_N\)이 주어진다. 이 수열을 오름차순으로 만들려 한다. 수열 \(A_1, \dots , 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\))
첫 번째 줄에 \(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점 | 추가 제약 조건 없음. |
5
3 1 4 1 5
4
5
3 1 5 1 5
6
5
1 2 3 4 5
0
riseoj 작성
출처 올림피아드 > 한국정보올림피아드 > KOI 2024 > 1차 대회 > 초등부 2번 / 중등부 1번
평가 및 의견
두 배
Log in to rate problems.
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
두 배