21/11/2024 19:36:55

Рабочее место участника

Выбрать соревнование

Задачи

Послать решение

Результаты проверки

Статистика по задачам

Вопросы и ответы

Результаты соревнования

Задачи

49. Статическая сложность

Ограничения: время – 2s/4s, память – 32MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод copy
Послать решение Blockly Посылки Темы Где Обсудить (0)

Анализ временной сложности алгоритмов – важный инструмент создания эффективных программ. Алгоритмы, выполняемые за линейное время, как правило, значительно быстрее алгоритмов, требующих для выполнения той же задачи квадратичного времени, так что предпочтение должно быть отдано первым. Обычно определяют время выполнения алгоритма по отношению к `n` – "размеру" входных данных. Это может быть число объектов, которые нужно отсортировать, число точек многоугольника и т.п. Поскольку определение формулы зависимости временной сложности алгоритма от `n` – непростая задача, было бы замечательно, если бы её можно было автоматизировать. К сожалению, в общем случае это невозможно. Но в этой задаче мы будем рассматривать программы очень простой природы, над которыми это можно проделать. Рассматриваемые программы записаны согласно следующим правилам БНФ, где <число> может быть любым неотрицательным целым числом:

<Программа> ::= "BEGIN" <Список операторов> "END"
<Список операторов> ::= <Оператор> | <Оператор> <Список операторов>
<Оператор> ::= <Оператор LOOP> | <Оператор OP>
<Оператор LOOP> ::= <Заголовок LOOP> <Список операторов> "END"
<Заголовок LOOP> ::= "LOOP" <число> | "LOOP n"
<Оператор OP> ::= "OP" <число>

Время выполнения такой программы может быть вычислено следующим образом: выполнение оператора OP требует столько единиц времени, сколько указано в его параметре. Список операторов, заключённый в оператор LOOP, выполняется столько раз, сколько указано в параметре оператора, то есть или заданное константное число раз, если задано число, или `n` раз, если параметром является n. Время выполнения списка операторов равно сумме времени выполнения его частей. Таким образом, время выполнения программы в целом зависит от `n`.

Ввод

В первой строке находится целое число `k` – число программ во входном файле. Затем идут `k` программ, удовлетворяющих приведённой грамматике. Пробелы и переводы строк могут встречаться везде в программе, но не в ключевых словах BEGIN, END, LOOP и OP, нет их и в целых числах.

Вывод

Для каждой программы сначала идёт строка с номером программы. В следующей строке записывается время работы программы в терминах `n` – многочлен степени не более 10. Многочлен должен быть записан обычным способом, то есть подобные слагаемые должны быть приведены, слагаемое с большей степенью должно предшествовать слагаемому с меньшей степенью, слагаемые с коэффициентом 0 не записываются, множители 1 не записываются. Общий вид второй строки "Runtime = a*n^10+b*n^9+...+i*n^2+j*n+k". Если время выполнения нулевое, нужно вывести "Runtime = 0". Между результатами должна быть пустая строка.

Ограничения: вложенность операторов LOOP не превышает 10, размер входного файла не более 2 Кбайт, коэффициенты многочлена в ответе не превышают `50\ 000`.

Пример ввода

2
BEGIN
  LOOP n 
    OP 4
    LOOP 3 LOOP n OP 1 END OP 2 END
    OP 1
  END
  OP 17
END

BEGIN
 OP 1997 LOOP n LOOP n OP 1 END END
END

Пример вывода

Program #1
Runtime = 3*n^2+11*n+17

Program #2
Runtime = n^2+1997

Источник: SWERC, 1997

03/07/2006	Лето 2006 дорешивание ( 4H)
10/07/2006	Лето 2006 - 4 (H)
12/05/2012	Занятие 18 (A)
21/10/2023	Марафон 80 задач, 1 этап (H)