Олимпиадные задачи с решениями на Turbo Pascal от двух Дмитриев, Ильи ну и Александра
| Информационный Канал Subscribe.Ru |
Разбор полетов.
Задача №7. Правильное скобочное выражение.
В этой и следующей задаче основная проблема программиста – нехватка памяти и для ее преодоления приходится выкручиваться различными способами. Под нехваткой памяти в данном случае мы понимаем ограничение системы
Идея алгоритма проста: будем составлять список и обрабатывать его следующим образом: если в исходной последовательности встретилась открывающая скобка, то добавляем ее в список, если скобка закрывающая, то проверяем, является ли предыдущая скобка открывающей для этой: если да, то уничтожаем открывающую и продолжаем просматривать последовательность, иначе скобочная запись не будет правильной. Заметим также, что в любой момент просмотра длина списка для правильной скобочной записи не превышает N/2 (почему?), поэтому нам нужно также контролировать и длину списка: если она превысит N/2, то можно прекратить просмотр, заявив о некорректности скобочной записи.
Мы предложим вам решение, где списки будем представлять с помощью динамических структур, однако, на наш взгляд, решение с помощью массива проще. Но указанное замечание распространяется на обе реализации: 100 000*(1 байт) и 100 000*(5 байт) в памяти не поместятся (соответственно в статической и динамической), а вот 50 000*(1 байт) и 50 000*(5 байт) разместить можно.
type
TBr=recordop,cl: char;
end;
PList=^TList;
TList=record
bracket: char;
prev: PList;
end;
var inp,outp: text;
br: array[1..150]of TBr;
seq: PList;
newitem, delitem: PList;
i,n,seqlen: longint;
brstr: string;
buf: char;
begin
seq:=nil;
assign(inp,'input.txt');
reset(inp);
readln(inp,n);
for i:=1 to n do
begin
readln(inp,brstr);
br[i].op:=brstr[1];
br[i].cl:=brstr[2];
end;
seqlen:=0;
assign(outp,'output.txt');
rewrite(outp);
while not eof(inp) do
begin
read(inp,buf);
for i:=1 to n do
if buf=br[i].op then
begin
inc(seqlen);
if seqlen>50000 then
begin
write(outp,'incorrect');
close(outp);
exit;
end;
new(newitem);
newitem^.bracket:=buf;
newitem^.prev:=seq;
seq:=newitem;
break;
end else
if buf=br[i].cl then
if seq=nil then
begin
write(outp,'incorrect');
close(outp);
exit;
end else
if seq^.bracket=br[i].op then
begin
dec(seqlen);
delitem:=seq;
seq:=seq^.prev;
dispose(delitem);
break;
end
else begin
write(outp,'incorrect');
close(outp);
exit;
end;
end;
if seq=nil then write(outp,'correct')
else write(outp,'incorrect');
closefile(outp);
end.
Задачу №8 мы оставим вам еще на неделю. Если ваше решение кажется вам не слишком оптимальным, но все равно работает при N=250 000 за приемлемое время, то присылайте хотя бы идеи – мы обязательно их оценим.
Новые горизонты.
Сегодня, как мы и обещали, будут рассмотрены особые типы списков – стеки, очереди и деки.
Стек – специальный вид списка, в котором все вставки и удаления выполняются на одном конце, называемом вершиной. Про стеки говорят, что они работают по принципу LIFO – last-in-last-out (последний вошел – первый вышел). Интуитивными моделями стека могут служить колода карт при игре в “дурака” и стопка тарелок: во всех этих моделях взять можно только верхний предмет, а добавить новый объект можно, только положив его на верхний. В решении задачи №7 мы по сути дела использовали стек, не упоминая об этом – можно использовать списки, не сильно задумываясь, какая их разновидность используется – важно понимать принципы их построения и работы. Одно из многих применение стеков – исключение рекурсии. В этом случае стек может хранить текущие значения параметров процедуры, текущие значения всех локальных переменных процедуры и адрес возврата, т. е. адрес места, куда должно перейти управление после завершения процедуры.
Схематично можно представить стек следующим образом:
nil <-- A1 <-- A2 <-- ... <-- An
Здесь An – вершина стека.
Другой специализированный вид списка – очередь, где элементы вставляются с одного конца, а удаляются с другого. Очереди также называют “списками типа FIFO” (first-in-first-out: первым вошел – первым вышел). Работать с очередями можно так же, как и со стеками.
Схематично очередь можно представить следующим образом:
A1 --> A2 --> ... --> An
Здесь элементы добавляются к An, а изымаются с A1. В любой момент времени мы может непосредственно обратиться к элементам A1 и An и только к ним.
До сих пор мы рассматривали списки, которые были связаны только в одном направлении, что не всегда удобно. В некоторых программах возникает необходимость организовать эффективное перемещение по списку как в прямом, так и в обратном направлении. Или по заданному элементу нужно быстро найти предшествующий ему и последующие элементы. В этих ситуациях можно поместить в элемент списка два поля связи: с последующим и предыдущим элементом, т.е. организовать дважды связанный список (или дек). Заметим, что при реализации списка массивом ничего дополнительного создавать не нужно: достаточно уменьшить или увеличить индекс текущего элемента.
Схематично дек можно представить следующим образом:
A1 <--> A2 <--> ... <--> An
Заметим, что в дважды связанных списках легко можно организовать удаление элемента: в обычных списках нам потребуется хранить где-то предыдущий элемент для дальнейшей связи его с последующим, а в деке мы информации, хранимой в самом элементе, достаточно для удаления.
Время покодить.
Задача №9. "Золотые" слова. (1 балл).
"Золотыми" называются слова, до и после которых идет одинаковое количество знаков препинания.
Сама задача: в тексте найти "золотые" слова. Знаками препинания считаются только . : , ; - .
Input.txt: исходный текст(возможно в несколько строчек). Число слов в тексте не превосходит 1 000 000.
Output.txt: через "пробел" в строчку "золотые" слова, или файл должен быть пустым, если "золотых" слов нет.
Пример:
Input.txt: Текст ,не - обязан быть осмысленным, вообще не обязан,
Output.txt: обязан быть осмысленным
Задача №10. Корни. (1 балл)
Дано натуральное число n.
Последовательность задается следующим образом:
k[1]=sqrt(1+n);
k[2]=sqrt(1+n*sqrt(1+(n+1)))
k[3]=sqrt(1+n*sqrt(1+(n+1)*sqrt(1+(n+2))))
и так далее...
k[m]=sqrt(1+n*sqrt(1+(n+1)*sqrt(1+...+(n+m-1))...)
Во входном файле input.txt дано n, m (m>2) (0<=m, n, <=1 000 000 000);(n на первой строке, m на второй).
Вывести sqrt(k[m]) с точностью до 6 знаков.
Пример:
Input.txt:
41
23
Output.txt
6,480739
Всего хорошего, до следующего номера.
Решения слать на olimp@math.pomorsu.ru
Ищешь фильм? http://aslof.balzer.ru/
http://subscribe.ru/catalog/rest.cinema.filmforyou
| http://subscribe.ru/
E-mail: ask@subscribe.ru |
Отписаться
Убрать рекламу |
| В избранное | ||
