| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 | 1024 MB | 9360 | 1639 | 1064 | 20.301% |
길이 $N$인 양의 정수열 $A_1, \dots , A_N$이 주어진다. 이 수열을 오름차순으로 만들려 한다. 수열 $A_1, \dots , A_N$이 오름차순이라는 것은, 각 $i$ (1ドル ≤ i ≤ N - 1$)에 대해 $A_i ≤ A_{i+1}$이라는 것이다.
수열 $A$를 오름차순으로 만들기 위해, 수열 $A$에 다음 연산을 몇 번이든 반복해서 적용할 수 있다.
연산을 최소 횟수로 적용해서 $A$를 오름차순으로 만들고 싶다. 이때, 최소 횟수를 구하라.
첫 번째 줄에 $N$이 주어진다.
두 번째 줄에 $A_1, \dots , A_N$이 주어진다.
첫 번째 줄에 답을 출력한다.
| 번호 | 배점 | 제한 |
|---|---|---|
| 1 | 12 | 각 $i$ (1ドル ≤ i ≤ N$)에 대해, $A_i = 1$ 또는 $A_i = 2$ |
| 2 | 10 | 각 $i$ (1ドル ≤ i ≤ N$)에 대해, $A_i = 2^{k_i}$를 만족하는 0ドル$ 이상의 정수 $k_i$가 존재 |
| 3 | 11 | $N ≤ 10$ |
| 4 | 19 | 각 $i$ (1ドル ≤ i ≤ N$)에 대해, $A_i = 2$ 또는 $A_i = 3$ |
| 5 | 20 | 각 $i$ (1ドル ≤ i ≤ N - 1$)에 대해, $A_i ≥ A_{i+1}$ |
| 6 | 28 | 추가 제약 조건 없음 |
5 3 1 4 1 5
4
$A_2,ドル $A_4$에 각각 두 번씩 연산을 적용하면 된다. 연산을 적용한 이후에 수열 $A$는 $[3, 4, 4, 4, 5]$가 된다.
5 3 1 5 1 5
6
$A_2$에 두 번, $A_4$에 세 번, $A_5$에 한 번 연산을 적용하면 된다. 연산을 적용한 이후에 수열 $A$는 $[3, 4, 5, 8, 10]$가 된다.
5 1 2 3 4 5
0
Olympiad > 한국정보올림피아드 > KOI 2024 1차대회 > 초등부 2번
Olympiad > 한국정보올림피아드 > KOI 2024 1차대회 > 중등부 1번