Early in the morning, Farmer John woke up to the sound of splintering wood. It
was the cows, and they were breaking out of the barn again!

Farmer John was sick and tired of the cows' morning breakouts, and he decided
enough was enough: it was time to get tough. He nailed to the barn wall a
counter tracking the number of days since the last breakout. So if a breakout
occurred in the morning, the counter would be \(0\) that day; if the most recent
breakout was \(3\) days ago, the counter would read \(3\). Farmer John meticulously
logged the counter every day.

The end of the year has come, and Farmer John is ready to do some accounting.
The cows will pay, he says! But lo and behold, some entries of his log are
missing!

Farmer John is confident that the he started his log on the day of a breakout.
Please help him determine, out of all sequences of events consistent with the
log entries that remain, the minimum and maximum number of breakouts that may
have take place over the course of the logged time.

Problem credits: Dhruv Rohatgi

Problem credits: Dhruv Rohatgi

The first line contains a single integer \(N\) (\(1 \leq N \leq 100\)), denoting the
number of days since Farmer John started logging the cow breakout counter.

The second line contains \(N\) space-separated integers. The \(i\)th integer is
either \(-1\), indicating that the log entry for day \(i\) is missing, or a
non-negative integer \(a_i\) (at most \(100\)), indicating that on day \(i\) the counter
was at
\(a_i\).

If there is no sequence of events consistent with Farmer John's partial log and
his knowledge that the cows definitely broke out of the barn on the morning of
day \(1\), output a single integer \(-1\). Otherwise, output two space-separated
integers \(m\) followed by \(M\), where \(m\) is the minimum number of breakouts of
any consistent sequence of events, and \(M\) is the maximum.

riseoj 작성

출처 올림피아드 > USACO > 2017-2018 > February > Bronze