|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Zapadinsky Anatoly \(ZAB\) 2:5020/400 30 Jan 2002 18:06:09
To : Aleksey Nilov
Subject : Re: Посоветуйте алгоритм, очень надо!!!
--------------------------------------------------------------------------------
Hello, Aleksey!
You wrote to ALL on Thu, 24 Jan 2002 19:46:28 +0300:
AN> Привет, ALL
AN> Имеется задача:
AN> Дана стpока, состоящая из скобок 4-х видов (,),[,]
AN> Опpеделить минимальное число скобок, котоpые надо подставить в
AN> стpоку, чтобы она стала "пpавильной"...
AN> Hапpимеp:
AN> "[ ( ] )" - "непpавильная стpока"
AN> "[ ] ( [ ] )" - "пpавильная", полученная путем подстановки в
AN> "непpав-ю" 2-х скобок!
AN> Интеpесует алгоpитм... условие - сложность <= O(N*N), а желательно
AN> O(N*log N)
Вот написал небольшой глючный алгоритм который однака проходит все
упоминавшиеся здесь тесты!
var
InS: string;
Right, Left: string;
LeftPos, RightPos: Integer;
EndCnt, OpenCnt: array[0..1] of Integer;
begin
Readln(InS);
EndCnt[0] := 0;
EndCnt[1] := 0;
OpenCnt[0] := 0;
OpenCnt[1] := 0;
Left := ''; Right := '';
for LeftPos := 1 to Length(InS) do
case InS[LeftPos] of
'(': Inc(OpenCnt[0]);
'[': Inc(OpenCnt[1]);
')': Inc(EndCnt[0]);
']': Inc(EndCnt[1]);
end;
LeftPos := 1;
RightPos := Length(InS);
while LeftPos <= RightPos do
begin
if InS[LeftPos] = ')' then
begin
Left := Left + '()';
Inc(LeftPos);
Dec(EndCnt[0]);
Continue;
end;
if InS[LeftPos] = ']' then
begin
Left := Left + '[]';
Inc(LeftPos);
Dec(EndCnt[1]);
Continue;
end;
if InS[RightPos] = '(' then
begin
Right := Right + ')(';
Dec(RightPos);
Dec(OpenCnt[0]);
Continue;
end;
if InS[RightPos] = '[' then
begin
Right := Right + '][';
Dec(RightPos);
Dec(OpenCnt[1]);
Continue;
end;
if (InS[LeftPos] = '(') and (InS[RightPos] = ')') then
begin
Left := Left + '(';
Right := Right + ')';
Dec(OpenCnt[0]);
Dec(EndCnt[0]);
Inc(LeftPos);
Dec(RightPos);
Continue;
end;
if (InS[LeftPos] = '[') and (InS[RightPos] = ']') then
begin
Left := Left + '[';
Right := Right + ']';
Dec(OpenCnt[1]);
Dec(EndCnt[1]);
Inc(LeftPos);
Dec(RightPos);
Continue;
end;
if InS[LeftPos] = '(' then
begin
if EndCnt[0] > OpenCnt[1] then
begin
Left := Left + '[';
Right := Right + ']';
Dec(EndCnt[1]);
Dec(RightPos);
end
else
begin
Left := Left + '(';
Right := Right + ')';
Dec(OpenCnt[0]);
Inc(LeftPos);
end;
end
else
begin
if EndCnt[1] < OpenCnt[0] then
begin
Left := Left + '[';
Right := Right + ']';
Dec(EndCnt[0]);
Inc(LeftPos);
end
else
begin
Left := Left + '(';
Right := Right + ')';
Dec(OpenCnt[1]);
Dec(RightPos);
end;
end;
end;
Write(Left);
for RightPos := Length(Right) downto 1 do Write(Right[RightPos]);
Writeln;
Readln;
end.
Оптимизировать можно сколько влезет...
Вопрос: Hа каком тесте он запарывается?
--- ifmail v.2.15dev5
* Origin: Demos online service (2:5020/400)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
| Тема: |
Автор: |
Дата: |
|
Посоветуйте алгоритм, очень надо!!! |
Aleksey Nilov |
24 Jan 2002 20:46:28 |
 Re: Посоветуйте алгоритм, очень надо!!! |
Grandalf Gray |
25 Jan 2002 19:44:12 |
  Re: Посоветуйте алгоритм, очень надо!!! |
Grandalf Gray |
25 Jan 2002 20:52:01 |
 Re: Посоветуйте алгоритм, очень надо!!! |
Aleksey Nilov |
26 Jan 2002 03:00:47 |
|
Re^2: Посоветуйте алгоритм, очень надо!!! |
Sergey Politov |
26 Jan 2002 06:50:50 |
|
Посоветуйте алгоритм, очень надо!!! |
Max Alekseyev |
25 Jan 2002 23:15:54 |
|
Посоветуйте алгоритм, очень надо!!! |
Max Alekseyev |
26 Jan 2002 03:40:34 |
|
Посоветуйте алгоритм, очень надо!!! |
Max Alekseyev |
25 Jan 2002 22:08:58 |
|
Re: Посоветуйте алгоритм, очень надо!!! |
Grandalf Gray |
26 Jan 2002 12:46:42 |
|
Посоветуйте алгоритм, очень надо!!! |
Max Alekseyev |
26 Jan 2002 02:30:30 |
|
Re: Посоветуйте алгоритм, очень надо!!! |
Grandalf Gray |
26 Jan 2002 12:46:43 |
|
Посоветуйте алгоритм, очень надо!!! |
Max Alekseyev |
25 Jan 2002 22:04:28 |
|
Посоветуйте алгоритм, очень надо!!! |
Aleksey Nilov |
29 Jan 2002 01:53:54 |
 Посоветуйте алгоритм, очень надо!!! |
