Codeforces Round 870 (Div. 2) |
---|
Закончено |
Есть группа из $$$n$$$ человек. Некоторые из них могут быть лжецами, которые всегда лгут. Остальные люди всегда говорят правду. $$$i$$$-й человек сказал: «Среди нас не менее $$$l_i$$$ лжецов». Определите, является ли сказанное людьми противоречивым, или это возможно. Если это возможно, выведите количество лжецов в группе. Если ответов несколько, вы можете вывести любой из них.
В первой строке находится единственное целое число $$$t$$$ ($$$1 \leq t \leq 1000$$$) — число наборов входных данных.
Первая строка каждого набора входных данных содержит единственное целое число $$$n$$$ ($$$1 \leq n \leq 100$$$).
Вторая строка каждого набора входных данных содержит $$$n$$$ целых чисел $$$l_i$$$ ($$$0 \leq l_i \leq n$$$) — число, которое сказал $$$i$$$-й человек.
Гарантируется, что сумма $$$n$$$ по всем наборам входных данных не превосходит $$$10^4$$$.
Для каждого набора входных данных выведите одно целое число. Если сказанное людьми противоречиво, выведите $$$-1$$$. Иначе выведите количество лжецов в группе. Если ответов несколько, вы можете вывести любой из них.
721 222 220 0111055 5 3 3 565 3 6 6 3 5
1 -1 0 -1 0 3 4
В первом примере единственный возможной ответ, это что лжет второй человек, откуда ответ $$$1$$$ лжец.
Во втором примере можно показать, что невозможно выбрать лжецов, так чтобы все высказывания удовлетворяли условию.
В третьем примере все говорят правду, откуда ответ $$$0$$$ лжецов.
Название |
---|