원문 PDF 의 글을 화면용으로 옮겼습니다. 내용이 다르면 원문이 맞습니다. (검수일 2026-11-20)
두 배
원제: 두 배
문제
길이 인 양의 정수열 이 주어진다. 이 수열을 오름차순으로 만들려 한다. 수열 이 오름차순이라는 것은, 각 ()에 대해 이라는 것이다.
수열 를 오름차순으로 만들기 위해, 수열 에 다음 연산을 몇 번이든 반복해서 적용할 수 있다.
- 어떤 ()에 대해 에 를 곱한다.
연산을 최소 횟수로 적용해서 를 오름차순으로 만들고 싶다. 이때, 최소 횟수를 구하라.
제약 조건
- 주어지는 모든 수는 정수이다.
- ()
부분문제
- (12점) 각 ()에 대해, 또는
- (10점) 각 ()에 대해, 를 만족하는 0 이상의 정수 가 존재
- (11점)
- (19점) 각 ()에 대해, 또는
- (20점) 각 ()에 대해,
- (28점) 추가 제약 조건 없음
입력 형식
첫 번째 줄에 이 주어진다.
두 번째 줄에 이 주어진다.
출력 형식
첫 번째 줄에 답을 출력한다.
예제
예제 1
입력
5 3 1 4 1 5
출력
4
, 에 각각 두 번씩 연산을 적용하면 된다. 연산을 적용한 이후에 수열 는 가 된다.
예제 2
입력
5 3 1 5 1 5
출력
6
에 두 번, 에 세 번, 에 한 번 연산을 적용하면 된다. 연산을 적용한 이후에 수열 는 가 된다.
예제 3
입력
5 1 2 3 4 5
출력
0