Taming the Herd

题目描述

清晨，Farmer John 被木头碎裂的声音吵醒。原来是奶牛们——它们又一次从牛棚里逃出来了！ Farmer John 对奶牛们每天早上的越狱行为忍无可忍，决定不再姑息：是时候强硬起来了。他在牛棚墙上钉了一个计数器，用来记录距离上一次越狱已经过去了多少天。因此，如果某天早上发生了越狱，那么计数器在这一天会显示为 $0$；如果最近一次越狱发生在 $3$ 天前，那么计数器会显示为 $3$。Farmer John 一丝不苟地每天记录计数器的数值。 一年结束了，Farmer John 准备做些账目核算。“奶牛们要付出代价！”他说。但令人震惊的是，他的日志中有一些记录丢失了！ Farmer John 确信他是在一次越狱发生的那天开始记录日志的。 请你帮助他确定：在所有与现存日志条目一致的事件序列中，在记录期间可能发生的越狱次数的最小值与最大值分别是多少。

输入格式

第一行包含一个整数 $N$（$1 \leq N \leq 100$），表示自 Farmer John 开始记录奶牛越狱计数器以来经过的天数。 第二行包含 $N$ 个用空格分隔的整数。第 $i$ 个整数要么为 $-1$，表示第 $i$ 天的日志记录缺失；要么为一个非负整数 $a_i$（不超过 $100$），表示第 $i$ 天计数器的值为 $a_i$。

输出格式

如果不存在任何事件序列能够同时满足 Farmer John 的部分日志以及他知道奶牛在第 $1$ 天早上一定发生过越狱这一事实，则输出一个整数 $-1$。否则，输出两个用空格分隔的整数 $m$ 和 $M$，其中 $m$ 是所有一致事件序列中越狱次数的最小值，$M$ 是最大值。

4
-1 -1 -1 1

2 3

提示

在该示例中，我们可以推断第 3 天必须发生过一次越狱。已知第 1 天也发生过越狱，那么唯一剩下的不确定性是第 2 天是否发生过越狱。因此，越狱总次数在 2 到 3 次之间。 题目来源：Dhruv Rohatgi

标签: USACO|2018|Bronze

来源

USACO|2018|Bronze