1

Задача 1. Знакопеременная последовательность

Для раскодирования информации, посылаемой по проводам связи, специальный прибор должен считать количество отрезков возрастания и убывания напряжения в проводе. На вход прибору подается N замеренных в разные отрезки времени величин напряжения a1, a2, ..., aN, а прибор должен выдать длину максимальной знакопеременной последовательности . Числа  должны встречаться в исходной последовательности a1, a2, ..., aN  в том же порядке (то есть i1 < i2 < ... < iM) и должны удовлетворять одной из двух следующих систем неравенств:  или  .

Чтобы подавить шумы, возникающие в линиях связи, введены следующие два ограничения на знакопеременную подпоследовательность. Во-первых, числа в исходной последовательности должны быть удалены друг от друга не менее, чем на L, то есть i2 - i1 ≥ L, i3 -i2 ≥ L, ..., iM  - iM-1 ≥ L. Во-вторых, два рядом идущих числа должны отличаться по модулю не менее, чем на U, то есть , , ..., .

Входные данные

В первой строке входного файла записаны через пробел целые положительные числа N, L, U, причем N ≤ 5000, L ≤ 5000, U  ≤ 109. В последующих N строках содержатся целые числа ai, по одному в каждой строке, |ai|≤109.

Выходные данные

В единственной строке выходного файла должно содержаться число M - длина максимальной знакопеременной подпоследовательности, удовлетворяющей указанным ограничениям.

Пример

Входной файл: input.txt

Выходной файл: output.txt

 
4 2 4
3
8

2

7

2

 
 

Задача 2. Лабиринт со сдвигами

В далёкой сказочной стране жил-был волшебник. Как-то раз узнал волшебник о существовании магической книги, написанной в давние времена. Неизвестно ни то, о чём эта книга, ни зачем она была написана, но зато известно, где она была спрятана. А спрятал ее злой маг. Он хотел, чтобы никто и никогда не смог достать эту книгу, и поэтому создал лабиринт, который необходимо пройти,  чтобы добраться до нее.

Лабиринт расположен под землёй, на N этажах. Каждый этаж состоит из M блоков, выстроенных в ряд. Некоторые блоки могут быть полыми. Перемещаться по лабиринту можно только внутри полых блоков сверху вниз, а также между полыми блоками, соприкасающимися своими гранями, вправо и влево, причем нельзя переходить с нижнего этажа на верхний.

Рассмотрим лабиринт, состоящий из трех этажей, каждый з которых образован семью блоками (N = 3, M = 7).


 

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

Например, так: или так:
1 сдвиг первого этажа влево;

1 сдвиг второго этажа вправо		 3 сдвига третьего этажа вправо

 

И, наконец, есть ещё одно важное условие - суммарное количество всех элементарных сдвигов должно быть минимальным, иначе включится секретный механизм и лабиринт обрушится.

Входные данные

В первой строке входного файла через пробел записаны два целых числа N и M  (0 < N < 100, 0 < M < 50) - размеры лабиринта.

В следующих N строках располагается описание этажей лабиринта. Каждый этаж задается M символами 'X' или '.'. 'X' обозначает заполненный блок, а '.' - полый блок.

Выходные данные

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

Примеры

Входной файл: input.txt

Выходной файл: output.txt

3 7

XXX..XX

X.XX..X

XX.XXXX

2

5 5

XXX.X

X.XXX

XX..X

X.X.X

XX.XX

3

5 5

XXX.X

XXXXX

XX..X

X.X.X

XX.XX

-1

 

Задача 3. Многопроцессорная система

Многопроцессорная система состоит из N (N £ 1000) процессоров. На ней требуется выполнить K (K £ 1000) независимых программ. Известны объемы всех программ, а также скорости работы каждого процессора.

Требуется определить минимальное время, за которое все программы будут выполнены. В процессе работы процессоры могут обмениваться программами, не теряя при этом времени, и продолжать выполнять программы, начатые другими процессорами.

Входные данные

В первой строке входного файла содержится число K. Начиная со следующей строки, задаются К целых чисел, разделенных пробелами или символами конца строки, - времена исполнения этих программ на стандартном процессоре в секундах.

В следующей строке содержится число N. Далее с новой строки приводятся N положительных действительных чисел. Эти числа определяют отношение скоростей работы  соответствующих процессоров к скорости стандартного. Они не превышают 1000 и разделены пробелами или символами конца строки.

Выходные данные

В выходной файл требуется вывести одно вещественное число - минимальное время выполнения всех программ  в секундах с точностью до 0.00001.

Пример

Входной файл: input.txt

Выходной файл: output.txt

2

10 2

3

1.0 0.5 0.4

10.0

 

Задача 4. Циклический ряд

Последовательность из 2n  чисел называется циклическим рядом, если выполнены следующие требования:

         все элементы последовательности различны;

         все элементы последовательности - целые неотрицательные числа;

         все элементы последовательности меньше 2n;

         двоичные записи любых двух соседних чисел отличаются лишь в одном разряде;

         двоичные записи первого и последнего числа отличаются лишь в одном разряде.

Требуется для заданного целого числа n построить какой-нибудь циклический ряд.