Max Alekseyev |
28 Jan 2002 16:49:14 |
|
Re: Посоветуйте алгоритм, очень надо!!! |
Sergey Politov |
29 Jan 2002 06:34:29 |
|
Re: Посоветуйте алгоритм, очень надо!!! |
Aleksey Nilov |
31 Jan 2002 02:43:30 |
|
Re: Посоветуйте алгоритм, очень надо!!! |
Ilya Potrepalov |
31 Jan 2002 09:41:58 |
|
Re: Посоветуйте алгоритм, очень надо!!! |
Ilya Potrepalov |
31 Jan 2002 13:11:33 |
|
Re^2: Посоветуйте алгоритм, очень надо!!! |
Sergey Politov |
01 Feb 2002 06:43:50 |
|
Re: Re^2: Посоветуйте алгоритм, очень надо! !! |
Ilya Potrepalov |
01 Feb 2002 15:46:36 |
|
Посоветуйте алгоритм, очень надо!!! |
Sergey Ezhov |
26 Jan 2002 14:03:07 |
|
Посоветyйте алгоpитм, очень надо!!! |
Stanislav Aranovsky |
27 Jan 2002 02:28:38 |
|
Посоветyйте алгоpитм, очень надо!!! |
Sergey Ezhov |
27 Jan 2002 22:36:11 |
|
Посоветyйте алгоpитм, очень надо!!! |
Stanislav Aranovsky |
28 Jan 2002 14:08:18 |
|
Re: Посоветyйте алгоpитм, очень надо!!! |
Sergey Politov |
30 Jan 2002 07:23:33 |
|
Посоветyйте алгоpитм, очень надо!!! |
Sergey Ezhov |
30 Jan 2002 22:54:47 |
|
Посоветуйте алгоритм, очень надо!!! |
Nickita A Startcev |
30 Jan 2002 02:18:38 |
|
Посоветyйте алгоpитм, очень надо!!! |
Stanislav Aranovsky |
27 Jan 2002 02:39:02 |
|
Re: Посоветyйте алгоpитм, очень надо!!! |
Sergey Politov |
27 Jan 2002 06:23:28 |
|
Посоветyйте алгоpитм, очень надо!!! |
Stanislav Aranovsky |
28 Jan 2002 03:18:38 |
|
Re: Посоветyйте алгоpитм, очень надо!!! |
Sergey Politov |
28 Jan 2002 06:46:54 |
|
Посоветyйте алгоpитм, очень надо!!! |
Stanislav Aranovsky |
29 Jan 2002 15:25:24 |
|
Посоветyйте алгоpитм, очень надо!!! |
Oleg Yanchenkov |
30 Jan 2002 22:03:08 |
|
Посоветyйте алгоpитм, очень надо!!! |
Stanislav Aranovsky |
01 Feb 2002 02:45:34 |
|
re: Посоветyйте алгоpитм, очень надо!!! |
Valentin Kononov |
30 Jan 2002 00:07:05 |
|
Re: Посоветyйте алгоpитм, очень надо!!! |
Andrew Ezhguroff |
31 Jan 2002 01:40:00 |
|
Посоветyйте алгоpитм, очень надо!!! |
Stanislav Aranovsky |
31 Jan 2002 02:19:28 |
|
Re^2: Посоветyйте алгоpитм, очень надо!!! |
Sergey Politov |
31 Jan 2002 05:25:21 |
|
re: Посоветyйте алгоpитм, очень надо!!! |
Valentin Kononov |
31 Jan 2002 23:44:04 |
|
re:Посоветyйте алгоpитм, очень надо!!! |
Valentin Kononov |
04 Feb 2002 00:16:36 |
|
Re: re:Посоветyйте алгоpитм, очень надо!!! |
Ilya Potrepalov |
05 Feb 2002 07:58:56 |
|
Посоветyйте алгоpитм, очень надо!!! |
Oleg Yanchenkov |
28 Jan 2002 08:30:07 |
|
Re: Посоветyйте алгоpитм, очень надо!!! |
Sergey Politov |
29 Jan 2002 06:08:00 |
|
Посоветyйте алгоpитм, очень надо!!! |
Stanislav Aranovsky |
29 Jan 2002 15:27:40 |
|
Re: Посоветуйте алгоритм, очень надо!!! |
Michael Leontyev |
29 Jan 2002 14:46:19 |
|
Посоветyйте алгоpитм, очень надо!!! |
Stanislav Aranovsky |
30 Jan 2002 04:25:30 |
|
Re: Посоветyйте алгоpитм, очень надо!!! |
Michael Leontyev |
30 Jan 2002 10:45:03 |
|
Re^2: Посоветуйте алгоритм, очень надо!!! |
Sergey Politov |
30 Jan 2002 07:55:24 |
|
Посоветyйте алгоpитм, очень надо!!! |
Oleg Yanchenkov |
01 Feb 2002 00:31:21 |
|
Re: Посоветуйте алгоритм, очень надо!!! |
Zapadinsky Anatoly \\(ZAB\\) |
30 Jan 2002 18:06:09 |
|
Re: Посоветуйте алгоритм, очень надо!!! |
Michael Leontyev |
30 Jan 2002 18:59:35 |
|
|
