RiseOJ – 욕심쟁이 선물 받기

설명

농부 존의 숙적인 농부 논에게는 $$N$$ 마리의 소 ( $1 \leq N \leq 10^5$ )가 있으며, 편의상 $1 \dots N$ 으로 번호가 매겨져 있다. 이 소들이 갑자기 농부 존의 농장에 나타났고, 한결같이 예의 바른 농부 존은 소들에게 선물을 주려고 한다.

이를 위해 농부 존은 무한한 선물 재고를 꺼내 왔고, 논의 소들은 그 앞에 줄을 섰다. 소 $$1$$ 이 줄의 맨 앞, 소 $$N$$ 이 맨 뒤이다. 농부 존은 매 시간 단계마다 줄 맨 앞의 소가 선물을 받고 줄 맨 뒤로 가리라 기대했다. 하지만 그는 논의 소들이 그렇게 예의 바르지 않다는 것을 방금 깨달았다! 각 소는 선물을 받은 후 줄 맨 뒤로 가지 않고, 맨 뒤쪽의 몇 마리 소들 앞에 새치기해서 끼어들 수 있다. 구체적으로, 소 $$i$$ 는 항상 정확히 $$c_i$$ 마리 ( $0 \leq c_i \leq N-1$ )를 새치기한다.

농부 존은 어떤 소들은 선물을 여러 번 받을 수도 있다는 것을 알고 있다. 선물 재고가 무한하므로 이는 걱정거리가 아니다. 하지만 어떤 소들이 선물을 하나도 받지 못해 불행해질까 봐 걱정이다.

선물을 아무리 많이 나누어 주어도 선물을 전혀 받지 못하는 소의 수를 구해 농부 존을 도와주자.

Problem credits: Dhruv Rohatgi

제약

Problem credits: Dhruv Rohatgi

입력 형식

첫째 줄에 정수 $$N$$ 이 하나 주어진다.

둘째 줄에 공백으로 구분된 $$N$$ 개의 정수 $c_1, c_2, \dots, c_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:

입력을 읽을 파일 greedy.in · 출력을 쓸 파일 greedy.out

예제 1

입력

3
1 2 0

출력

문제 정보

riseoj 작성

출처 올림피아드 > USACO > 2017-2018 > December > Platinum

올림피아드 > USACO > 2017-2018 > December > Platinum

태그

JudgeUSACO

욕심쟁이 선물 받기

평가 및 의견

풀이 제출