Олимпиадный тренинг

Задача . Counting Friends


Задача

Темы: графы

N коров Фермера Джона (2 <= N <= 500) объединились в социальную сеть "MooBook". Каждая корова имеет одну или более подружек с которой контактирует в MooBook. ФД сделал список, содержащий для каждой коровы количество её подружек, однако по ошибке он включил в список одно лишнее число и его список содержит N+1 число вместо планировавшихся N чисел.
Пожалуйста, помогите ФД определить какое число в этом списке является лишним – то есть внесённым по ошибке.
PROBLEM NAME: fcount
Формат входных данных
* Строка 1: Одно целое число N.
* Строки 2..2+N: Строка i+1 содержит количество подружек для одной из коров ФД или возможно неправильное лишнее число.
Формат выходных данных
* Строка 1: Целое число K, определяющее количество возможных ошибочного чисел, или 0, если не существует числа в этом списке, удаление которого нарушило бы парность друзей.
* Строки 2..1+K: Каждая строка содержит индекс от 1 до N+1 числа во входной нумерации чисел, которое потенциально может быть лишним числом, поскольку это число может быть удалено и оставшиеся N чисел определяют допустимое множество отношений дружбы между оставшимися коровами. Эти строки должны быть в отсортированном порядке.
Примечание
Удаление первого числа (число 1) оставляет в списке числа 2 2 3 1. Если обозначить коров символами от A до D, то при отношении дружбы заданном парами (A,B), (A,C), (A,D), (B,C) мы получим что у коровы A 3 подружки, у коров B и С по 2 подружки, а у D – 1 подружка. Аналогично при удалении другой 1 и при удалении 3. Удаление числа 2 невозможно – сумма оставшихся чисел нечётна, из чего с очевидностью следует невозможность составить пары.
Примеры
№Входные данныеВыходные данные
1 
4
1
2
2
1
3
 
3
1
4
5
Статистика успешных решений по компиляторам
Комментарий учителя

Ваш ответ

выберите язык и введите исходный код


Для отправки решения задачи необходимо зарегистрироваться или авторизоваться!
     

Загруженные файлы
Нет