Начало
Рабочее место участника
| Выбрать соревнование | Задачи | Послать решение | Результаты проверки | Статистика по задачам | Вопросы и ответы | Результаты соревнования | Состояние сервера | Изменить данные | Управление командой | Помощь |
Задачи
1859. Правдолюбы и лгуны
Индукция и другие математические методыОлимпиадные задачи на русском языке
| 28/10/2012 | Региональные отборочные командные соревнования для школьников (F) |
| 22/07/2015 | Практика 1 и 2 курса (7) (A) |
Ограничения: время – 1s/2s, память – 256MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод 
Послать решение Blockly Посылки Темы Где Обсудить (0) 
Трактир "Залатанный барабан" весьма популярен среди искателей приключений, наемников, сорвиголов и
негодяев. Искатели приключений всегда ходят большими кампаниями, так как убить дракона
или гигантского монстра в одиночку практически невозможно. Рассказывая о своих подвигах одни
герои (лгуны) всегда их приукрашивают, а другие (правдолюбы) говорят только правду. Нельзя
верить ни одному числу, сказанному лгуном. Он может рассказать, как одним выстрелом из баллисты
убил семь драконов, хотя всем известно, что драконы не летают стаями, и у них только одно
уязвимое место на брюхе, в которое очень сложно попасть. Во время путешествий герои часто
рассказывают друг другу истории и поэтому знают, сколько в их кампании лгунов и правдолюбцев.
Трактирщик Чарли решил узнать, сколько лгунов в кампании, зашедшей в его трактир, так
как кампания, в которой все лгуны, может удрать, не заплатив, или расплатиться фальшивой монетой. Но
в результате, опросив всех героев и получив разные числа, Чарли не смог разобраться с этой проблемой.
Напишите программу, которая поможет Чарли определить, сколько лгунов в кампании, зашедшей в трактир.
Формат ввода
Первая строка ввода содержит одно целое число `N` (`2\ ≤\ N\ ≤\ 100`) – количество человек в кампании.
Во второй строке содержится `N` целых чисел в диапазоне от 0 до `N` – ответы искателей приключений на
вопрос Чарли о количестве лгунов в их кампании.
Формат вывода
В первой строке вывести одно число `K` – число вариантов количества лгунов.
Во второй строке вывести `K` чисел – варианты количества лгунов в порядке возрастания. Если `K` равно 0, то
вторая строка не выводится.
Пример ввода 1
2 1 1
Пример вывода 1
1 2
Пример ввода 2
2 1 0
Пример вывода 2
2 1 2
Пример ввода 3
2 0 2
Пример вывода 3
0
Во всех примерах количество лгунов может быть 0, 1 или 2.
В первом примере ни один из героев не может быть правдолюбом. Если один из участников правдолюб, то он сказал правду, тогда второй лгун, который тоже сказал правильное количество лгунов, противоречие. Следовательно, оба героя лгут.
В втором примере, если сказал правду герой, сказавший 0, то второй герой тоже должен был сказать 0. Следовательно, сказать правду мог только герой, назвавший число 1. Так же есть вариант когда оба героя лгут, не называя число 2.
В третьем примере не может говорить правду ни первый, ни второй герой, так как при этом получается противоречие. Оба герои не могут быть и лгунами, так как при этом получилось бы, что второй герой сказал правду. Возможно, Чарли ошибся и опросил не всех людей в кампании. Поэтому вариантов 0.
