레이팅 미적용설명
농장 너머의 장기적인 진로 가능성을 염두에 두고, 소 베시는 여러 온라인 코딩 사이트에서 알고리즘을 배우기 시작했다.
지금까지 베시가 가장 좋아하는 알고리즘은 "버블 정렬"이다. 다음은 길이 \(N\)의 배열 \(A\)를 정렬하는, 소 코드로 작성한 베시의 구현이다.
sorted = false
while (not sorted):
sorted = true
moo
for i = 0 to N-2:
if A[i+1] < A[i]:
swap A[i], A[i+1]
sorted = false
소 코드의 "moo" 명령은 "moo"를 출력하는 것 외에는 아무 일도 하지 않는 듯하다. 이상하게도 베시는 코드 곳곳에 이 명령을 넣겠다고 고집하는 것 같다.
입력 배열이 주어졌을 때, 베시의 코드가 "moo"를 몇 번 출력할지 예측해 보자.
출제자: Brian Dean
제약
출제자: Brian Dean
입력 형식
입력의 첫째 줄에 \(N\) (\(1 \leq N \leq 100,000\))이 주어진다. 다음 \(N\)개의 줄에는 \(A[0] \ldots A[N-1]\)이 주어지며, 각각 \(0 \ldots 10^9\) 범위의 정수이다. 입력 원소들이 서로 다르다는 보장은 없다.
출력 형식
"moo"가 출력되는 횟수를 출력한다.
Standard input / output
This problem is judged over standard input/output. The original contest used named files — if you prefer the classic interface, tick “File I/O” on the submit form and read/write these files instead:
입력을 읽을 파일
sort.in · 출력을 쓸 파일 sort.out예제 1
입력
5
1
5
3
8
2출력
4문제 정보
riseoj 작성
출처 올림피아드 > USACO > 2017-2018 > US Open > Silver
태그