Входные данные

Во входном файле задано целое неотрицательное число n < 14.

Выходные данные

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

Пример

Входной файл: input.txt

Выходной файл: output.txt

2

0 1 3 2

 

Задача 5. Программа для робота

На одном секретном заводе инженеры задумались об экономии топливных расходов. Дело в том, что каждый день робот-конструктор перемещается от одного объекта завода до другого в соответствии со своей программой. При перемещении робот тратит топливо как на движение по прямой, так и на повороты. Инженеры решили перепрограммировать робота, чтобы он затрачивал на перемещение минимальное количество топлива. Ваша задача состоит в том, чтобы составить для робота такую программу.

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

Входные данные

В первой строке входного файла заданы четыре целых неотрицательных числа A, B, C, D, не превосходящие 100 каждое. Число A обозначает количество топлива, требующееся на перемещение из одной клетки в соседнюю;. B и С - количество топлива, требующееся на изменение направления движения робота, соответственно, направо и налево на 90 градусов;  D - количество топлива, требующееся для разворота робота при его движении. Во второй строке входного файла содержится целое число M - количество контрольных пунктов на территории завода. В каждой из последующих M строк заданы координаты клеток, соответствующие этим контрольным пунктам. Координатами клетки называется пара номеров горизонтали и вертикали, на которых она находится. При этом по горизонтали клетки считаются  слева направо, по вертикали - снизу вверх.

Выходные данные

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

Примеры

Входной файл: input.txt

Выходной файл: output.txt

10 20 30 40

2

1 1

2 1

10

1 2

10 20 30 40

4

1 1

1 3

1 5

5 3

90

1 2 4

10 20 100 30

4

1 1

1 3

1 5

5 3

150

1 2 3 2 4

 

Задача 6.  Нумерация координатной сетки

 

Узлы координатной сетки занумерованы по спирали, как показано на рисунке.  Необходимо по координате узла определить его номер.

 

Входные данные

В первой строке входного файла  записано целое число N - число тестов в файле            ( 0<N£100000).

В последующих N строках на каждой строке расположены два целых числа X и Y, разделённые пробелом, - координаты узлов по оси X и Y, соответственно (-20000 < X < 20000 , -20000 < Y < 20000).

Выходные данные

В выходной файл необходимо записать N целых чисел, по одному на строке, - номера соответствующих узлов, координаты которых указаны во входном файле.

Пример

Входной файл: input.txt

Выходной файл: output.txt

3

2 2

-1 -2

0 2

13

22

15

 

 

 

Задача 7. Преферанс

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

Требуется написать программу, которая указывает, как надо осуществить тасовку, чтобы в итоге получить заранее заданное расположение карт.

Входные данные

Единственная строка входного файла содержит информацию о порядке карт, в котором они должны оказаться после тасовки. Карты перечислены сверху вниз.

Каждая карта обозначается латинской буквой, указывающей масть (пики - S, трефы - C, бубны - D, червы - H), и номиналом (туз - A, король - K, дама - Q, валет - J, десятка - 0, остальные - в соответствии со своим значением: 9, 8, 7).

Выходные данные

В первую строку выходного файла необходимо вывести целое число N (0 £ N £ 5) - количество шагов тасовки. Следующие N строк должны содержать информацию о каждом шаге тасовки. Каждая строка при этом должна содержать 16 чисел, указывающих  номера позиций, на которых оказываются снятые карты. Номера позиций выводятся в порядке возрастания и разделены пробелами. Нумерация позиций производится сверху вниз от 1 до 32.

Если указанное расположение карт получить невозможно, то требуется вывести одно число "-1".

Пример

Входной файл: input.txt

C7 H7 C8 H8 C9 H9 C0 H0 S7 D7 S8 D8 S9 D9 S0 D0 SJ DJ SQ DQ SK DK SA DA CJ HJ CQ HQ CK HK CA HA

 

Выходной файл: output.txt

2

2 4 6 8 10 12 14 16 18 20 22 24 26 28 30 32

1 2 3 4 5 6 7 8 25 26 27 28 29 30 31 32

 

Задача 8. Лампочки

Для  проведения городского праздника на главной улице города развесили  n (1 £ n £ 108) разноцветных лампочек. Переключениями лампочек занимается компьютер, для которого была написана программа. Эта программа представляет собой последовательность из m целых чисел (1 £ m £ 10000). Числа в последовательности принимают значения от 1 до k (1 £ k £ 50). Компьютер через некоторый интервал времени считывает очередное число i и переключает все лампочки с номерами, кратными i. Если лампочка с номером, кратным i, горела, то она выключится, и наоборот. Изначально все лампочки горят. Главного менеджера праздника заинтересовало, сколько лампочек будет гореть после выполнения заданной программы. Помогите ему в этом.

Входные данные

В первой строке входного файла через пробел записаны целые числа n, k и m.

Следующая строка содержит последовательность из m целых чисел - программу переключения лампочек.

Выходные данные

В выходной файл необходимо выдать одно целое число - количество лампочек, которые останутся гореть.

Пример

Входной файл: input.txt

Выходной файл: output.txt

10 3 5

1 2 3 2 2

6