Rambler's Top100

Скачать программы    Все программы автора

ЦЕПЬ

Есть N кусков цепи, каждый i-й из которых содержит Li звеньев. Можно разгибать произвольные звенья и потом сгибать их снова, соединяя отдельные куски.

Задание

Напишите программу CHAIN, которая по количеству кусков цепи N и количеству звеньев в кусках Li определяет минимальное количество звеньев, которые нужно разогнуть и согнуть снова, чтобы соединить все куски в одну цепь. Цепь не может иметь разветвлений, т.е. каждое звено должно быть соединено с двумя звеньями (кроме двух звеньев по краям цепи, которые должны быть соединены только с одним звеном).

Входные данные

В первой строке входного файла CHAIN.DAT находится целое число N (2£N£10 000). Во второй строке находятся N целых чисел Li (1£Li£1 000 000 000).

Выходные данные

В единственной строке выходного файла CHAIN.SOL должно находится целое число — наименьшее количество звеньев, которые необходимо разогнуть и согнуть снова, чтобы получить одну цепь из всех кусков.

Пример входных и выходных данных

CHAIN.DAT

CHAIN.SOL

3

100 3 4

2

{ Problem: CHAIN}

const

maxN=10000;

Inf=maxN-1;

type

list = array[1..maxN] of word;

procedure heapsort(var a: list; N: word);

var

i:word;

procedure Xch(i,j:word);

var

temp:word;

begin

temp:=a[i];

a[i]:=a[j];

a[j]:=temp;

end;

procedure Heapify(what:word);

var

max:word;

begin

while what*2<=N do

begin

max:=what;

if a[what*2]>a[max] then

max:=what*2;

if (what*2+1<=N)AND

(a[what*2+1]>a[max]) then

max:=what*2+1;

if max=what then

what:=n

else

begin

Xch(what,max);

what:=max;

end;

end;

end;

begin

for i:=N div 2 downto 1 do

Heapify(i);

i:=N;

while N>1 do

begin

Xch(1,N);

Dec(N);

Heapify(1);

end;

N:=i;

end;

var

kuski:list;

s,N,M,i:word;

fi,fo:text;

temp:longint;

begin

assign(fi,'chain.dat');

assign(fo,'chain.sol');

reset(fi);

rewrite(fo);

readln(fi,N);

for i:=1 to N do

begin

read(fi,temp);

if temp>=Inf then

kuski[i]:=Inf

else

kuski[i]:=temp;

end;

heapsort(kuski,N);

s:=0;

i:=1;

M:=0;

while s+kuski[i]<N-i do

begin

Inc(M);

s:=s+kuski[i];

Inc(i);

end;

writeln(fo,N-M-1);

close(fi);

close(fo);

end.

Белорусский рейтинг MyMinsk.com Сайты беларуси Регистр "ЗУБР" Каталог на TIGA.BY, а также  новости, работа, объявления, фото и многое другое Рейтинг@Mail.ru Rambler's Top100 Белорусский каталог программ
Hosted by uCoz