레이팅 미적용설명
베시와 엘시는 농부 존의 설거지를 돕고 있다. 마주 보는 엄지가 없는 소들에게 이 일은 생각보다 훨씬 복잡한 과정이다.
두 소는 베시가 비누칠을 하고 엘시가 헹구기로 한다. 베시에게는 \(1\)부터 \(N\)까지 (\(1 \leq N \leq 10^5\)) 번호가 붙은 더러운 접시 더미가 주어진다. 엘시에게는 깨끗한 접시가 놓일 빈 더미가 있다. 베시와 엘시 사이에는 비누칠된 접시 더미들을 놓을 조리대가 있다.
각 단계에서 다음 중 하나가 일어난다:
- 베시가 더러운 더미의 맨 위에서 접시를 하나 집어 비누칠을 한 다음 조리대에 놓는다. 비누칠된 접시를 조리대에 놓을 때, 베시는 (i) 이미 존재하는 비어 있지 않은 비누칠 더미의 맨 위에 접시를 놓거나 (ii) 기존의 모든 비누칠 더미의 오른쪽에 새로운 비누칠 더미를 만들어야 한다.
- 엘시가 가장 왼쪽 비누칠 더미의 맨 위에서 접시를 하나 집는다. 엘시는 접시를 헹군 다음 깨끗한 더미의 맨 위에 놓는다.
목표는 깨끗한 더미의 모든 접시가 가장 작은 번호가 맨 아래, 가장 큰 번호가 맨 위에 오도록 순서대로 쌓이는 것이다. 접시 더미 전체에 대해 이 목표를 달성하는 것이 불가능할 수도 있으므로, 입력 순서의 접두사 중 목표 달성이 가능한 가장 긴 접두사의 길이를 구하시오.
문제 제공: George Xing
제약
문제 제공: George Xing
입력 형식
첫째 줄에 \(N\)이 주어진다. 다음 \(N\)개의 줄은 베시의 더미에 있는 접시들의 순서를 나타내며, 첫 번째 수가 더미 맨 위의 접시이다.
출력 형식
접시들이 깨끗한 더미에 올바른 순서로 쌓이도록 성공적으로 설거지할 수 있는, 입력 더미의 가장 긴 접두사의 길이를 출력한다.
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:
입력을 읽을 파일
dishes.in · 출력을 쓸 파일 dishes.out예제 1
입력
5
4
5
2
3
1출력
4문제 정보
riseoj 작성
출처 올림피아드 > USACO > 2018-2019 > February > Gold
태그