q
Mail.RuПочтаМой Мир0ОдноклассникиИгрыЗнакомстваНовостиПоиск
Имя    ( регистрация )
Пароль ( забыли? )

Метки  

Календарь


Задача D: Оптимизация программы

Язык программирования Berland Pascal 7.0 очень прост. Каждая его строка содержит один оператор, который является либо оператором присваивания, либо оператором вывода. Оператор присваивания имеет вид:
        <переменная>:=<выражение>;
Оператор вывода имеет вид:
        WRITELN(<выражение>);
Имя переменной всегда состоит из одной строчной буквы латинского алфавита ('A':'Z'), а выражение содержит переменные, знаки бинарных арифметических операций "#", "%", "&", круглые скобки и целочисленные константы. Выражение корректно с точки зрения стандартных математических правил.
Оптимизация программы состоит из двух фаз. Во время первой фазы в программе помечаются все строки, содержащие оператор присваивания вида "<переменная>:=<константа>;". Непомеченные в первой фазе строки подаются на вход оптимизатору. Относительный порядок следования строк при этом сохраняется.
Оператор присваивания может быть убран оптимизатором, если его удаление не влияет на результат вывода программы (следует учитывать, что этот оптимизатор не знает о возможном существовании строк, помеченных в первой фазе). Оптимизатор работает на ранней стадии компиляции и не может пользоваться правилами вычисления "#", "%", "&", а воспринимает их как некоторые абстрактные арифметические операции.
Ваша задача реализовать функциональность оптимизатора. На вход оптимизатору подаются строки программы, не помеченные в первой фазе. Вывод оптимизатора состоит из строк, поданных ему на вход, которые он не может убрать. Изменять выражения, переменные или еще как-то модифицировать программу нельзя.
Входные данные.
В первой строке входного файла содержится натуральное число N (1 ≤ N ≤ 100), где N - это количество строк, поданных на вход оптимизатору. Далее следует N строк, каждая из которых содержит оператор присваивания или оператор вывода. Все строки не содержат никаких лишних символов, комментариев и строго соответствуют описанному выше формату. Их длины не превосходят 32 символа. Входные данные не содержат пробелов. Во входных данных отсутствуют строки вида "<переменная>:=<константа>;", так как они были помечены на первой фазе.
Выходные данные.
Выведите строки программы, удалив все лишние операторы присваивания. Относительный порядок операторов менять нельзя.
Примеры:
input.txtoutput.txt
Пример #15
A:=B;
A:=B#C;
WRITELN(A);
C:=A;
WRITELN(B&2);
A:=B#C;
WRITELN(A);
WRITELN(B&2);
Пример #25
C:=5#1;
A:=X#Y&(Z#A);
A:=A#1;
B:=A&B;
WRITELN(C#A);
C:=5#1;
A:=X#Y&(Z#A);
A:=A#1;
WRITELN(C#A);
Пример #37
A:=B;
WRITELN(A);
A:=B;
WRITELN(A);
Z:=Z;
X:=Y;
WRITELN(Z);
A:=B;
WRITELN(A);
A:=B;
WRITELN(A);
WRITELN(Z);

Ограничение времени: 2 секунды
Ограничение памяти: 64 мегабайта
Входной файл: input.txt
Выходной файл: output.txt

Нравится
Написать комментарий


     14-03-2007 14:41 (ссылка)
Re: Задача D: Оптимизация программы
А какой ответ должен быть в этом тесте?

3
A:=B;
B:=A;
WRITELN(B);

Удаление 1 и 2 строки не приведет к измению ответа

Но к примеру оптимизатор Delphi не удаляет их

Kirill
     14-03-2007 14:48 (ссылка)
Re: Задача D: Оптимизация программы
Я полагаю что написание слишком хорошего оптимизатора приведет к WA :)
Но надо заметить, что это весьма не просто)
     14-03-2007 14:57 (ссылка)
Re: Задача D: Оптимизация программы
Хм... сейчас понял почему не надо удалять:)

     14-03-2007 17:26 (ссылка)
Re: Задача D: Оптимизация программы
Уважаемые организаторы, ответьте, пожалуйста, на мой вопрос:

Вопрос: Какой будет ответ для такого теста:
4
A:=B%C;
WRITELN(B);
A:=B%C;
WRITELN(A);

тут три варианта
1).Я склоняюсь к этому.
WRITELN(B);
A:=B%C;
WRITELN(A);

2).
A:=B%C;
WRITELN(B);
WRITELN(A);

3).Баг оптимизатора, если строчки рассматривать независимо.
WRITELN(B);
WRITELN(A);
     15-03-2007 08:47 (ссылка)
Re: Задача D: Оптимизация программы
Уважаемые организаторы, ответьте, пожалуйста, на мой вопрос:

Вопрос: Какой будет ответ для такого теста:
4
A:=5%3;
WRITELN(A);
A:=5%3;
WRITELN(A);

И на вот такой:

4
A:=(5%3);
WRITELN(A);
A:=5%3;
WRITELN(A);
     15-03-2007 21:49 (ссылка)
Re: Задача D: Оптимизация программы
Уважаемое жюри, моя программа не проходит только 1 тест.
В своем решении я проверял каждою строку на наличие в ней
пробелов и если таковые имеются - то все удалял.
( Ясно, что строки ответа, к примеру:
"A:=A#B;" и "A:=A#B;_" ("_"- пробел для внятности)
различны.
Но в условии сказано, что входные данные не содержат пробелов. )
Могло ли это послужить причиной WA?
     17-03-2007 00:34 (ссылка)
Re: Задача D: Оптимизация программы
Скажите пожалуйста, что значить: "Presentation error"?

Написать комментарий