Коэффициенты многочлена (30 мин., 100 баллов)

Дан многочлен (a_n*xⁿ+a_n-1*x_n-1+...+a_1*x+a₀)^k. Необходимо посчитать сумму коэффициентов многочлена после возведения в степень.

Входной файл (input.txt) в первой строке содержит значение n - степень многочлена в скобках. Во второй строке через пробел n+1 число - коэффициенты a_n в порядке убывания индекса. В третьей строке k - степень, в которую возводится многочлен.

Входные данные таковы, что результат не превосходит 10⁹.

Выходной файл (output.txt) содержит сумму коэффициентов многочлена после возведения в степень.

Пример

Исходные данные	Результат
1 1 1 2	4

Комментарий: (x+1)²=x²+2x+1.

1+2+1=4.

Шахматный номер (20 мин., 100 баллов)

Телефонный номер считается шахматным, если его цифры набираются на телефонном кнопочном номеронабирателе ходом шахматного коня. Сколько можно набрать разных семизначных шахматных номеров, которые начинаются с заданной цифры?

_____

1 2 3

4 5 6

7 8 9

__0__

Входной файл (input.txt) содержит одно число – первую цифру семизначного шахматного номера.

Выходной файл (output.txt) содержит одно число – ответ на вопрос задачи.

Пример

Исходные данные	Результат
1	136

Ханойские башни (30 мин., 100 баллов)

Ханойские башни - детская игра, основанная на одной из древних легенд.

Цель игры - перенести башню, состоящую из n колец, с иглы а на иглу с по следующим правилам:

· перемещать можно только одно кольцо;

· при переносе можно использовать любую иглу как вспомогательную;

· нельзя класть большее кольцо на меньшее.

Необходимо помочь играющему, определив порядок перемещения колец

Входной файл (input.txt) содержит единственное число - количество колец.

Выходной файл (output.txt) состоит из m строк, где m - количество перемещений колец с иглы на иглу, необходимое для перемещения всей башни. Каждая строка представляет собой два разделенных пробелом символа, первый из которых определяет с какой иглы снимается кольцо, а второй - на какую иглу оно перемещается. В конце файла не должно быть пустой строки.

Пример

Исходные данные	Результат
3	a c a b c b a c b a b c a c

Фокус (30 мин., 100 баллов)

Требуется отсортировать колоду карт лежащую на столе <рубашками> вверх. При этом должно обязательно соблюдаться условие - доступной для просмотра в колоде является только верхняя карта.

Колоду разрешается разделить на две (но не более) равные части, которые необходимо перевернуть рубашками вниз. Любую из доступных карт в каждой из этих колод можно оставить либо на месте, либо формировать из них новую колоду, кладя карту на стол рубашкой вверх. Сформированную колоду опять можно разделить на две. Такую процедуру можно многократно повторять.

Для упрощения поиска решения предполагается, что каждая карта помечена числом, которое соответствует её порядковому номеру в отсортированной колоде и количество карт в колоде всегда равно степени двойки.

Входной файл (input.txt) состоит из двух строк. Первая из них содержит число, определяющее количество карт в колоде. Вторая - числа, разделенные пробелом, которые соответствуют номерам карт в произвольно сложенной колоде с конца колоды к ее началу.

Выходной файл (output.txt) состоит из m строк, где m соответствует количеству разделений колоды на две. Каждая строка представляет собой последовательность разделенных пробелом чисел, определяющих порядок карт в сформированной на очередном шаге колоде. В конце файла не должно быть пустой строки.

Пример

Исходные данные	Результат
16 3 6 2 8 1 9 7 5 4 10 11 15 14 13 16 12	3 4 6 10 2 11 8 15 1 14 9 13 7 16 5 12 1 3 4 14 6 9 10 13 2 7 11 16 5 8 12 15 1 2 3 4 7 11 14 16 5 6 8 9 10 12 13 15 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16

Кубизм ( 30 мин., 100 баллов)

Дан параллелепипед [M, N, N], заполненный натуральными числами. Выполнить "Зеркальное отображение" его элементов относительно побочного сечения (см. рисунок).

Входной файл (input.txt) в первой строке содержит два натуральных числа: M, N (см. рисунок). В последующих строках расположены строки матриц вертикальных сечений параллелепипеда (матрицы отделены друг от друга пустой строкой, а элементы матрицы разделяются пробелом).

