레이팅 미적용설명
베시와 친구들은 편리하게 1..N으로 번호가 매겨진 N (1 <= N <= 100,000)개의 서로 다른 랭크를 가진 덱을 사용하는 독특한 버전의 포커를 하고 있다 (보통의 덱은 N = 13이다). 이 게임에서 소들이 낼 수 있는 핸드는 한 종류뿐이다. i라고 적힌 카드와 j라고 적힌 카드를 골라 i부터 j까지의 모든 값의 카드를 한 장씩 내는 것이다. 이런 종류의 핸드를 "스트레이트"라고 부른다.
베시의 손에는 현재 랭크 i의 카드가 a_i장 있다 (0 <= a_i <= 100000). 모든 카드를 없애기 위해 그녀가 내야 하는 핸드의 최소 개수를 구하는 것을 도와주자.
제약
문제 제공: Albert Gu, 2011
입력 형식
첫째 줄: 정수 N.
둘째 줄부터 1+N번째 줄까지: i+1번째 줄에 a_i의 값이 주어진다.
출력 형식
첫째 줄: 베시가 모든 카드를 없애기 위해 내야 하는 스트레이트의 최소 개수.
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:
입력을 읽을 파일
poker.in · 출력을 쓸 파일 poker.out예제 1
입력
5
2
4
1
2
3출력
6설명
Output details: Bessie can play a straight from 1 to 5, a straight from 1 to 2, a straight from 4 to 5, two straights from 2 to 2, and a straight from 5 to 5, for a total of 6 rounds necessary to get rid of all her cards.
문제 정보
태그