1. «Выражение» (10 баллов)
Даны N целых чисел X1, X2, …, Xn. Расставить между ними знаки «+» или «–» так, чтобы значение получившегося выражения было равно заданному целому S.
Ограничения:
.
Вход: из файла expr.in. В первой строке находятся числа N и S. В следующей строке — N чисел через пробел.
Вывод: в файл expr.out. Если получить требуемый результат невозможно, вывести «No solution», если можно — то вывести равенство. Если решение не единственное, то вывести любое.
Пример:
Ввод 1 Ввод 2
3 10 2 100
15 25 30 10 10
Вывод 1 Вывод 2
15+25-30=10 No solution
2. «Возрастающая подпоследовательность» (15 баллов)
Даны N целых чисел X1, X2, …, Xn. Требуется вычеркнуть из них минимальное количество чисел так, чтобы оставшиеся шли в порядке возрастания.
Ограничения:
.
Ввод из файла incseq.in. В первой строке находится число N. В следующей строке — N чисел через пробел.
Вывод в файл incseq.out. В первой строке выводится количество невычеркнутых чисел, во второй — сами невычеркнутые числа через пробел в исходном порядке. Если вариантов несколько — вывести любой.
Пример
Ввод
6
2 5 3 4 6 1
Вывод
4
2 3 4 6
3. «Игра "Даты"», «2012» (15 баллов)
Играют двое. Задается какая-то дата 2012 года (2004 года). Каждый игрок на своем ходе называет более позднюю дату, увеличивая на 1 или 2 либо день в месяце, либо месяц, но не то и другое сразу. При этом сочетание дня и месяца должно оставаться датой. Игрок, назвавший 31 декабря, проигрывает. Оба играют наилучшим образом. Исходя из заданной даты, вывести, кто выиграет.
Ограничения: месяц от 1 до 12, день от 1 до числа дней в месяце, даты «31 декабря» во входных данных нет.
Ввод из файла dategame.in. В первой строке находятся разделенные пробелом числа, обозначающие день и месяц.
Вывод в файл dategame.out. Вывести 1, если выигрывает первый (начинающий) игрок, или 2 — в противном случае.
Пример
Ввод 1 Ввод 2 Ввод 3
30 12 29 12 29 11
Вывод 1 Вывод 2 Вывод 3
2 1 2
4. «Статическая сложность» (15 баллов)
Анализ временной сложности алгоритмов — важный инструмент создания эффективных программ. Алгоритмы, выполняемые за линейное время, как правило, значительно быстрее алгоритмов, требующих для выполнения той же задачи квадратичного времени, так что предпочтение должно быть отдано первым.
Обычно определяют время выполнения алгоритма по отношению к n — «размеру» входных данных. Это может быть число объектов, которые нужно отсортировать, число точек многоугольника и т. п. Поскольку определение формулы зависимости временной сложности алгоритма от n — непростая задача, было бы замечательно, если бы ее можно было автоматизировать. К сожалению, в общем случае это невозможно. Но в этой задаче мы будем рассматривать задачи очень простой природы, над которыми это можно проделать. Рассматриваемые программы записаны согласно следующим правилам БНФ, где <число> может быть любым неотрицательным целым числом:
<Программа> ::= BEGIN <Список операторов> END
<Список операторов> ::= <Оператор> | <Оператор> <Список операторов>
<Оператор> ::= <Оператор LOOP> | <Оператор OP>
<Оператор LOOP> ::= <Заголовок LOOP> <Список операторов> END
<Заголовок LOOP> ::= LOOP <число> | LOOP n
<Оператор OP> ::= OP <число>
Время выполнения такой программы может быть вычислено следующим образом: выполнение оператора OP требует столько единиц времени, сколько указано в его параметре. Список операторов, заключенный в оператор LOOP, выполняется столько раз, сколько указано в параметре оператора, т. е. или заданное константное число раз, если задано число, или n раз, если параметром является n. Время выполнения списка операторов равно сумме времени выполнения его частей. Таким образом, время выполнения программы в целом зависит от n.
Ограничения: вложенность операторов LOOP не превышает 10, размер входного файла не более 10 Кбайт, коэффициенты многочлена в ответе не превышают 50 000.
Ввод из файла icomplex.in. В первой строке находится целое число k — число программ во входном файле. Затем идут k программ, удовлетворяющих приведенной грамматике. Пробелы и переводы строк могут встречаться везде в программе, но не в ключевых словах BEGIN, END, LOOP и OP, нет их и в целых числах.
Вывод в файл icomplex.out. Для каждой программы сначала идет строка с номером программы. Общий вид первой строки: «Program #номер_программы» (см. пример ниже).
В следующей строке записывается время работы программы в терминах n — многочлен степени не более 10. Многочлен должен быть записан обычным способом, т. е. подобные слагаемые долны быть приведены, слагаемое большей степени должно предшествовать слагаемому меньшей степени, слагаемые с коэффициентом 0 не записываются. Общий вид второй строки: «Runtime = a*n^10+b*n^9+...+i*n^2+j*n+k». Если время выполнения нулевое, нужно вывести «Runtime = 0». За строкой с многочленом должна следовать пустая строка.
Пример
Ввод
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