Завод по огранке драгоценных камней приобрёл сейф повышенной надёжности. Для определения драгоценных камней, которые необходимо положить в сейф, сначала отбираются 5% самых дорогих камней.
Если у самого дешёвого камня из вошедших в группу 5% самых дорогих оказывается ценовая категория такая же, как и у нескольких других, то эти камни тоже включаются в группу камней для размещения в сейфе повышенной надёжности в том случае, если их ценовая категория не менее 15.
Напишите эффективную по времени работы и по используемой памяти программу (укажите используемую версию языка программирования, например, Borland Pascal 7.0), которая по результатам входных данных будет определять, какую минимальную цену должен иметь драгоценный камень, чтобы его поместили в сейф повышенной надёжности.
На вход программе сначала подаётся общее количество камней на складе N. В каждой из следующих N строк находится информация по каждому камню отдельно в следующем формате:
< Название драгоценного камня > < Код > < Ценовая категория >, где < Название драгоценного камня > — строка, состоящая не более чем из 20 символов, <Код> — строка, состоящая не более чем из 15 символов, < Ценовая категория > — целое число от 1 до 20.
< Название драгоценного камня >, < Код > и < Ценовая категория > разделены одним пробелом. Пример входной строки: Рубин Р 123413.
Программа должна выводить минимальную Ценовую категорию драгоценного камня, который необходимо положить в сейф повышенной надёжности.
Программа читает все входные данные один раз, сразу подсчитывая в массиве с индексами от 1 до 20 количество камней, принадлежащих определённой ценовой категории. Путём просмотра этого массива с конца (от 20-й ценовой категории) определяется число камней, заведомо попадающих в число 5% самых дорогих (добавление всех камней, следующей ценовой категории приводит к выходу за 5%). Последняя ценовая категория, в которую попало не менее одного драгоценного камня, запоминается. Если хотя чбы один из камней следующей ценовой категории также попадает в 5%, то проверяется имеют ли он и другие камни, набравшие столько же баллов, ценовую категорию не менее 15-й. В этом случае они все добавляются к числу драгоценных камней, которые необходимо поместить в сейф повышенной надёжности и ценовая категория которых является искомой.
Паскаль
var kcenkat : array[1..20] of integer;
с : char;
i,N,b,S,minckat : integer;
begin
for i:=0 to 20 do kcenkat[i]:=0;
readln(N);
for i:=l to N do
begin
repeat
read(c);
until c=' '; {считано название драгоценного камня}
repeat
read(c);
until c=' '; {считан код}
readln(b);
kcenkat[b]:-kcenkat[b]+1;
end;
S:=0; b:=20;
while S+kcenkat[b] < N*0.05 do
begin
if kcenkat[b]>0 then
begin
S:=S+kcenkat[b];
minckat:=b;
end;
b:=b-l;
end;{определены те камни, которые наверняка попадают
в сейф и пропущены ценовые категории, в которые
не попал ни один камень}
if S+1<=N*0.05 then
{если ещё хотя бы один драгоценный камень попадёт
в 5%,то проверяется: ценовая категория этого и
таких же камней — не менее 15-й}
if b>=15 then minckat:=b
writeln(minckat);
end.
Бейсик
DIM kcenkatU ТО 20) AS INTEGER
DIM ss AS STRING
INPUT N
FOR TO N
LINE INPUT ss
i=l
DO
c$sMID$(ss,i,l)
i-i+i;
LOOP WHILE c$<>" "
'Считываем название драгоценного камня
DO
c$-MID$(ss,i,l)
i-i+1
LOOP WHILE c$<>" "
'Считываем код
b=VAL(MID$(ss,i))
kcenkat(b)-kcenkat(b)+1
NEXT j
b-20
WHILE s+kcenkat(b)<=N*0.05
IF kcenkat(b)>0 THEN
s=s+kcenkat(b)
minckat-b
END IF
b=b-l
WEND
IF s+l<N*0.05 THEN
IF b>-15 THEN
minckat-b
END IF
END IF
PRINT minckat
END