레이팅 미적용이른 아침, 농부 존은 나무가 부서지는 소리에 잠에서 깼다. 소들이었다. 소들이 또 헛간을 부수고 탈출하고 있었다!
농부 존은 소들의 아침 탈출에 진절머리가 났고, 더는 참을 수 없다고 결심했다. 이제 강경하게 나갈 때였다. 그는 마지막 탈출 이후 지난 날 수를 기록하는 계수기를 헛간 벽에 못으로 박아 두었다. 즉, 아침에 탈출이 일어났다면 그날 계수기는 \(0\)이 되고, 가장 최근의 탈출이 \(3\)일 전이었다면 계수기는 \(3\)을 가리킨다. 농부 존은 매일 꼼꼼하게 계수기 값을 기록했다.
연말이 되어 농부 존은 결산을 하려고 한다. 소들이 대가를 치르게 하겠다는 것이다! 그런데 이럴 수가, 기록의 일부 항목이 사라져 있었다!
농부 존은 자신이 기록을 시작한 날에 탈출이 있었다고 확신한다. 남아 있는 기록 항목들과 모순되지 않는 모든 사건 순서들 가운데, 기록된 기간 동안 일어났을 수 있는 탈출 횟수의 최솟값과 최댓값을 구하도록 도와주자.
출제자: Dhruv Rohatgi
출제자: Dhruv Rohatgi
첫째 줄에 농부 존이 소 탈출 계수기를 기록하기 시작한 이후 지난 날 수를 나타내는 정수 \(N\)이 하나 주어진다 (\(1 \leq N \leq 100\)).
둘째 줄에 공백으로 구분된 정수 \(N\)개가 주어진다. \(i\)번째 정수는 \(-1\)이거나(이는 \(i\)일째의 기록 항목이 사라졌음을 뜻한다), 음이 아닌 정수 \(a_i\)(\(100\) 이하)로, \(i\)일째에 계수기가 \(a_i\)였음을 뜻한다.
농부 존의 부분적인 기록 및 소들이 \(1\)일째 아침에 확실히 헛간을 탈출했다는 그의 확신과 모순되지 않는 사건 순서가 존재하지 않으면, 정수 \(-1\) 하나를 출력한다. 그렇지 않으면, 공백으로 구분된 두 정수 \(m\)과 \(M\)을 출력한다. 여기서 \(m\)은 모순되지 않는 사건 순서들의 최소 탈출 횟수이고, \(M\)은 최대 탈출 횟수이다.
taming.in · 출력을 쓸 파일 taming.out4
-1 -1 -1 12 3In this example, we can deduce that a breakout had to occur on day 3. Knowing
that a breakout also occurred on day 1, the only remaining bit of uncertainty
is whether a breakout occurred on day 2. Hence, there were between 2 and 3
breakouts in total.
riseoj 작성
출처 올림피아드 > USACO > 2017-2018 > February > Bronze