У Димы есть много книг, которые он ещё не прочитал. Дима обожает толстые старые книги. Кроме того, он не любит произведения с длинными названиями. В очередной раз, когда ему надо было выбрать себе книгу, он решил воспользоваться помощью компьютера. Мальчик составил список непрочитанных книг и определил критерии, по которым необходимо выбрать книгу: год издания должен быть ранее 1980-го, количество страниц—не менее 400, а название должно быть по возможности самым коротким из названий книг, удовлетворяющих первым двум условиям. Гарантируется, что хотя бы одна книга удовлетворяет перечисленным критериям.
Программа должна выводить количество книг в списке, изданных ранее 1980 г. и содержащих не менее 400 страниц, а также наименование книги с самым коротким названием.
Описание входных и выходных данных.
На вход программе сначала подаётся число имеющихся у Димы книг N. В каждой из следующих N строк находится описание какой-либо книги в следующем формате:
<�Фамилия автора> <�Год издания> <�Кол-во страниц> <�Название>, где <�Год издания>, <�Кол-во страниц>—целые числа;
<�Фамилия автора> — строка без пробелов, состоящая не более чем из 20 символов;
<�Название>—строка, состоящая не более чем из 40 символов. <�Фамилия автора>, <�Год издания>, <�Кол-во страниц>, <�Название> разделены между собой одним пробелом.
Пример входных данных:
5
Теккерей 1986 736 Ярмарка тщеславия
Булычев 1976 484 Великий Гусляр
Днепров 1974 798 Глиняный бог
Брэдбери 1964 368 Марсианские хроники
Казанцев 1988 637 Клокочущая пустота
Пример выходных данных для приведённого выше примера входных данных:
2
Глиняный бог
Напишите эффективную как по времени, так и по памяти программу для решения поставленной задачи, если известно, что вводятся сведения о N книгах.
Программа считается эффективной по времени, если время работы программы пропорционально N, то есть при увеличении N в k раз время работы программы должно увеличиваться не более чем в k раз. Программа считается эффективной по памяти, если размер памяти, необходимой программе для хранения всех переменных, не увеличивается с ростом числа N.
Максимальная оценка за правильную (не содержащую синтаксических ошибок и дающую правильный ответ при любых допустимых входных данных) программу, эффективную по времени и по памяти,—4 балла. Максимальная оценка за правильную программу, эффективную только по времени,—3 балла. Максимальная оценка за правильную программу, не удовлетворяющую требованиям эффективности,—2 балла.
Вы можете написать одну программу или две программы решения задачи (например, одна из программ может быть менее эффективна). Если вы напишете две программы, то каждая из них будет оцениваться независимо от другой, итоговой станет бо´ льшая из двух оценок. Перед текстом программы обязательно кратко опишите алгоритм решения. Укажите использованный язык программирования и его версию.
Программа читает все входные данные один раз. При прочтении данных очередной книги сразу проверяются условия: издана ли эта книга ранее 1980 года и содержит ли она не менее 400 страниц. Если оба условия одновременно выполняются, то значение счётчика увеличивается на единицу и проверяется условие: является ли название такой книги меньше уже просмотренных. В результате прочтения данных обо всех книгах становятся известны количество искомых книг и самое короткое название.
Пример программы на языке PascalABC 1.8.Программа эффективна по времени и по памяти.
var c: Char;
s, ms: string;
i, y, p, N, k, ml: Integer;
begin
Readln(N);
ml := 41; k := 0;
for i:=1 to N do
begin
repeat
Read(c);
until c=’ ’; {считана фамилия}
Read(y); Read(p);
Readln(s);
if (y < 1980) and (p >= 400) then
begin
Inc(k);
if Length(s) < ml then
begin
ml := Length(s);
ms := s;
end;
end;
end;
Writeln(k);
Writeln(ms)
end.