Выходной файл (output.txt) содержит матрицы вертикальных сечений параллелепипеда после зеркального отображения. Матрицы отделены друг от друга пустой строкой, а элементы матрицы разделяются пробелом. В конце файла не должно быть пустой строки.

Пример

Исходные данные	Результат
3 2 1 2 3 4 5 6 7 8 9 10 11 12	8 2 10 4 12 6 7 1 9 3 11 5

ПОЛИЗ (60 мин., 300 баллов)

ПОЛИЗ (польская инверсная запись) представляет собой постфиксную форму записи алгебраических выражений, которая в отличие от традиционной инфиксной формы не содержит скобок и не требует учета приоритетности операций в процессе вычисления выражения.

ПОЛИЗ формируется по следующим правилам (см. пример):

· знак операции(" + " , " - " , " / " , " * ") записывается непосредственно после двух (и только двух) операндов;

· если знак операции следует за одним операндом, второй операнд - это ранее вычисленное значение;

· для знака операции, предыдущим символом которого является знак операции, операнды - это два ранее вычисленных значения.

Входной файл (input.txt) состоит из строки, задающей выражение в инфиксной форме.

Выходной файл (output.txt) состоит из строки, задающей выражение в постфиксной форме. В конце файла не должно быть пустой строки.

Пример

Исходные данные	Результат
(((a+b)*d+e)/f)+(a/c)	аb+d*e+f/аc/+

Премудрые схемотехники (30 мин., 100 баллов)

Схемотехники перемудрили в создании нового процессора, и теперь, чтобы с ним работать, необходимо посылать в его регистр числа в обратном порядке бит двоичного представления. Например, число 514 (10 0000 0010) надо послать как 257 (01 0000 0001). Числа, которые необходимо посылать должны быть целые, от 512 до 1023.

Входной файл (input.txt) содержит строки потока чисел «истинного» представления.

Выходной файл (output.txt) содержит строки потока чисел, которые необходимо посылать в процессор. В конце файла не должно быть пустой строки.

Пример

Исходные данные	Результат
512 513 514	1 513 257

Фишки (30 мин., 100 баллов)

Вы являетесь одним из разработчиков новой компьютерной игры. Игра происходит на прямоугольной доске, состоящей из W*H клеток. Каждая клетка может либо содержать, либо не содержать фишку. Важной частью игры является проверка того, соединены ли две фишки путем, удовлетворяющим следующим свойствам:

1. Путь должен состоять из отрезков вертикальных и горизонтальных прямых.

2. Путь не должен пересекать других фишек.

При этом часть пути может оказаться вне доски. Вам необходимо написать программу, проверяющую, можно ли соединить две фишки путем, обладающим вышеуказанными свойствами, и, в случае положительного ответа, определяющую минимальную длину такого пути (считается, что путь имеет изломы, начало и конец только в центрах клеток (или "мнимых клеток", расположенных вне доски), а отрезок, соединяющий центры двух соседних клеток, имеет длину 1).

Входной файл (input.txt) в первой строке содержит два натуральных числа: W - ширина доски, H - высота доски (1<=W,H<=75). Следующие H строк содержат описание доски: каждая строка состоит ровно из W символов: символ (заглавная английская буква <икс>) обозначает фишку, символ <.> (точка) обозначает пустое место. Все остальные строки содержат описания запросов: каждый запрос состоит из четырёх натуральных чисел, разделённых пробелами - X1, Y1, X2, Y2, причём 1<=X1,X2<=W, 1<=Y1,Y2<=H. Здесь (X1, Y1) и (X2, Y2) - координаты фишек, которые требуется соединить (левая верхняя клетка имеет координаты (1,1)). Гарантируется, что эти координаты не будут совпадать (кроме последнего запроса; см. далее). Последняя строка содержит запрос, состоящий из четырёх чисел 0, разделенных пробелами; этот запрос обрабатывать не надо. Количество запросов не превосходит 20.

Выходной файл (output.txt) для каждого запроса содержит в отдельной строке одно целое число - длину кратчайшего пути, или 0, если такого пути не существует. В конце файла не должно быть перевода строки.

Пример

Исходные данные	Результат
5 4 XXXXX X...X XXX.X .XXX. 2 3 5 3 1 3 4 4 2 3 3 4 0 0 0 0	5 6 0