问题 3934 --Minimum Liars

3934: Minimum Liars

时间限制: 1 Sec  内存限制: 128 MB
提交: 0  解决: 0
[提交][状态][讨论版][命题人:]

题目描述

There is a group of N people numbered from 0 to N-1. Each of them is either an honest person or a liar. You wish to know how many liars are in the group. To do this, you have asked the same question to every person in the group: "What is the number of liars in this group?". The people in the group themselves know the exact number of liars, but since you are a foreigner in the group, they have not told it to you exactly. Instead, the i-th person answered you as follows: "There are at least claim[i] liars in the group." It is known that statements by honest persons are always true. However, statements by liars are always false. So, if a liar claims that there are at least X liars in the group, then in fact there are less than X liars.


Now, given a vector claim[i] containing the N answers that you received, you would like to determine the number of liars in the group. Unfortunately, there's another twist that makes this problem more complicated. The people in the group speak a different language than you, so you might have misunderstood some of their answers. The answers in claim are how you understood them, but they might not match what the people actually told you. If you definitely misunderstood at least one of the answers, return -1. Otherwise, assuming that you understood all answers correctly, return the minimum number of liars that could be in the group.

输入

The first line of each case contains n,n<=50,and then the second line contains n integers:claim[0]---claim[n-1],for each i(0<=i<n),0<=claim[i]<=100.

输出

For each test case, print a line containingthe minimum number of lairs that could be in the group.

If you definitely misunderstood at least one of the answers,return -1.

样例输入

4
1 1 1 2
5
5 5 5 5 5

样例输出

1
-1

提示

The first case:It would be impossible for all the members of the group to be honest because in that case, all of their answers would be 0. It is, however, possible that only the last person is a liar and each of the first three persons is honest. Therefore the correct answer is 1.


The second case:Everybody agrees that there are at least 5 liars in the group. The group contains exactly 5 people, so in fact all of them claim that everybody is a liar. We can't assume that some person is honest because this person definitely wouldn't have claimed him/herself as being a liar. We also can't assume that all of them are liars because in this case it will appear that all their statements are true. Every scenario we can try leads to a contradiction, so you must have misunderstood at least one of the answers.

来源

 

[提交][状态]