Украинские Олимпиады по Информатике

Материалы Информация Добро пожаловать Гостевая книга Обратная связь О сайте Сборник Ссылки Литература Статьи Рассылки Интервью Обзор Международные Всесоюзные Всеукраинские (IV этап) Разные...

Донецк'2003, II тур Цепь Есть N кусков цепи, каждый i-й из которых содержит Li звеньев. Можно разгибать произвольные звенья и потом сгибать их снова, соединяя отдельные куски. Задание Напишите программу CHAIN, которая по количеству кусков цепи N и количеству звеньев в кусках Li определяет минимальное количество звеньев, которые нужно разогнуть и согнуть снова, чтобы соединить все куски в одну цепь. Цепь не может иметь разветвлений, т.е. каждое звено должно быть соединено с двумя звеньями (кроме двух звеньев по краям цепи, которые должны быть соединены только с одним звеном). Входные данные В первой строке входного файла CHAIN.DAT находится целое число N (2£N£10 000). Во второй строке находятся N целых чисел Li (1£Li£1 000 000 000). Выходные данные В единственной строке выходного файла CHAIN.SOL должно находится целое число — наименьшее количество звеньев, которые необходимо разогнуть и согнуть снова, чтобы получить одну цепь из всех кусков. Пример входных данных 3 100 3 4 Пример выходных данных 2

Олимпиады Всеукраинские 1988 1989 1990 1991 1992 1993 1994 1995 1996 1997 1998 1999 2000 2001 2002 2003 2004 Отборочные сборы 1992 1993 1994 1996 1997 1998 1999 2000 2001 2002 2003 2004 Международные 1989 1990 1991 1992 1993 1994 1995 1996 1997 1998 1999 2000 2001 2002 2003 2004 Всесоюзные 1988 1989 1990 1991 1992

© Разработано рабочей группой UOI 1998-2004 гг.